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

旧城等待， 2024-03-31 05:04 72阅读 0赞

#### 文章目录 ####

*   *  一、四数相加II
     *   *  思路
         *  注意
         *  AC代码
     *  二、赎金信
     *   *  思路
         *  AC代码
     *  三、三数之和
     *   *  思路
         *  AC代码
     *  四、四数之和
     *   *  思路
         *  AC代码
     *  五、总结

### 一、四数相加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.  由于可能出现的字符都是小写英文字母，对应的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.  由于题目返回值限定，这里我们无法使用map/set，如果硬要使用效率反而降低了。
2.  我们首先对数组进行排序
3.  我们仍然使用遍历的思想，同时加入双指针left、right，固定开始的一个数字，left始终等于i+1,right始终等于nums.length-1.两个指针**向中靠拢**（移动分为三种情况，当前大于0，当前小于0，当前满足），满足结果就收集，循环终止条件不能是left<=right，而是left<right，毕竟题目要求结果集中的数必须对应的不同下标的数。
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.  本题仍然延续三数之和的双指针思想，只需要在上边的循环外边再嵌套一个循环就可以，相当于固定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.  哈希常用结构
    
     *  数组
     *  map
     *  set