代码随想录训练营Day7 | 四数相加&&赎金信&&三数之和&&四数之和&&哈希总结

454.四数相加II

文章：6. 四数相加II

题目：454. 四数相加 II

视频：学透哈希表，map使用有技巧！LeetCode：454.四数相加II_哔哩哔哩_bilibili

该题出现的元素数值有可能很大，不适合用数组作为解题 -> set \ map

要统计是否出现过，还需要存出现了多少次，且去重 -> 使用 map

key：两数组相加的值 | value： 数值出现了多少次

注意事项：用于返回计数的count 在遇到有符合题目要求的组合时应该 += value ！

• Java实现

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int res = 0;
        for(int i: nums1){
            for(int j : nums2){
                int sum = i+j;
                map.put(sum,map.getOrDefault(sum,0)+1);
            }
        }
        for(int i : nums3){
            for(int j : nums4){
                res += map.getOrDefault(0-i-j,0);
            }
        }
        return res;
    }
}

• Go实现

一开始增强for循环写错了，写成了for i := range nums1，这时的i其实遍历的是数组的下标，而不是数组值！

func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
    res := 0
    m := make(map[int]int)
    for _,i := range nums1{
        for _,j := range nums2{
            m[i+j]++
        }
    }
    for _,i:= range nums3{
        for _,j := range nums4{
            res += m[0-i-j]
        }
    }
    return res
}

---

383.赎金信

文章：7. 赎金信

题目：383. 赎金信

和有效的异位字符很像，不赘述噜。

• Java实现

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
//用数组
        int[]arr = new int[26];
        for(char c : magazine.toCharArray()){
            arr[c - 'a']++;
        }
        for(char c : ransomNote.toCharArray()){
            arr[c - 'a']--;
        }
        for(int i : arr){
            if(i <0)return false;
        }
        return true;
    }
}

• Go实现

两个语法问题：

​ 1、对数组初始化还不是很熟悉： make( []int , size)

​ 2、对增强for循环的 for 下标： 下标对应的值 := range 数组1

func canConstruct(ransomNote string, magazine string) bool {
    res :=make([]int,26)
    for _,i := range magazine{
        res[ i - 'a' ]++
    }
    for _,i := range ransomNote{
        res[ i - 'a']--
    }
    for _,i := range res{
        if i < 0 {
            return false
        }
    }
    return true
}

---

15.三数之和

文章：8. 三数之和

题目：15. 三数之和

视频：梦破碎的地方！| LeetCode：15.三数之和_哔哩哔哩_bilibili

【思路】

题目要求返回的三元组需要去重，所以这道题并不适合使用哈希表解决。因此我们采用双指针法进行解决。

使用

使用双指针法的要求为：数组必须是有序的。因此我们首先需要对数组进行排序。

值得注意的是，我们对数组排序完后，如果nums[i] > 0 的话，我们就可以直接return了：后续的值无论怎么加，大于零的数不会再比 0 小，因此不需要再计算后续的数值。

以及，我们需要对结果集提前进行去重，保证写入结果集的值不重复。这便涉及到我们判断到底是在nums[i] = nums[i-1] 的时候continue呢，还是在 num[i] = nums[i+1]的时候continue。我们应该选择在nums[i] = nums[i-1]的时候进行去重。比如[ -1 , -1 , 2 ]中，我们需要去重的是第二个-1。这样才不会造成数据的重复出现。

此外，在使用双指针的时候，需要注意while的边界值，到底是left <= right还是left < right。

去重的逻辑，一定要放在收获一个符合条件的结果下面，不然会导致当前结果无法写入结果集。

• Java实现

新了解到： res.add(Arrays.asList(nums[i],nums[left],nums[right]));能够直接添加一个List

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        //双指针法
        List<List<Integer>> res = new ArrayList<>();
      
        Arrays.sort(nums);
        for(int i = 0; i < nums.length ;i++){
            if(nums[i]>0)return res;
            if(i > 0 && nums[i] == nums[i-1]){ //去重a
                continue;
            }
            int left = i+1 ; //左指针要比 i 大
            int right = nums.length-1;
            while(left < right){
                int temp = nums[i] + nums[left]+nums[right];
                if(temp > 0){
                    right--;
                }else if(temp < 0){
                    left++;
                }else{
                    res.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    //去重bc
                    while(right > left && nums[right] == nums[right-1])right--;
                    while(right > left && nums[left] == nums[left+1])left++;
                    left++;
                    right--;
                }
            }
        }
        return res;

    }
}

