No.15&16&18 三数之和四数之和双指针

题目列表

No.15 三数之和
No.16 最接近的三数之和
No. 18 四数之和

15 三数之和

题目大意

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

分析

第一个思路，先排序，然后两重循环后+二分查找。超时。
第二个思路，先排序，固定nums[i],然后用双指针，找满足-nums[i] == nums[low] + nums[high]的元素，并要注意去重！

代码一

首先来看下第一版写的二分查找。

public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for(int i=0;i<nums.length-2;i++) {
            if(nums[i]>0) break;
            for(int j=i+1;j<nums.length-1;j++)
            {
                if(nums[i] + nums[j] > 0) break;
                int index = search(nums,j+1,nums.length-1,-nums[i]-nums[j]);
                if(index!=-1) {
                    List<Integer> list = new ArrayList<>(Arrays.asList(nums[i],nums[j],nums[index]));
                    if(!res.contains(list))
                        res.add(list);
                } 
            }
        }
        return res;
    }

 private int search(int[] nums, int low, int high, int target) {
        while(low < high) {
            int mid = (low + high) >> 1;
            if(nums[mid] == target) return mid;
            else if(nums[mid] < target) low = mid + 1;
            else high = mid - 1;
        }
        return nums[low] == target? low:-1;
    }

代码二

双指针。去重的关键在于排序后相同的元素一定相邻。

public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for(int i=0;i<nums.length-2;i++) {
            if(nums[i] > 0) break;
            if(i>0 && nums[i] == nums[i-1]) continue;
            int low = i+1, high = nums.length-1;
            while(low < high) {
                if(nums[low]+nums[high] == -nums[i]) {
                    res.add(Arrays.asList(nums[i],nums[low],nums[high]));
                    while(low < high && nums[low] == nums[low+1]) ++low;
                    while(low < high && nums[high] == nums[high-1]) --high;
                    ++low;
                    --high;
                }
                else if(nums[low]+nums[high] > -nums[i]) --high;
                else ++low;
            }
        }
        return res;
    }

运行时间49ms,击败35.4%。

16 最接近的三数之和

题目大意

给定一个包括 n 个整数的数组 nums 和一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

分析

这题和前一题的思路一样，如果暴力解法，复杂度为O(n^3)，可能会超时。这里采用双指针的方法，先给数组排序，然后一遍for循环固定nums[i],并移动双指针l,r。

代码

public int threeSumClosest(int[] nums, int target) {
        if(nums.length < 3) return 0;
        Arrays.sort(nums);
        int res = nums[0]+nums[1]+nums[2];
        for(int i=0;i<nums.length-2;i++) {
            int l = i+1, h = nums.length-1; //双指针
            while(l<h) {
                int threeSum = nums[i]+nums[l]+nums[h];
                if(Math.abs(threeSum-target) < Math.abs(res-target)) {
                    res = threeSum;
                } 
                if(threeSum == target) return threeSum;
                else if(threeSum > target) --h;
                else ++l;
            }
        }
        return res;
    }

运行时间6ms，击败85.76%。

18 四数之和

题目大意

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
示例：

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

代码一

这里采用集中去重的方法，还有可以优化的地方。

public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums.length<4) return res;
        Arrays.sort(nums);
        for(int i=0;i<nums.length-3;i++){
            for(int j=i+1;j<nums.length-2;j++) {
                int l = j+1, r = nums.length-1;
                int tmp = target - nums[i] - nums[j];
                while(l<r) {
                    if(nums[l]+nums[r] == tmp) {
                        res.add(Arrays.asList(nums[i],nums[j],nums[l],nums[r]));
                        ++l;
                        --r;
                    } else if(nums[l] + nums[r] < tmp) l++;
                    else r--;
                }
            }
        }
        List<List<Integer>> tmp = new ArrayList<>();
        for(int i=0;i<res.size();i++)
            if(!tmp.contains(res.get(i))) tmp.add(res.get(i));
        return tmp;
    }

运行时间42ms,击败32.05%。

代码二

固定前两个num，然后调节nums[l],nums[r]。

public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums.length <4) return res;

        Arrays.sort(nums);
        for(int i=0;i<nums.length-3;i++) {
            //首元素
            if(i>0 && nums[i] == nums[i-1]) continue;
            int min1 = nums[i]+nums[i+1]+nums[i+2]+nums[i+3];
            if(min1>target) break;
            int max1 = 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;
                min1 = nums[i]+nums[j]+nums[j+1]+nums[j+2];
                if(min1>target) break;

                max1 = nums[i]+nums[j]+nums[nums.length-1]+nums[nums.length-2];
                if(max1<target) continue;
                //第三、四个元素
                int l = j+1, r = nums.length-1;
                int tmp = target - nums[i] - nums[j];
                while(l<r) {
                    if(nums[l]+nums[r] == tmp) {
                        res.add(Arrays.asList(nums[i],nums[j],nums[l],nums[r]));
                        while(l<r && nums[l] == nums[l+1]) ++l;
                        while(l<r && nums[r] == nums[r-1]) --r;
                        ++l;--r;
                    } else if(nums[l]+nums[r] < tmp)
                        ++l;
                    else --r;
                }

            }

        }
        return res;
    }

运行时间4ms,击败99.57%。