哈希表的查找、插入及删除——217、633、349、128、202、500，290、532、205（五简四中）

本文主要是介绍哈希表的查找、插入及删除——217、633、349、128、202、500，290、532、205（五简四中），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

217. 存在重复元素（简单）

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

解法一、哈希

无则加入，有则代表重复，返回true

之后发现hs.add本身在存在时就会返回false，所以其实一次判断就好

class Solution {public boolean containsDuplicate(int[] nums) {HashSet<Integer> hs = new HashSet<>();for(int num : nums){if(hs.contains(num))return true;else hs.add(num);}return false;}
}

解法二、排序

class Solution {public boolean containsDuplicate(int[] nums) {Arrays.sort(nums);int n = nums.length;for (int i = 0; i < n - 1; i++) {if (nums[i] == nums[i + 1]) {return true;}}return false;}
}作者：力扣官方题解
链接：https://leetcode.cn/problems/contains-duplicate/solutions/518991/cun-zai-zhong-fu-yuan-su-by-leetcode-sol-iedd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

633. 平方数之和（中等）

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。

解法一、枚举

还是熟悉的sqrt法，如果double = int，在一定数据规格内可以判断有。就是效率有点让人不嘻嘻

class Solution {public boolean judgeSquareSum(int c) {int t =(int) Math.sqrt(c);for(int i = t;i >= 0;i--){if(Math.sqrt(c - i * i) == (int)Math.sqrt(c - i * i))return true;}return false;}
}

解法二、双指针

假定left <= right，a*+b*= c则返回，小于则加a，大于则减b

class Solution {public boolean judgeSquareSum(int c) {long left = 0;long right = (long) Math.sqrt(c);while (left <= right) {long sum = left * left + right * right;if (sum == c) {return true;} else if (sum > c) {right--;} else {left++;}}return false;}
}作者：力扣官方题解
链接：https://leetcode.cn/problems/sum-of-square-numbers/solutions/747079/ping-fang-shu-zhi-he-by-leetcode-solutio-8ydl/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解法三、数学

费马大定理：一个非负整数 c 如果能够表示为两个整数的平方和，当且仅当 c 的所有形如 4k+3 的质因子的幂均为偶数。

关于最后一次判断：如11*2*2, 转完后c=11，而11符合x%4==3的条件，却不符合双数。解决类似这样的情况。