• Go实现

再次熟悉了如何在切片中添加新的数据：res = append(res,[]int{nums[i],n2,n3})

func threeSum(nums []int) [][]int {
    //Go的排序
    sort.Ints(nums)
    res := [][]int{}
    //这里是需要-2的，避免数组越界，也就是计算到当 i 为倒数第三个数时的数组后停止循环。
    for i := 0 ; i <len(nums)-2;i++{
        if nums[i] > 0 {
            return res
        }
        if i > 0 && nums[i] == nums[i-1]{
            continue
        }
        left := i+1
        right := len(nums)-1
        for left < right{
            sum := nums[i] + nums[left]+nums[right]
            if sum == 0{
                n2,n3 := nums[left],nums[right]
                res = append(res,[]int{nums[i],n2,n3})
                for right > left && nums[right] == nums[right-1]{
                    right--
                }
                for right > left && nums[left] == nums[left+1]{
                    left++
                }
                left++
                right--
            }else if sum < 0{
                left++
            }else{
                right--
            }
        }
    }
    return res
}

---

9.四数之和

文章：9. 四数之和

题目：18. 四数之和

视频：难在去重和剪枝！| LeetCode：18. 四数之和_哔哩哔哩_bilibili

【思路】

大体的解题思路和上面的三数之和答案相似，就是在三数之和的答案的基础上在外面套一层for循环，达到四数之和。时间复杂度达到了O(n^3)。

有很多小小细节需要注意：

​ 剪枝和去重

​ 剪枝：不去循环最外层循环到的 nums[k] 大于 target 的值，但是要注意负数+负数会更小，nums[k] 一定要大于 0 && target 大于 0 。（数组已经排序过了）

​ 去重：将nums[i]和nums[i-1]进行比较。

• Java实现

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>>res = new ArrayList<>();
        Arrays.sort(nums);
        for(int i = 0 ; i < nums.length;i++){
            if(nums[i] >0 && nums[i]>target)return res;//剪枝
            if( i > 0 && nums[i] == nums[i-1])continue;//去重
            for(int j = i+1 ; j < nums.length ;j++){
                if(j > i + 1 && nums[j] == nums[j-1])continue;
                int left = j+1;
                int right = nums.length-1;
                while(right > left){
                    int n2 = nums[left];
                    int n3 = nums[right];
                    long sum = (long)(nums[i]+nums[j]+n2+n3);
                    if(sum >target)right--;
                    else if(sum < target) left++;
                    else{
                        res.add(Arrays.asList(nums[i],nums[j],n2,n3));
                        while(right > left && nums[right] == nums[right-1]){
                            right--;
                        }
                        while(right > left && nums[left] == nums[left+1]){
                            left++;
                        }
                        left++;
                        right--;
                    }    
                }
                
            }
           
        }
         return res;
    }
}

• Go实现

​ 注意for循环的边界条件！第一个循环的边界条件为len(nums)-3，第二个循环的边界条件为len(nums)-2，是为了避免数组越界&&只需要遍历到倒数第四个数值即可。

​ 再次熟悉了如何在切片中添加新的数据：res = append(res,[]int{nums[i],n2,n3})

func fourSum(nums []int, target int) [][]int {
    if len(nums) < 4 {
        return nil
    }
    sort.Ints(nums)
    var res [][]int
    for i := 0;i < len(nums)-3;i++{
        n1 := nums[i]
        if i>0 && nums[i] == nums[i-1]{
            continue
        }
        for j:=i+1;j<len(nums)-2;j++{
            n2 := nums[j]
            if j > i+1 && nums[j] == nums[j-1]{
                continue
            }
            left ,right := j+1,len(nums)-1
            for right > left{
                n3 := nums[left]
                n4 := nums[right]
                sum := n1+n2+n3+n4
                if(sum > target){
                    right--
                }else if(sum < target){
                    left++
                }else{
                    res = append(res,[]int{n1,n2,n3,n4})
                    for right > left && n3 == nums[left+1]{
                        left++
                    }
                    for right > left && n4 == nums[right-1]{
                        right--
                    }
                    left++
                    right--
                }
            }
        }
    }
    return res
}

