Leetcode每日一题 ——n数之和

两数之和
LCR 179. 查找总价格为目标值的两个商品 - 力扣（LeetCode）
三数之和
15. 三数之和 - 力扣（LeetCode）
四数之和
18. 四数之和 - 力扣（LeetCode）
思路
1.这三个求几数之和的算法的实现思路均用到了双指针和单调性的思想
2.两数之和直接设置两个指针，分出来三种情况，当两数之和大于目标值的时候，右指针左移，当两数之和小于目标值的时候，左指针右移，剩下的情况是相等的时候，因为这个两数之和的题目是要求找到一组解就可以退出，所以等于目标值的时候就直接返回
3.三数之和这个题，延续了两数之和的解决思想，先定下来一个数，在分别让左右指针移动去找到相等的值，此题要求返回所有符合条件的结果，并且去重，涉及到的分支情况的逻辑和两数之和完全一致，此处主要讲如何去重，因为嵌套了一层，所以这边需要进行两次去重，一次是在双指针的部分，当左右指针遇到重复值的时候进行去重，一个是固定的数字的去重，这样下来就可以做到不重不漏
4.四数之和和前两个的处理分支的逻辑完全一致，特殊的是在处理重复的结果的时候要多加一步去重，因为这个的思想是延续了两数之和和三数之和，先固定一个数a，在固定一个数b，设计一个新的tar等于所给tar进行做差，得到新的tar，本质上就是把四数之和进行拆解成求两数之和，除了三数之和的两步去重，还涉及到数a的去重，在此题中加了一些必要的剪枝的优化
代码
（1）两数之和

    public int[] twoSum(int[] price, int target) {
        int left=0,right=price.length-1;
        while(left<right){
            if(price[left]+price[right] < target){
               left++;
            }else if(price[left]+price[right] > target){
                right--;
            }else {
                return new int[]{price[left],price[right]};
            }
        }
        return new int[]{0};
    }

（2）三数之和

 public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret=new ArrayList<>();
        //排序优化
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            //优化二 正数相加不可能为0
            if(nums[i]>0){
                break;
            }
            int left=i+1,right=nums.length-1;
            //去重二
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            while(left<right){
                int sum=nums[left]+nums[right];
                if(sum< Math.abs(nums[i])){
                    left++;
                }else if(sum>Math.abs(nums[i])){
                    right--;
                }else {
                    ret.add(new ArrayList<>(List.of(nums[left],nums[right],nums[i])));
                    //去重一
                    while(left<right&&nums[left]==nums[left+1]){
                        left++;
                    }
                    while(left<right&&nums[right]==nums[right-1]){
                        right--;
                    }
                    left++;
                    right--;
                }
            }
        }
        return ret;
    }

（3）四数之和

    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ret=new ArrayList<>();

        Arrays.sort(nums);
        for (int i = 0; i < nums.length-3; i++) {
            //三数之和
            //去重三
            if(i>0 && nums[i]==nums[i-1])continue;
            // 剪枝1：最小四个数的和都大于target，后面更大，直接break
            long min1 = (long) nums[i] + nums[i+1] + nums[i+2] + nums[i+3];
            if (min1 > target) break;

            // 剪枝2：当前最大和都小于target，跳过本轮循环
            long max1 = (long) nums[i] + nums[nums.length-1] + nums[nums.length-2] + nums[nums.length-3];
            if (max1 < target) continue;
            for (int j = i+1; j < nums.length-2; j++) {
                //双指针求解
                //去重二
                if (j > i+1 && nums[j] == nums[j - 1]) continue;
                // 剪枝3：当前固定i,j后的最小和大于target
                long min2 = (long) nums[i] + nums[j] + nums[j+1] + nums[j+2];
                if (min2 > target) break;

                // 剪枝4：当前固定i,j后的最大和小于target
                long max2 = (long) nums[i] + nums[j] + nums[nums.length-1] + nums[nums.length-2];
                if (max2 < target) continue;

                long tar=(long)target-(long)nums[i]-(long)nums[j];
                int left = j + 1, right = nums.length - 1;
                while (left<right) {
                    long sum = (long) nums[left] + (long) nums[right];
                    if (sum < tar) {
                        left++;
                    } else if (sum > tar) {
                        right--;
                    } else {
                        ret.add(new ArrayList<>(List.of(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 ret;
    }

1 个帖子 - 1 位参与者

阅读完整话题