某数之和系列(二)

Posted by Lain on 09-20,2019

1、最接近的三数之和

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

例如,给定数组 nums = [-1,2,1,-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

这题乍看上去,和我们上次做的三数之和很像,只不过条件从三个数相加等于0,变成了三个数之和与某个固定值最接近,那么我们的双指针法又能派上用场了。只需要先排序,借助已经排好序的数组,只要通过判断三数之和与目标值的差值的绝对值大小,让双指针向中心靠拢,就可以逼近目标值。

代码如下:

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);//老规矩,排序
        int min = Integer.MAX_VALUE;
        int result = Integer.MAX_VALUE;
        for(int k = 0;k<nums.length - 2;k++){
            //区间坐标
            int i = k + 1 ;
            int j = nums.length - 1;
            while(i < j){
                //计算和值
                int sum = nums[k] + nums[i] + nums[j];
                if(sum > target){//和值大于目标值
                    j--;//移动右边指针,平衡和值
                }
                if(sum == target){//三数之和恰好等于目标值,目标达成
                    return sum;
                }
                if(sum < target){//和值小于目标值
                    i++;//移动左边指针,平衡和值
                }
                //计算与target之间的差值的绝对值
                int minTemp = Math.abs(sum - target);
                if(minTemp< min){//差值的绝对值小于当前最小值时
                    min = minTemp;//更新当前最小差值
                    result = sum;//更新结果
                }
            }
        }
        return result;
    }
}

之后我又看到对双指针法的一种改进,它添加了一层判断,先计算区间最小和值和区间最大和值,然后判断两者和目标值之间的关系,如果区间最小和值大于target,则不需要再进行之后的循环操作了,因为循环中出现的和值必定比区间最小值大,与目标值的差值也就越大;同理,如果区间最大值小于target,那也没必要继续进行之后的循环操作了。我觉得这个加上这个判断不仅是减少了部分情况下的复杂度,而且很好的体现出了双指针法的精髓,有助于对双指针法的理解。
这里给出他的解法:


/**
 * 作者:tenlee   
 * 链接:https://leetcode-cn.com/problems/3sum-closest/solution/shuang-zhi-zhen-fa-you-hua-java-2msji-bai-100-by-t/   
 * 来源:力扣(LeetCode)
 */
public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int result = Integer.MAX_VALUE, left, right, min = Integer.MAX_VALUE;
        for (int k = 0; k < nums.length - 2; k++) {
            left = k + 1;
            right = nums.length - 1;

            // 区间[left,right]内,和最小的值
            int rangeMin = nums[k] + nums[left] + nums[left + 1];
            // 区间[left,right]内,和最大的值
            int rangeMax = nums[k] + nums[right] + nums[right - 1];
            if (rangeMin > target) {
                // 区间最小值比目标大, 没必要寻找区间其他值的和了
                if (rangeMin - target < min) {
                    min = rangeMin - target;
                    result = rangeMin;
                }
            } else if (rangeMax < target) {
                // 区间最大的值比目标还要小,也没必要寻找区间其他值的和了
                if (target - rangeMax < min) {
                    min = target - rangeMax;
                    result = rangeMax;
                }
            } else {
                while (left < right) {
                    int sum = nums[left] + nums[right] + nums[k];
                    if (sum < target) {
                        left++;
                    } else if (sum > target) {
                        right--;
                    } else {
                        return sum;
                    }
                    if (Math.abs(sum - target) < min) {
                        result = sum;
                        min = Math.abs(sum - target);
                    }
                }
            }
        }
        return result;
    }

2、 四数之和

给定一个包含 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]
]

现在遇到这类问题,感觉都有点轻车熟路了,不要问,问就是双指针法(
思路都是一样的,先排序,然后再固定数组的前两个数,然后再使用两个指针标记剩下的数组空间,判断四数之和与目标值的大小,大了就移动右指针,小了就移动左指针,So easy~
然后我就在剪枝上摔了个狗吃屎==
在三数之和里,在剪枝判断里有个细节,就是有个前置条件k>0(k是被固定元素的指针),当时没深入思考这点,因为这个判断在三数之和里仅仅是为了保证第一次循环的时候,nums[k-1]不会报越界异常。
但是在四数之和里,这个判断除了保证第一层的剪枝判断不越界以外,还保证了第二层的剪枝判断不会多剪,所谓的剪枝,是应该在该指针的活动范围内进行的判断,如果是[0,0,0,0]这样的测试用例,当k1 指向了下标0,k2指向下标1,如果在剪枝的时候不做k2>k1+1这个判断的话(注意,对于k2来说,是不存在k2-1越界的,因为有k1的存在),就会漏掉[0,0,0,0]这个解。在leetcode上有几个解答,把[0,0,0,0]作为特殊情况特殊处理,实际上是不对的,只要剪枝判断理解到位,这种情况是极其正常的。
下面给出代码:

public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> lists = new ArrayList<>();
        Arrays.sort(nums);
        for(int k1 = 0;k1<nums.length - 3; k1++){
            if(k1>0&&nums[k1]==nums[k1-1])continue;//剪枝判断,k1>0,防止k1=0时nums[k1-1]越界
            for(int k2 = k1+1;k2<nums.length - 2;k2++){
                int l = k2 + 1;
                int r = nums.length -1;
                if(k2>k1+1&&nums[k2]==nums[k2-1])continue;//剪枝判断,k2>k1+1 保证当nums[k1]==nums[k1+1]时,不会漏掉结果
                //区间最小值判定
                int minSum = nums[k1] + nums[k2] + nums[l] + nums[l+1];
                if(minSum > target)continue;
                //区间最大值判定
                int maxSum = nums[k1] + nums[k2] + nums[r] + nums[r-1];
                if(maxSum <target)continue;
                while (l<r){
                    int sum = nums[k1] + nums[k2] + nums[l] + nums[r];
                    if(sum < target){
                        while(l<r &&nums[l]==nums[++l]);
                    }
                    if(sum > target){
                        while(l<r &&nums[r]==nums[--r]);
                    }
                    if(sum == target){
                        lists.add(Arrays.asList(nums[k1] , nums[k2] , nums[l] , nums[r]));
                        while(l<r &&nums[r]==nums[--r]);
                        while(l<r &&nums[l]==nums[++l]);
                    }
                }
            }
        }
        return lists;
    }

时间复杂度为O(nlogn)+O(n2) = O(n2)

提交时间提交结果执行用时内存消耗语言
几秒前通过7 ms37.4 MBJava