【算法题解答·七】哈希

• 一个哈希 set1 用来保存数组1的值，一个哈希 resSet 用来保存相交的值

class Solution {public int[] intersection(int[] nums1, int[] nums2) {Set<Integer> set1 = new HashSet<>();Set<Integer> resSet = new HashSet<>();for (int i : nums1) { // 遍历数组1set1.add(i);}for (int i : nums2) { // 遍历数组2if (set1.contains(i)) { // 数组2中也存在则加入resSet.add(i);}}int[] arr = new int[resSet.size()];int j = 0;for (int i : resSet) {arr[j++] = i;}return arr;}
}

class Solution {public int[] twoSum(int[] nums, int target) {int[] res = new int[2]; // 返回值if (nums == null || nums.length == 0) {return res;}Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {int t = target - nums[i];if (map.containsKey(t)) { // 包含关键字 tres[1] = i;res[0] = map.get(t); // 得到关键字的 valuebreak;} else {map.put(nums[i], i); // 加入 map}}return res;}
}

计算有多少组满足

• 首先定义 一个HashMap，key放a和b两数之和，value放a和b两数之和出现的次数
• 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中。
• 定义int变量count，用来统计 a + b + c + d = 0 出现的次数。
• 再遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。

class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int res = 0;Map<Integer, Integer> map = new HashMap<>();// 遍历 A和Bfor (int i : nums1) {for (int j : nums2) {int sum = i + j;// map.getOrDefault(sum, 0)如果存在sum返回其value,否则返回0map.put(sum, map.getOrDefault(sum, 0) + 1);}}// 遍历 C和Dfor (int i : nums3) {for (int j : nums4) {res += map.getOrDefault(0 - i - j, 0);}}return res;}
}

• 因为 不可包括重复 的三元组，使用 哈希法，去重过程 不好处理

• 使用 双指针法 要比 哈希法 高效一些，而且要求 返回的是数值 的话，就可以使用 双指针法了

• 和 15.三数之和 是同一个思路，多一层 for 循环，

• 对于 15.三数之和 双指针法就是将原本暴力O(n^3)的解法，降为O(n^2)的解法，
  18.四数之和 的双指针解法就是将原本暴力O(n^4)的解法，降为O(n^3)的解法

• 先把 "bac" 转化为 [b,a,c]，sort 排序后再转回字符串 "abc"，为它的 key
• 先把 "bca" 转化为 [b,c,a]，sort 排序后再转回字符串 "abc"，为它的 key
• 上述两者 key 相同

// sort 得到 key，相同的 key 加入同一个列表中
class Solution {public List<List<String>> groupAnagrams(String[] strs) {// 排序法Map<String, List<String>> map = new HashMap<>();// 遍历数组中的每个字符串for (String str : strs) {char[] ss = str.toCharArray(); // 转为字符数组Arrays.sort(ss); // 排序得到其 keyString key = String.valueOf(ss); // 字符数组 -> 字符串List<String> list = map.getOrDefault(key, new ArrayList<String>());list.add(str); // 结果中加入当前字符串map.put(key, list); // 更新 map}return new ArrayList<List<String>>(map.values());}
}

• 先找到起点 x，如果 x-1 也在 set 中，说明 x 不是起点
• 找到起点后，循环查看 set 中是否有下一个数

// 用 HashSet，查找元素方便，如果x-1也在set里，继续遍历直到没有x-1时，x为起点
class Solution {public int longestConsecutive(int[] nums) {int ans = 0;Set<Integer> st = new HashSet<>();// 把数组转换为哈希集合for (int num : nums) {st.add(num);}for (int x : st) {// 如果 x-1 在集合中，继续if (st.contains(x - 1)) {continue;}// x 是起点int y = x + 1; // 下一个数while (st.contains(y)) {y++;}// 循环结束后，y-1 是最后一个在哈希集合中的数ans = Math.max(ans, y - x);}return ans;}
}