代码随想录算法训练营第7天 | 454. 四数相加 II ，383. 赎金信 ，15. 三数之和 ，18. 四数之和

哈希知识基础

文章链接：https://programmercarl.com/%E5%93%88%E5%B8%8C%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html#%E5%93%88%E5%B8%8C%E8%A1%A8

454. 四数相加 II

题目链接：https://leetcode.cn/problems/4sum-ii/description/

思路:哈希法

这道题目是四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况。
他这里不用考虑重复的情况，同时也只要求多少个，不用求下标，用哈希法很快。
我们的思路就是对数组1和数组2的所有可能的相加结果，加到hashmap里，因为map里可以存key跟value，value就是出现的次数。因为假如出现了3次的话，后面加是要3次的。然后再把num3和num4所有可能的相加结果挨个的遍历一遍，再通过map去查找有没有对应的value，如果有的话就直接相加。

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

        int result = 0;
          for(int i:nums3){
            for(int j:nums4){
                result += map.getOrDefault(0-i-j,0);
            }
        }
        return result;
    }
}

时间复杂度 O(n^2)
空间复杂度 O(n^2)

383. 赎金信

题目连接：https://leetcode.cn/problems/ransom-note/description/

解法：哈希法

这题很简单，用一个简单的数组做哈希映射就可以解决。

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[]arr = new int[26];
        for(char ch:magazine.toCharArray()){
            arr[ch-'a'] += 1;
        }

        for(char ch:ransomNote.toCharArray()){
            arr[ch-'a'] -= 1;
        }

        for(int i:arr){
            if(i<0)
                return false;
        }
        return true;
    }
}

时间复杂度 O(n)
空间复杂度 O(1)

15. 三数之和

题目连接：https://leetcode.cn/problems/3sum/description/

解法：双指针法

以nums数组来举例，首先将数组排序，（排序可以方便我们之后比较是否有重复的数值）然后有一层for循环，i从下标0的地方开始，for循环中 i指向的是第一个数字，同时定义一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。

依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i]，b = nums[left]，c = nums[right]。

接下来如何移动left 和right呢， 如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。

如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。

同时，a，b，c的去重这里也是需要注意的地方
a的去重，不能是nums[i] == nums[i+1] ，这样1,1,2 这样的情况，这组数据就直接被pass掉了，我们正确的理解应该是出现和之前相同的数字时再去重。（记得加上i>0 ，否则index可能会报错）
然后b跟c的去重也是，找到了我们要求的解时，也要在他的附近看看是否还有同样的值，给他去重了

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>>ans = new ArrayList<>();
        Arrays.sort(nums);
        for(int i=0;i<nums.length;i++){
            int left = i+1;
            int right = nums.length - 1;
            // 剪枝,如果第一个数就大于0，说明怎么组合都不可能满足条件了
            if(nums[i]>0)
                return ans;

            // 对a去重
            if(i>0 && nums[i]==nums[i-1])
                continue;

            // 双指针法
            while(left < right){
                int sum = nums[i] + nums[left] + nums[right];
                if(sum>0){
                    right --;
                } 
                else if(sum<0)
                    left++;
                else{
                    // 找到一个解
                    ans.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    // 找到后不等于说其他情况不存在了，比如0+8,后面还有3+5
                    // 对相同的b跟c要进行去重
                    // !! right>left也要加上，防止后面的值都是一样的，然后left报了index错误
                    while(right>left && nums[left]==nums[left+1]) left++;
                    while(right>left && nums[right]==nums[right-1])  right--;
                    left++;
                    right--;
                }
            }
            
        }
        return ans;
    }
}

时间复杂度：O(n^2)

解法2：哈希法（不推荐用）

两层for循环就可以确定 a 和b 的数值了，可以使用哈希法来确定 0-(a+b) 是否在 数组里出现过，其实这个思路是正确的，但是我们有一个非常棘手的问题，就是题目中说的不可以包含重复的三元组。
去重的过程不好处理，有很多小细节，很难想到位。

