# Leetcode刷题day7|454.四数相加II, 383. 赎金信,15. 三数之和 ,18四数之和

一、四数相加II

思路

1. 不难想到，本题可以使用暴力解法，直接四个for循环嵌套。如果和为0，ret++。不过这里需要注意四个for循环的取值范围。
2. 但是上边这种解法的时间复杂度是O(n^4)，为了降低时间复杂度，我们回想哈希的用法
3. 属于在一个集合中快速查找指定元素组合问题，通过转换可以转化成寻找指定元素问题。因此可以使用哈希。
4. 分析可以知道，不属于使用数组的情况，又因为涉及计算组合的个数，涉及到排列组合，同一个值可以对应不同中组合，因此我们这里使用map，方便结果集个数的统计。
5. 怎么转化？？可以两两分组，先两个for循环把一组的和放进map中，得到的结果一定是相异的。
6. 然后再for循环嵌套，遍历另一组，怎么遍历？？用0-前一组的和，然后再map中寻找这个值，如果存在，就像ret中加入这组数的value值。

注意

1. map的getOrdefault方法和put方法的配套使用

AC代码

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

二、赎金信

思路

1. 属于在集合中快速查找问题，使用哈希
2. 由于可能出现的字符都是小写英文字母，对应的ASCII码比较集中，因此，这里我们这里使用数组作为哈希结构
3. 数组大小为26，遍历第一个字符串，对应索引全部赋值
4. 遍历第二个字符串，判断存不存在，如果存在对应数值–，不存在直接返回false
5. 如果全部遍历完，都没有返回false，那么返回true

AC代码

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] hash=new int[26];
        for(int i=0;i<magazine.length();i++){
            char ch=magazine.charAt(i);
            hash[ch-'a']++;
        }
        for(int i=0;i<ransomNote.length();i++){
            char ch=ransomNote.charAt(i);
            if(hash[ch-'a']>0){
                hash[ch-'a']--;
            }else{
                return false;
            }
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

三、三数之和

思路

1. 由于题目返回值限定，这里我们无法使用map/set，如果硬要使用效率反而降低了。
2. 我们首先对数组进行排序
3. 我们仍然使用遍历的思想，同时加入双指针left、right，固定开始的一个数字，left始终等于i+1,right始终等于nums.length-1.两个指针向中靠拢（移动分为三种情况，当前大于0，当前小于0，当前满足），满足结果就收集，循环终止条件不能是left<=right，而是left
4. 因为题目要求不能是重复的三元组，所以我们需要进行去重，比如对于数组[-1,0,0,0,1,1]，判断条件是nums[right]==nums[right-1],对应的还有nums[left]==nums[left+1]
5. 同时，如果i对应的数字已经大于0，那么往后边必然没有符合要求的结果集。这时我们加入一个判断条件nums[i]>0直接返回结果集。这也就是我们说的剪枝。

AC代码

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret=new ArrayList<>();
        Arrays.sort(nums);
        for(int i=0;i<nums.length;i++){
            if(nums[i]>0){
                return ret;
            }
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            int left=i+1;
            int right=nums.length-1;
            while(left<right){
                List<Integer> list=new ArrayList<>();
                int sum=nums[i]+nums[left]+nums[right];
                if(sum>0){
                    right--;
                }else if(sum<0){
                    left++;
                }else{
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    ret.add(list);
                    while(left<right&&nums[right]==nums[right-1]){
                        right--;
                    }
                    while(left<right&&nums[left]==nums[left+1]){
                        left++;
                    }
                    right--;
                    left++;
                }
            }
        }
        return ret;
    }
}
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
37
38
39

四、四数之和

思路

1. 本题仍然延续三数之和的双指针思想，只需要在上边的循环外边再嵌套一个循环就可以，相当于固定k和i两个进行寻找。在此基础上，对里边的代码做一些细节的处理
2. 但是有以下几点需要注意
   • i的范围：k+1到nums.length
   • k的去重和剪枝与原来的i的去重剪枝相似，如果需要剪枝，直接返回结果集
   • i的去重和剪枝需要改变，如果需要剪枝，不能直接返回结果集……
   • 需要考虑四数之和相加溢出的情况——对应解决方案（强转）

AC代码

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ret=new ArrayList<>();
        Arrays.sort(nums);
        for(int k=0;k<nums.length;k++){
            if(nums[k]>target&&target>0){
                return ret;
            }
            if(k>0&&nums[k]==nums[k-1]){
                continue;
            }
            for(int i=k+1;i<nums.length;i++){
                if(nums[i]+nums[k]>target&&target>0){
                    //return ret;
                    break;
                }
                if(i>k+1&&nums[i]==nums[i-1]){
                    continue;
                }
                int left=i+1;
                int right=nums.length-1;
                while(left<right){
                    List<Integer> list=new ArrayList<>();
                    long sum=(long)nums[k]+nums[i]+nums[left]+nums[right];
                    //int sum=nums[k]+nums[i]+nums[left]+nums[right];
                    if(sum>target){
                        right--;
                    }else if(sum<target){
                        left++;
                    }else{
                        list.add(nums[k]);
                        list.add(nums[i]);
                        list.add(nums[left]);
                        list.add(nums[right]);
                        ret.add(list);
                        while(left<right&&nums[right]==nums[right-1]){
                            right--;
                        }
                        while(left<right&&nums[left]==nums[left+1]){
                            left++;
                        }
                        right--;
                        left++;
                    }
                }
            }
        }
        return ret;
    }
}
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50

五、总结

1. 使用哈希的情景：在集合中快速查找元素（是否存在或者值）
2. 哈希常用结构
   • 数组
   • map
   • set