---

哈希表总结

哈希表理论基础

一般来说，哈希表都是用来快速判断一个元素时候出现在集合里。

• 哈希函数

  哈希函数是把传入的key映射到符号表的索引上。

• 哈希碰撞

  哈希碰撞处理有多个key映射到相同索引上时的情景，处理碰撞的普遍方式是拉链法和线性探测法。

• 常见的三种哈希结构

  • 数组
  • set（集合）
  • map（映射）

---

经典题目

数组作为哈希表

适合用到数据量较小且数据是连续和有限的的

在242.有效的字母异位词 (opens new window)中，我们提到了数组就是简单的哈希表，但是数组的大小是受限的！

这道题目包含小写字母，那么使用数组来做哈希最合适不过。

在383.赎金信 (opens new window)中同样要求只有小写字母，那么就给我们浓浓的暗示，用数组！

本题和242.有效的字母异位词 (opens new window)很像，242.有效的字母异位词 (opens new window)是求 字符串a 和 字符串b 是否可以相互组成，在383.赎金信 (opens new window)中是求字符串a能否组成字符串b，而不用管字符串b 能不能组成字符串a。

一些同学可能想，用数组干啥，都用map不就完事了。

上面两道题目用map确实可以，但使用map的空间消耗要比数组大一些，因为map要维护红黑树或者符号表，而且还要做哈希函数的运算。所以数组更加简单直接有效！

set作为哈希表

在349. 两个数组的交集 (opens new window)中我们给出了什么时候用数组就不行了，需要用set。

这道题目没有限制数值的大小，就无法使用数组来做哈希表了。

主要因为如下两点：

• 数组的大小是有限的，受到系统栈空间（不是数据结构的栈）的限制。
• 如果数组空间够大，但哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。

所以此时一样的做映射的话，就可以使用set了。

在202.快乐数 (opens new window)中，我们再次使用了unordered_set来判断一个数是否重复出现过。

map作为哈希表

在1.两数之和 (opens new window)中map正式登场。

来说一说：使用数组和set来做哈希法的局限。

• 数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
• set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。

map是一种<key, value>的结构，本题可以用key保存数值，用value在保存数值所在的下标。所以使用map最为合适。

同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解），1.两数之和 (opens new window)中并不需要key有序，选择std::unordered_map 效率更高！

在454.四数相加 (opens new window)中我们提到了其实需要哈希的地方都能找到map的身影。

本题咋眼一看好像和18. 四数之和 (opens new window)，15.三数之和 (opens new window)差不多，其实差很多！

关键差别是本题为四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑重复问题，而18. 四数之和 (opens new window)，15.三数之和 (opens new window)是一个数组（集合）里找到和为0的组合，可就难很多了！

用哈希法解决了两数之和，很多同学会感觉用哈希法也可以解决三数之和，四数之和。

其实是可以解决，但是非常麻烦，需要去重导致代码效率很低。

在15.三数之和 (opens new window)中我给出了哈希法和双指针两个解法，大家就可以体会到，使用哈希法还是比较麻烦的。

所以18. 四数之和，15.三数之和都推荐使用双指针法！

哈希章总结

本篇我们从哈希表的理论基础到数组、set和map的经典应用，把哈希表的整个全貌完整的呈现给大家。

同时也强调虽然map是万能的，详细介绍了什么时候用数组，什么时候用set。

【算法总结】

• 四数相加II需要返回四数相加和的值与出现的次数&&需要去重，因此我们使用了**map**进行存储。
• 赎金信需要对字符进行统计计数，因此我们使用了数组。
• 三数之和需要返回三数相加等于target的次数&&需要去重，因此我们使用了双指针法，需要注意for循环的边界条件！
• 四数之和需要返回四数相加等于target的次数&&需要去重，因此我们使用了双指针法配合剪枝、去重，需要注意for循环的边界条件！

【语法总结】

• Java

 在list中插入一个new List元素：`res.add( Arrays.asList( nums[i], nums[left], nums[right] ));`

• Golang

​ 增强型for循环：for index,value := range arr

​ 数组初始化：arr := []int/arr := make([]int,size)

​ 在切片末尾添加元素：res = append(res,[]int{n1,n2,n3,n4})