class Solution {public boolean judgeSquareSum(int c) {for (int base = 2; base * base <= c; base++) {// 如果不是因子，枚举下一个if (c % base != 0) {continue;}// 计算 base 的幂int exp = 0;while (c % base == 0) {c /= base;exp++;}// 根据 Sum of two squares theorem 验证if (base % 4 == 3 && exp % 2 != 0) {return false;}}// 例如 11 这样的用例，由于上面的 for 循环里 base * base <= c ，base == 11 的时候不会进入循环体// 因此在退出循环以后需要再做一次判断return c % 4 != 3;}
}作者：力扣官方题解
链接：https://leetcode.cn/problems/sum-of-square-numbers/solutions/747079/ping-fang-shu-zhi-he-by-leetcode-solutio-8ydl/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

349. 两个数组的交集（中等）

给定两个数组 nums1 和 nums2 ，返回 它们的

交集。输出结果中的每个元素一定是唯一的。我们可以 不考虑输出结果的顺序 。

解法一、TreeSet

treeSet的特性：排序，不重复。当然hashSet也是一样的

class Solution {public int[] intersection(int[] nums1, int[] nums2) {TreeSet<Integer> hs = new TreeSet<>();List<Integer> list = new ArrayList<>();for(int num : nums1){hs.add(num);}for(int num:nums2){if(!hs.contains(num)){list.add(num);hs.remove(num);}}int[] res = new int[list.size()];for(int i = 0;i < list.size();i++){res[i] = list.get(i);}return res;}
}

解法二、双集合

两个数组转集合，然后用较小的集合分别搜索另一个有没有。getIntersection的前三行挺有意思的，可以确认较小的在前面，学了

class Solution {public int[] intersection(int[] nums1, int[] nums2) {Set<Integer> set1 = new HashSet<Integer>();Set<Integer> set2 = new HashSet<Integer>();for (int num : nums1) {set1.add(num);}for (int num : nums2) {set2.add(num);}return getIntersection(set1, set2);}public int[] getIntersection(Set<Integer> set1, Set<Integer> set2) {if (set1.size() > set2.size()) {return getIntersection(set2, set1);}Set<Integer> intersectionSet = new HashSet<Integer>();for (int num : set1) {if (set2.contains(num)) {intersectionSet.add(num);}}int[] intersection = new int[intersectionSet.size()];int index = 0;for (int num : intersectionSet) {intersection[index++] = num;}return intersection;}
}作者：力扣官方题解
链接：https://leetcode.cn/problems/intersection-of-two-arrays/solutions/469445/liang-ge-shu-zu-de-jiao-ji-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解法三、排序+双指针

先排序。维护pre避免重复，若不等，较小右移；若相等且和pre不等，加入，更新pre并同时右移；若相等且和pre相等，则只同时右移

class Solution {public int[] intersection(int[] nums1, int[] nums2) {Arrays.sort(nums1);Arrays.sort(nums2);int length1 = nums1.length, length2 = nums2.length;int[] intersection = new int[length1 + length2];int index = 0, index1 = 0, index2 = 0;while (index1 < length1 && index2 < length2) {int num1 = nums1[index1], num2 = nums2[index2];if (num1 == num2) {// 保证加入元素的唯一性if (index == 0 || num1 != intersection[index - 1]) {intersection[index++] = num1;}index1++;index2++;} else if (num1 < num2) {index1++;} else {index2++;}}return Arrays.copyOfRange(intersection, 0, index);}
}作者：力扣官方题解
链接：https://leetcode.cn/problems/intersection-of-two-arrays/solutions/469445/liang-ge-shu-zu-de-jiao-ji-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解法四、哈希

import java.util.*;class Solution {public int[] intersection(int[] nums1, int[] nums2) {List<Integer> result = new ArrayList<>();Map<Integer, Integer> hash = new HashMap<>();// 将 nums1 中的元素存入哈希表中for (int c : nums1) {hash.put(c, 1);}// 遍历 nums2 中的元素，检查是否在哈希表中并且只添加一次for (int c : nums2) {if (hash.containsKey(c) && hash.get(c) == 1) {result.add(c);hash.put(c, 0);  // 确保元素只添加一次}}// 将结果转换为 int 数组int[] resArray = new int[result.size()];for (int i = 0; i < result.size(); i++) {resArray[i] = result.get(i);}return resArray;}
}

128. 最长连续序列（中等）

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

解法一、哈希集

第一遍全丢进set，第二遍遍历set。如果num的上一个数不在哈希里（为了判断num是连续数字的第一个），则往右探索长度。

注意，第二遍遍历已经去重的set，如果遍历数组，花费时间会远大于预计

class Solution {public int longestConsecutive(int[] nums) {Set<Integer> hs = new HashSet<>();for(int num : nums){hs.add(num);}int res = 0;for(int num : hs){int y = 0;if(!hs.contains(num - 1)){while(hs.contains(num)){num++;y++;}}res = Math.max(res,y);}return res;}
}

解法二、排序

先排序，然后判断，记录步长。

class Solution {public int longestConsecutive(int[] nums) {if (nums == null || nums.length == 0) {return 0;}Arrays.sort(nums);int cur = nums[0];int max = 1;int step = 1;for (int i = 1; i < nums.length; i++) {if (nums[i] == cur) {} else if (nums[i] == cur + 1) {step ++;} else {max = Math.max(max, step);step = 1;}cur = nums[i];}return max;}
}

202. 快乐数(简单)

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

解法一、模拟，哈希

为了证明每个循环的数字都是一样的，我们可以使用数学中的不动点理论。在一个有限的系统中，重复应用一个确定的操作最终会达到一个循环，这是因为系统的状态是有限的。在快乐数的情况下，由于每次计算都是基于有限的数字（0-9）的平方，因此可能的结果也是有限的。这意味着，如果我们从某个数字开始，不断重复计算它的各位数字的平方和，最终必然会进入一个循环，因为可能的平方和是有限的，而且每次计算都是确定性的。

此外，由于每个非快乐数都会进入一个固定的循环，而这个循环不包含1，这意味着循环中的所有数字都是固定的，并且每次遇到同一个数字时，都会得到相同的下一个数字。这就是为什么每个循环的数字都是一样的。

综上所述，我们可以得出结论，对于非快乐数，它们在重复计算各位数字的平方和的过程中不仅会形成一个循环，而且每个循环中的数字都是一样的。这一结论是基于有限性原理和确定性操作的重复应用。

每次做一次改变，n更新为改变后的数，判断n在不在哈希集里。如果在，代表陷入了死循环；如果不在，存入旧n进哈希。1的平方还是1，所以必然跳出，判断结束循环时是不是1就可以。

class Solution {public boolean isHappy(int n) {Set<Integer> hs = new HashSet<>();hs.add(n);int temp = 0;do{hs.add(temp);temp = 0;while(n!=0){int j = n % 10;temp+= j * j;n/=10;}n = temp;}while(!hs.contains(n));return n==1;}
}

解法二、快慢指针

快走两步，慢走一步

class Solution {
public:int bitSquareSum(int n) {int sum = 0;while(n > 0){int bit = n % 10;sum += bit * bit;n = n / 10;}return sum;}bool isHappy(int n) {int slow = n, fast = n;do{slow = bitSquareSum(slow);fast = bitSquareSum(fast);fast = bitSquareSum(fast);}while(slow != fast);return slow == 1;}
};作者：金字塔下的小蜗牛
链接：https://leetcode.cn/problems/happy-number/solutions/21454/shi-yong-kuai-man-zhi-zhen-si-xiang-zhao-chu-xun-h/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解法三、数学

下一个值可能比自己大的最大数字是什么？根据我们之前的分析，我们知道它必须低于 243。因此，我们知道任何循环都必须包含小于 243 的数字，用这么小的数字，编写一个能找到所有周期的强力程序并不困难。

如果这样做，您会发现只有一个循环：4→16→37→58→89→145→42→20→4。所有其他数字都在进入这个循环的链上，或者在进入 1 的链上。

因此，我们可以硬编码一个包含这些数字的散列集，如果我们达到其中一个数字，那么我们就知道在循环中。

实话说有点像数根的那道题····

class Solution {private static Set<Integer> cycleMembers =new HashSet<>(Arrays.asList(4, 16, 37, 58, 89, 145, 42, 20));public int getNext(int n) {int totalSum = 0;while (n > 0) {int d = n % 10;n = n / 10;totalSum += d * d;}return totalSum;}public boolean isHappy(int n) {while (n != 1 && !cycleMembers.contains(n)) {n = getNext(n);}return n == 1;}
}作者：力扣官方题解
链接：https://leetcode.cn/problems/happy-number/solutions/224894/kuai-le-shu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

500. 键盘行（简单）

给你一个字符串数组 words ，只返回可以使用在 美式键盘 同一行的字母打印出来的单词。键盘如下图所示。

美式键盘 中：

第一行由字符 "qwertyuiop" 组成。
第二行由字符 "asdfghjkl" 组成。
第三行由字符 "zxcvbnm" 组成。

解法一、哈希查询

学会了直接把List转为Array的方法，学会了设置全局哈希表的方法（这个for-each循环也写得很漂亮）。我自己忽略了大小写的细节

官解用了预处理：
 String rowIdx = "12210111011122000010020202";

import java.util.*;class Solution {private static final Map<Character, Integer> charToRow = new HashMap<>();static {// 初始化字符到行号的映射for (char ch : "qwertyuiop".toCharArray()) {charToRow.put(ch, 1);}for (char ch : "asdfghjkl".toCharArray()) {charToRow.put(ch, 2);}for (char ch : "zxcvbnm".toCharArray()) {charToRow.put(ch, 3);}}public String[] findWords(String[] words) {List<String> validWords = new ArrayList<>();// 遍历每个单词for (String word : words) {int row = charToRow.get(Character.toLowerCase(word.charAt(0))); // 获取首字符的行号boolean isValid = true;// 检查每个字符是否属于同一行for (int i = 1; i < word.length(); i++) {if (charToRow.get(Character.toLowerCase(word.charAt(i))) != row) {isValid = false;break; // 如果有字符不在同一行，立即退出}}// 如果所有字符都在同一行，加入结果列表if (isValid) {validWords.add(word);}}// 将结果列表转换为数组并返回return validWords.toArray(new String[0]);}
}

解法二、正则

class Solution {public String[] findWords(String[] words) {// 正则表达式匹配三个键盘行的字符String pattern1 = "^[qwertyuiopQWERTYUIOP]+$";String pattern2 = "^[asdfghjklASDFGHJKL]+$";String pattern3 = "^[zxcvbnmZXCVBNM]+$";List<String> validWords = new ArrayList<>();for (String word : words) {if (word.matches(pattern1) || word.matches(pattern2) || word.matches(pattern3)) {validWords.add(word); // 如果匹配其中一个模式，将其加入结果列表}}return validWords.toArray(new String[0]);}
}

290. 单词规律（简单）

给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。

这里的遵循指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律

示例1:
输入: pattern = "abba", s = "dog cat cat dog"
输出: true
示例 2:
输入:pattern = "abba", s = "dog cat cat fish"
输出: false
示例 3:
输入: pattern = "aaaa", s = "dog cat cat dog"
输出: false

解法一、哈希

先split分割成Array，判断长度是否相等。然后遍历pattern的每一个字母，如果存在这个键，就比对是不是；如果不存在，且确保这个字符串和之前放进去的都不一样（避免不同的键指向同一个单词）就放进去。

class Solution {public boolean wordPattern(String pattern, String s) {int lenP = pattern.length();String[] temp = s.split(" ");HashMap<String,String> hm = new HashMap<>();if(lenP != temp.length)return false;for(int i = 0;i < lenP;i++){if(!hm.containsKey(String.valueOf(pattern.charAt(i)))){for(String c : hm.values()){if(c.equals(temp[i]))return false;}hm.put(String.valueOf(pattern.charAt(i)),temp[i]);}else{String p = hm.get((String.valueOf(pattern.charAt(i))));if(!p.equals(temp[i]))return false;}}return true;}
}

532. 数组中的 k-diff 数对（中等）

给你一个整数数组 nums 和一个整数 k，请你在数组中找出 不同的 k-diff 数对，并返回不同的 k-diff 数对 的数目。

k-diff 数对定义为一个整数对 (nums[i], nums[j]) ，并满足下述全部条件：

0 <= i, j < nums.length
i != j
|nums[i] - nums[j]| == k

注意，|val| 表示 val 的绝对值。

解法一、哈希

一开始全部放进hs里。如果k==0，那么第一个循环直接判断，重复就加计数；如果k不等于零，再开一个循环，然后计算。注意，因为不计算重合的部分，所以放了一个resSet来算值。

这里res只记了两个数里较小那个，避开了绝对值讨论。

class Solution {public static int findPairs(int[] nums, int k) {HashSet<Integer> hs = new HashSet<>();HashSet<Integer> res = new HashSet<>();for(int num : nums){if(k==0 && hs.contains(num) && !res.contains(num)){res.add(num);}hs.add(num);//如果不包括，则加入}if(k!=0){for(int num : nums){if(hs.contains(num - k)&& !res.contains(num)){//如果hs里有num-k，并且res里没有numres.add(num);}}}return res.size();}
}

解法二、排序+双指针

class Solution {public int findPairs(int[] nums, int k) {Arrays.sort(nums);int n = nums.length, y = 0, res = 0;for (int x = 0; x < n; x++) {if (x == 0 || nums[x] != nums[x - 1]) {while (y < n && (nums[y] < nums[x] + k || y <= x)) {y++;}if (y < n && nums[y] == nums[x] + k) {res++;}}}return res;}
}作者：力扣官方题解
链接：https://leetcode.cn/problems/k-diff-pairs-in-an-array/solutions/1602225/shu-zu-zhong-de-k-diff-shu-dui-by-leetco-ane6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

205. 同构字符串(简单)

给定两个字符串 s 和 t ，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

解法一、哈希

总体逻辑和290是一样的

class Solution {public boolean isIsomorphic(String s, String t) {HashMap<String,String> hm = new HashMap<>();int len = s.length();for(int i = 0;i < len;i++){if(!hm.containsKey(String.valueOf(s.charAt(i)))){for(String temp : hm.values()){if(temp.equals(String.valueOf(t.charAt(i))))return false;}hm.put((String.valueOf(s.charAt(i))),String.valueOf(t.charAt(i)));}else{if(!hm.get(String.valueOf(s.charAt(i))).equals(String.valueOf(t.charAt(i))))return false;}}return true;}
}

解法二、数组哈希

利用了ascii

 public boolean isIsomorphic(String s, String t) {char[] chars = s.toCharArray();char[] chart = t.toCharArray();int[] preIndexOfs = new int[256];int[] preIndexOft = new int[256];for (int i = 0; i < chars.length; i++) {if (preIndexOfs[chars[i]] != preIndexOft[chart[i]]) {return false;}preIndexOfs[chars[i]] = i + 1;preIndexOft[chart[i]] = i + 1;}return true;}