时间复杂度可以做到O(n^2)，但还是比较费时的，因为不好做剪枝操作。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>>ans = new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            if(nums[i]>0)   // 剪枝
                break;
            
            // 三元组a去重
            if(i>0 && nums[i] == nums[i-1])
                continue;
            
            Set<Integer>set = new HashSet<>();
            for(int j=i+1; j<nums.length;j++){
                // 三元组b去重
                // 检查当前的b和前一个b是否相同，如果相同，则跳过当前的b
                // 如果只写nums[j]=nums[j-1]，就会出现把a也算进去的情况 [-1,-1,0,2...]

                // if(nums[j]==nums[j-1])
                //     continue;

                // j>2 也不行，j一定要在i的后面三位开始判断 
                // [0,0,0],[0,0,0,1],[0,0,0,0]
                if(j>i+2 && nums[j]==nums[j-1] && nums[j-1]==nums[j-2])
                    continue;
                int c = 0-(nums[i]+nums[j]);
                if(set.contains(c)){
                    ans.add(Arrays.asList(nums[i],nums[j],c));
                    set.remove(c);
                }else
                    set.add(nums[j]);
                    
            }
           

        }
         return ans;
    }
}

18. 四数之和

题目连接：https://leetcode.cn/problems/4sum/

解法：双指针法

和上一题十分的类似，只不过从3个数变成了4个数之和，和15.三数之和 是一个思路，都是使用双指针法, 基本解法就是在上一题基础上再套一层for循环。
但是有一些细节需要注意，例如： 不要判断nums[k] > target 就返回了，三数之和 可以通过 nums[i] > 0 就返回了，因为 0 已经是确定的数了，四数之和这道题目 target是任意值。比如：数组是[-4, -3, -2, -1]，target是-10，不能因为-4 > -10而跳过。但是我们依旧可以去做剪枝，逻辑变成nums[i] > target && (nums[i] >=0 || target >= 0)就可以了。

三数之和的双指针解法是一层for循环num[i]为确定值，然后循环内有left和right下标作为双指针，找到nums[i] + nums[left] + nums[right] == 0。

四数之和的双指针解法是两层for循环nums[k] + nums[i]为确定值，依然是循环内有left和right下标作为双指针，找出nums[k] + nums[i] + nums[left] + nums[right] == target的情况，三数之和的时间复杂度是O(n2)，四数之和的时间复杂度是O(n^3) 。

那么一样的道理，五数之和、六数之和等等都采用这种解法。

对于15.三数之和 (opens new window)双指针法就是将原本暴力O(n3)的解法，降为O(n2)的解法，四数之和的双指针解法就是将原本暴力O(n4)的解法，降为O(n^3)的解法。

同时，注意一下这里的四个数相加可能会超过int范围，最后结果转成long，防止爆了。

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>>ans = new ArrayList<>();
        Arrays.sort(nums);
        for(int i=0;i<nums.length;i++){
            // 可能有负数的话，就要加上nums[i]>0
            if(nums[i] >0 && nums[i]>target)
                break;
            if(i>0 && nums[i]==nums[i-1])
                continue;
            for(int j=i+1;j<nums.length;j++){
                // 对b去重 
                if(j>i+1 && nums[j]==nums[j-1])
                    continue;
                
                int left = j+1;
                int right = nums.length-1;
                while(left < right){
                    // 相加可能会溢出
                    long sum = (long)nums[i] + nums[j] + nums[left] + nums[right];
                    if(sum>target)
                        right --;
                    else if(sum<target)
                        left++;
                    else{
                        ans.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        while(left < right && nums[left] == nums[left+1])   left++;
                        while(left < right && nums[right] == nums[right-1]) right--;
                        left++;
                        right--;
                    }
                }

            }
            
        }
        return ans;
    }
}

时间复杂度：O(n^3)
空间复杂度：O(1)

写在最后

双指针法的使用是有条件的，如果是要返回索引下标，就不能用。因为双指针法一定是要先排序，一旦排序之后原数组的索引就被改变了。
如果要求返回的是数值的话，就可以使用双指针法了。
比如，我们这里所说的三数之和可以使用双指针法，但我们昨天写的1.两数之和，要求返回的是索引下标，就不能使用双指针法了。