跟练代码随想录之哈希表篇

写在前面，这个系列是跟着B站的代码随想录跟练算法的部分。算法还是比较薄弱，慢慢打基础吧，这篇文章很久以前就写好了，只是发布的时间比较晚了，最近也是打算迁移一下自己的文章。

友链到卡哥

https://www.programmercarl.com/

1.有效的字母异位词（leetocde242）

有效的字母异位词，就是两个字符串是由相同个数的字母组成的，比如abbc和bbac。这题一看就是用哈希来做。

一般的哈希结构我们有三种，用哈希数组、哈希set、哈希map来做。

个数小的时候可以用数组，大的时候可以用set，有明确k-v值的话可以用map。

这里我们可以用最简单的数组来做。

image-20240407203212200

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//这个是用哈希数组来做：O（n）的复杂度：
class Solution {
    public boolean isAnagram(String s, String t) {
        int[] hash = new int[26];
        if (s.length()!=t.length()) return false;
        for(int i=0;i<s.length();i++){
            hash[s.charAt(i)-'a']++;
            hash[t.charAt(i)-'a']--;
        }
        for(int i=0;i<hash.length;i++){
            if (hash[i]!=0) return false;
        }
        return true;
    }
}

2.两个数组的交集（leetocde349）

什么时候要用哈希表呢。比如一个什么什么判断是否出现过，这种就是用哈希表。

然后为什么不用数组呢，因为比如像0，5，20000，这样就要开很大的数组，如果元素比较集中且较小就可以用数组。

image-20240407203242297

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

3.两数之和（leetcode1）

这题要判断每个元素是否之前出现过。所以其实还是比较简单的，时间复杂度O(n)就够了。

image-20240407203304121

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] retArr = new int[2];
        Map<Integer,Integer> Map = new HashMap<>();
        for(int i=0;i<nums.length;i++){
            int p = target-nums[i];
            if (Map.containsKey(p)){
                retArr[0] = Map.get(p);
                retArr[1] = i;
                return retArr;
            }
            Map.put(nums[i],i);
        }
        return new int[0];
    }
}
//用HashMap就可以了。

4.四数相加II（leetcode454）

哈希表里比较经典的题目。

先循环nums1和nums2，保存a+b的值到map中，然后循环后两个数组的值，获取数组和，去判断map中是否有相反数，有的话就让value+1，其实还是很好理解的，这个过程。

image-20240407203324989

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer,Integer> map = new HashMap<>();
        int result = 0;
        for(int i:nums1){
            for(int j:nums2){
                map.put((i+j),map.getOrDefault((i+j),0)+1);
            }
        }
        for(int i:nums3){
            for(int j : nums4){
                result+=map.getOrDefault((0-i-j),0);
            }
        }
        return result;
    }
}

5.三数之和（leetcode15）

这题我感觉真的还是蛮难的，看了这么多题。哈希的思路很好想，跟上面那题挺像，但是难在去重；

然后好做的方法是双指针，但是也难在去重，这个去重的逻辑真的不好想。

​ 0

注意看我的注释，有很多细节要注意，要考虑好多种测试用例和边界情况：

比如 -1 -1 -1 -1 1 1 1 1 1，这种如何去重；

比如 0 0 0 00 0 0 这种对于i而言如何去重；

比如要先保存结果再去移动去重

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
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);
        for(int i=0;i<nums.length;i++){
            if (nums[i]>0) return list;
            //对i去重
            //细节下面这个逻辑在000的样例中会下标越界
            //while(i>=1&&nums[i]==nums[i-1]) i++; //说明i之前已经被加过了
            //得改成这样：
            if (i>=1&&nums[i]==nums[i-1]) continue;
            int left = i+1;
            int right = nums.length-1;
            //细节不能等于，不然就是同一个数字了
            while(left<right){
                if (nums[i]+nums[left]+nums[right]>0) right--;
                else if(nums[i]+nums[left]+nums[right]<0) left++;
                else{
                    //先保存结果
                    List<Integer> retList = new ArrayList<>();
                    retList.add(nums[i]);
                    retList.add(nums[left]);
                    retList.add(nums[right]);
                    list.add(retList);
                    //对left和right去重
                    while(left<right&&nums[right]==nums[right-1]) right--;
                    while(left<right&&nums[left]==nums[left+1]) left++;
                    //细节，最后还要移动
                    right--;
                    left++;
                }
            }
        }
        return list;
    }
}

6.四数之和（leetcode18）

这题是在三数之和的上面演进的，考虑的细节还是比较多的，注意的是target可能小于0！！！

所以我们这里一个是剪枝如何剪枝，我考虑 了nums[i]>target，我认为这个还是比较正确的，卡尔没讲到；

然后就是去重的操作，注意我的注释细节；

有个用法可以学学，怎么把一组数转为list，用到Arrays.asList()

​ 0

把第一层结束之后，后面的步骤就跟三数之和是一样的了。

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
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        //两级剪枝，两级去重
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        //一级
        for(int i=0;i<nums.length;i++){
            //真正的剪枝
            if (nums[i]>target/4) break;
            //一级去重，思路是一样的，只记录i第一次当-2的情况
            if (i>=1&&nums[i]==nums[i-1]) continue;
            for (int j=i+1;j<nums.length;j++){
                int sum = target-nums[i];
                //这个剪枝可能不是最优的
                //if (nums[i]+nums[j]>target) break;
                //二番目，这里想的太简单了，不能这样剪枝，对于负数的target不适用
                if (j>i+1&&nums[j]==nums[j-1]) continue;
                int left = j+1;
                int right = nums.length-1;
                while(left<right){
                    if (nums[j]+nums[left]+nums[right]>sum) right--;
                    else if (nums[j]+nums[left]+nums[right]<sum) left++;
                    else {
                        //先保存再去重
                        result.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        while(left<right&&nums[right]==nums[right-1]) right--;
                        while(left<right&&nums[left]==nums[left+1]) left++;
                        right--;
                        left++;
                    }
                }
            }
        }
        return result;
    }
}