此教程参考 代码随想录-哈希表篇
感谢支持！

哈希表 Hash Table

代码随想录-总汇 中包含哈希表的基础知识

题目

242. 有效的字母异位词

1
2
3
4
5
6
7
8
9
10
11
12
public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    int[] alpha = new int[26];
    for(int i = 0; i< s.length(); i++) {
        alpha[s.charAt(i) - 'a'] ++;
        alpha[t.charAt(i) - 'a'] --;
    }
    for(int i=0;i<26;i++)
        if(alpha[i] != 0)
            return false;
    return true;
}

349. 两个数组的交集

没有什么难点，但是有个用法可以学一下: Java 的 stream： 把set中的值变成array:

1
int[] res = resSet.stream().mapToInt(x -> x).toArray();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int[] intersection(int[] nums1, int[] nums2) {
      Set<Integer> resSet = new HashSet<>();
      Set<Integer> numSet = new HashSet<>();
      for (int i : nums1) {
          numSet.add(i);
      }
      for (int i : nums2) {
          if (numSet.contains(i)) {
              resSet.add(i);
          }
      }
      int[] res = resSet.stream().mapToInt(x -> x).toArray();
      return res;
  }

202. 快乐数

这道题主要在于识别题干中的 无限循环， 即会出现sum重复出现的情况 于是题目就变成：如何快速查找sum是否已经出现过，即哈希应用题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean isHappy(int n) {
    // 由于可能出现 无限循环 即会出现sum重复出现的情况
    // 于是题目就变成：如何快速查找sum是否已经出现过，即哈希应用题；
    Set<Integer> sumSet = new HashSet<>();
    int sum = 0;
    int nCopy = n;
    while (!sumSet.contains(sum)) {
        int newN = nCopy;
        sumSet.add(sum);
        sum = 0;
        while (newN > 0) {
            sum += (newN % 10) * (newN % 10);
            newN /= 10;
        }
        nCopy = sum;
        if (sum == 1) return true;
    }
    return false;
}

1. 两数之和

缅怀我逝去的青春 😋

1
2
3
4
5
6
7
8
9
10
11
12
13
public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> val2Idx = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int cur = nums[i];
        int needNum = target - cur;
        if (val2Idx.containsKey(needNum)) {
            return new int[] {val2Idx.get(needNum), i};
        } else {
            val2Idx.put(nums[i], i);
        }
    }
    return new int[] {-1, -1};
}

454. 四数相加 II

首先非常丑的暴力做法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private int brutalForce(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
    // 非常丑的 暴力： 200^4 = over 10^8 超时
    int count = 0;
    for (int i = 0; i < nums1.length; i++) {
        for (int j = 0; j < nums2.length; j++) {
            for (int k = 0; k < nums3.length; k++) {
                for (int l = 0; l < nums4.length; l++) {
                    if (nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0) count++;
                }
            }
        }
    }
    return count;
}

可以考虑用时间换空间，借用两数之和的思想我们可以想到哈希表：

使用哈希表来优化至 O(N^2) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
  // 哈希表两两分组：
  // nums1 nums2 一组 的所有可能出现的和 存入哈希表
  // nums3 nums4 一组 在哈希表找可能出现的 -(的所有可能出现的和)
  // 哈希可以使其优化到 O(N^2)
  Map<Integer, Integer> sum2Count = new HashMap<>();
  for (int i = 0; i < nums1.length; i++) {
      for (int j = 0; j < nums2.length; j++) {
          int sum = nums1[i] + nums2[j];
          sum2Count.put(sum, sum2Count.getOrDefault(sum, 0) + 1);
      }
  }

  int count = 0;
  for (int k = 0; k < nums3.length; k++) {
      for (int l = 0; l < nums4.length; l++) {
          int sum = nums3[k] + nums4[l];
          if (sum2Count.containsKey(-sum)) {
              count += sum2Count.get(-sum);
          }
      }
  }
  return count;
}

383. 赎金信

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean canConstruct(String ransomNote, String magazine) {
      int[] hm = new int[26];
      for (char r : ransomNote.toCharArray()) {
          int pos = r - 'a';
          hm[pos] += 1;
      }

      for (char m : magazine.toCharArray()) {
          int pos = m - 'a';
          hm[pos] -= 1;
      }

      for (int j : hm) {
          if (j > 0) return false;
      }
      return true;
  }

15. 三数之和

写做三数之和但是用哈希表来做会非常麻烦由于涉及到去重的操作。因此双指针会简便许多。具体流程如下：

三数之和过程

另外一些关于去重问题的考虑：

我们有三个数需要去重 nums[i] nums[left] nums[right]：

  1. i 的去重
    1. 在 i 入口处就可以跳过：那么问题是我们应该用 nums[i] == nums[i + 1] 还是 nums[i] == nums[i - 1]
      1. 答案是用 nums[i] == nums[i - 1]
      2. 考虑用{-1, -1 ,2} 这组数据，如果用nums[i] == nums[i + 1] 当遍历到第一个-1 的时候，判断 下一个也是-1，那这组数据就pass了。
  2. nums[left] nums[right] 的 去重：
    1. 见代码 4. 处
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++) { // 1. Change the loop condition
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1, right = nums.length - 1;
            int num = nums[i];
            int needNum = -num;

            while (left < right) {
                int currentSum = nums[left] + nums[right]; // 2. Calculate the current sum
                if (currentSum < needNum) {
                    left++;
                } else if (currentSum > needNum) {
                    right--;
                } else {
                    List<Integer> temp = new ArrayList<>(Arrays.asList(
                            nums[i], nums[left], nums[right] // 3. Use nums[i], nums[left], nums[right] instead of i, left, right
                    ));
                    res.add(temp);

                    // 4. Handle duplicates for left and right pointers
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;

                    // 5. Move left and right pointers inward
                    left++;
                    right--;
                }
            }
        }
        return res;
    }

18. 四数之和

本质上还是三数之和即排序加双指针但是有两个地方需要注意一下看下面的代码块：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public List<List<Integer>> fourSum(int[] nums, int target) {
      Arrays.sort(nums);
      List<List<Integer>> res = new ArrayList<>();
      for (int i = 0; i < nums.length - 3; i++) {
          if (i > 0 && nums[i] == nums[i - 1]) continue;
          for (int j = i + 1; j < nums.length - 2; j++) {
              // 注意这里是 j > i + 1 不能直接 j > 0 否则 case 例如 [2, 2, 2, 2, 2] 会返回空 （毕竟看到2就都过去了）
              if (j > i + 1 && nums[j] == nums[j - 1]) continue;
              int left = j + 1, right = nums.length - 1;
              // 注意边界，需要用long for case：
              // [1000000000,1000000000,1000000000,1000000000] -294967296
              long sumIJ = nums[i] + nums[j];
              long needSum = target - sumIJ;
              while (left < right) {
                  long curSum = nums[left] + nums[right];
                  if (curSum < needSum) {
                      left++;
                  } else if (curSum > needSum) {
                      right--;
                  } else {
                      List<Integer> temp = new ArrayList<>(
                              Arrays.asList(nums[i], nums[j], nums[left], nums[right])
                      );
                      res.add(temp);

                      while (left < right && nums[left] == nums[left + 1]) left++;
                      while (left < right && nums[right] == nums[right - 1]) right--;

                      left++;
                      right--;
                  }
              }
          }
      }
      return res;
  }