常见的三种哈希结构：
- 数组
- set（集合）
- map（映射）
数组对于那些知道长度的题目比较适宜，因为map的空间消耗要比数组的大，所以有的时候用数组更贱简单有效。但是数组的大小是有限的，受到系统栈空间（不是数据结构的栈）的限制。如果数组空间够大，但哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费，这时候可以考虑采用set。set是一个集合，里面放的元素只能是一个key，而有的题目还需要记录一些额外的信息，如下标或出现次数，这时候可以考虑用map。
一、两个数组的交集
题目链接：349.两个数组的交集
/** * <pre> * 维护两个hashSet，hashSet查找元素只需要O(1)的时间 * 或者对数组首先进行排序，随后使用双指针遍历 * </pre> * * @author <a href="https://github.com/kil1ua">Ken-Chy129</a> * @date 2023/1/8 11:43 */ public class 两个数组的交集349 { public int[] intersection(int[] nums1, int[] nums2) { Set<Integer> set1 = new HashSet<>(); Set<Integer> set2 = new HashSet<>(); for (int i : nums1) { set1.add(i); } for (int i : nums2) { set2.add(i); } if (set1.size() > set2.size()) { set2.removeIf(next -> !set1.contains(next)); int[] res = new int[set2.size()]; int i = 0; for (Integer integer : set2) { res[i++] = integer; } return res; } else { set1.removeIf(next -> !set2.contains(next)); int[] res = new int[set1.size()]; int i = 0; for (Integer integer : set1) { res[i++] = integer; } return res; } } public int[] intersection2(int[] nums1, int[] nums2) { Arrays.sort(nums1); Arrays.sort(nums2); int pos1 = 0, pos2 = 0, i=0; int[] res = new int[Math.min(nums1.length, nums2.length)]; while (pos1 < nums1.length && pos2 < nums2.length) { while (pos2 < nums2.length && nums2[pos2] < nums1[pos1]) { pos2++; } if (pos2 < nums2.length && nums2[pos2] == nums1[pos1]) { if (i == 0 || nums1[pos1] != res[i-1]) { // 保证元素的唯一性 res[i++] = nums2[pos2]; } pos1++; pos2++; continue; } pos1++; } return Arrays.copyOfRange(res, 0, i); } }
二、两个数组的交集 II
题目链接：350.两个数组的交集 II
/** * <pre> * 同样可以使用哈希表或者排序加双指针方式解决 * 由于需要保存相同的元素，所以不能用hashSet，而应该选择hashMap维护元素数量 * </pre> * * @author <a href="https://github.com/kil1ua">Ken-Chy129</a> * @date 2023/1/8 13:41 */ public class 两个数组的交集II350 { public int[] intersect(int[] nums1, int[] nums2) { Map<Integer, Integer> map = new HashMap<>(); for (int i : nums1) { map.put(i, map.getOrDefault(i, 0) + 1); } int[] res = new int[Math.min(nums1.length, nums2.length)]; int index = 0; for (int i : nums2) { Integer orDefault = map.getOrDefault(i, 0); map.put(i, orDefault-1); if (orDefault > 0) { res[index++] = i; } } return Arrays.copyOfRange(res, 0, index); } public int[] intersect2(int[] nums1, int[] nums2) { Arrays.sort(nums1); Arrays.sort(nums2); int pos1 = 0, pos2 = 0, i=0; int[] res = new int[Math.min(nums1.length, nums2.length)]; while (pos1 < nums1.length && pos2 < nums2.length) { while (pos2 < nums2.length && nums2[pos2] < nums1[pos1]) { pos2++; } if (pos2 < nums2.length && nums2[pos2] == nums1[pos1]) { res[i++] = nums2[pos2]; pos1++; pos2++; continue; } pos1++; } return Arrays.copyOfRange(res, 0, i); } }
三、快乐数
题目链接：[202. 快乐数]
/** * <pre> * 根据题目我们不难看出对于任何一个数只有两种可能，变为1或一直循环（不可能变得无限大） * 那么判断是否处于循环我们首先可以想到把前面出现的数字记录到set中，后面如果再次遇到就说明出现循环 * 同时我们还能联想到之前的环形链表问题，对于这类循环查找问题，我们可以使用快慢指针，如果出现循环快指针一定会与慢指针相遇 * </pre> * * @author <a href="https://github.com/kil1ua">Ken-Chy129</a> * @date 2023/1/8 13:51 */ public class 快乐数202 { public boolean isHappy(int n) { Set<Integer> set = new HashSet<>(); while (n != 1) { int r, k = n; n = 0; while (k != 0) { r = k % 10; k = k / 10; n += r * r; } if (set.contains(n)) { return false; } set.add(n); } return true; } public boolean isHappy2(int n) { int slow = n, quick = n; while (quick != 1) { quick = getNext(getNext(quick)); slow = getNext(slow); if (quick != 1 && quick == slow) { return false; } } return true; } public int getNext(int n) { int r, k=0; while (n != 0) { r = n % 10; n = n / 10; k += r * r; } return k; } }
四、四数相加
题目链接：454. 四数相加 II
/** * <pre> * 分组+哈希 * 对第一、二个数组维护一个哈希表存储相加的值和出现次数，然后遍历三四组的和，查找map中是否存在与之相反的记录，加上记录数 * </pre> * * @author <a href="https://github.com/kil1ua">Ken-Chy129</a> * @date 2023/1/8 15:44 */ public class 四数相加II454 { public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { Map<Integer, Integer> map = new HashMap<>(); for (int num1 : nums1) { for (int num2 : nums2) { map.put(num1 + num2, map.getOrDefault(num1 + num2, 0) + 1); } } int ans = 0; for (int num3 : nums3) { for (int num4 : nums4) { if (map.containsKey(-num3 - num4)) { ans += map.get(-num3 - num4); } } } return ans; } }
四数相加一题是为四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑重复问题。
而四数之和以及三数之和是一个数组（集合）里找到和为0的组合，需要去重导致代码效率很低，所以采用双指针而非哈希表。以下给出代码：
五、两数之和
题目链接：1.两数之和
/** * <pre> * 1.两重循环暴力遍历数组：O(n^2) * 2.哈希表存储数组+遍历哈希表判断表中是否存在另一个值使得和为target：O(n) * 3.排序+双指针：O(n*logn) * </pre> * * @author <a href="https://github.com/kil1ua">Ken-Chy129</a> * @date 2023/1/8 15:13 */ public class 两数之和1 { // 暴力遍历数组，二重循环，O(n^2) public int[] twoSum(int[] nums, int target) { int[] result = new int[2]; for(int i=0; i<nums.length; i++) { for(int j=i+1; j<nums.length; j++) { if(nums[i] + nums[j] == target) { result[0] = i; result[1] = j; break; } } } return result; } // 哈希表 public int[] twoSum2(int[] nums, int target) { // value为key所在的下标 Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; ++i) { if (map.containsKey(target - nums[i])) { return new int[]{map.get(target - nums[i]), i}; } map.put(nums[i], i); } return new int[0]; } }
1）三数之和
题目链接：15. 三数之和
/** * <pre> * 先对数组升序排序，随后遍历数组： * 第一层循环选择第一个数，得到剩下两个数的和应该取的目的值 * 第二层循环使用双指针遍历，一个从第一层循环下一位开始，一个从最后一位开始，后面的指针不断前移直到两指针和小于目的值，则前面的指针后移（因为数组从小到大，所以当满足的两个数分别选择的是第i位和第j位时，随着i下一次增加，j一定是减小的） * </pre> * * @author <a href="https://github.com/kil1ua">Ken-Chy129</a> * @date 2023/1/8 16:30 */ public class 三数之和15 { public List<List<Integer>> threeSum(int[] nums) { int n = nums.length; Arrays.sort(nums); List<List<Integer>> ans = new ArrayList<>(); for (int first=0; first<n; first++) { // 需要和上一次枚举的数不相同 if (first > 0 && nums[first] == nums[first - 1]) { continue; } // c 对应的指针初始指向数组的最右端 int third = n - 1; int target = -nums[first]; for (int second=first+1; second<n; second++) { if (second > first + 1 && nums[second] == nums[second - 1]) { continue; } while (second < third && nums[second] + nums[third] > target) { --third; } // 如果指针重合，随着 b 后续的增加就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环 if (second == third) { break; } if (nums[second] + nums[third] == target) { List<Integer> list = new ArrayList<>(); list.add(nums[first]); list.add(nums[second]); list.add(nums[third]); ans.add(list); } } } return ans; } }
2）四数之和
题目链接：18. 四数之和
/** * <pre> * 解法同三数之和 * </pre> * * @author <a href="https://github.com/kil1ua">Ken-Chy129</a> * @date 2023/1/8 16:44 */ public class 四数之和18 { public List<List<Integer>> fourSum(int[] nums, int target) { Arrays.sort(nums); List<List<Integer>> ans = new ArrayList<>(); for (int first=0; first<nums.length-3; first++) { if (first > 0 && nums[first] == nums[first-1]) { continue; } // 剪枝 // 接下来最小的四个数都大于目标值则结束 if ((long) nums[first] + nums[first + 1] + nums[first + 2] + nums[first + 3] > target) { break; } // 这一轮这个取值和最大的三个数相加都小于目标值，则这一轮这个数不可能找到满足的情况 if ((long) nums[first] + nums[nums.length - 3] + nums[nums.length - 2] + nums[nums.length - 1] < target) { continue; } for (int second=first+1; second<nums.length-2; second++) { if (second > first+1 && nums[second] == nums[second-1]) { continue; } // 同理剪枝 if ((long) nums[first] + nums[second] + nums[second + 1] + nums[second + 2] > target) { break; } if ((long) nums[first] + nums[second] + nums[nums.length - 2] + nums[nums.length - 1] < target) { continue; } long aim = (long)target-nums[first]-nums[second]; int fourth = nums.length-1; for (int third=second+1; third<nums.length-1; third++) { if (third > second+1 && nums[third] == nums[third-1]) { continue; } while (third < fourth && nums[third] + nums[fourth] > aim) { fourth--; } if (third == fourth) { break; } if (nums[third] + nums[fourth] == aim) { List<Integer> tmp = new ArrayList<>(); tmp.add(nums[first]); tmp.add(nums[second]); tmp.add(nums[third]); tmp.add(nums[fourth]); ans.add(tmp); } } } } return ans; } }
