最接近的三数之和

0x1 题目详情

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

测试用例:

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

0x2 解题思路

看到题目是不是有种似曾相识的感觉?那就是在一个数组找到三数和为0的组合，如果不熟悉三指针的基本玩法，可以去看看我写的关于三数之和题解。

这道题稍微变通一下也可以使用三指针解决。

首先需要对数组进行排序。

我们要求的是三数之和sun与target之间的差最小。同样固定一个指针i，然后使用left和right指针处理i之后的所有元素。首先讲述一下指针移动的规则:

• target-sum==0:又因为题目保证了只有一个解，所以可以直接返回target

• target-sum!=0:当二者不等时，情况又可以分为两种：

  • target-sum>0:表示还可以增加当前的sum，即移动左指针left

  • target-sum<0:表示当前sum太大了，需要减小，即移动右指针right

下面就是核心步骤辣。

我们可以规定一个sum与target的差值difference：

• 如果当前Math.abs(target-sum)<difference时，我们就可以记录当前的三个数之和并更新最小值，然后指针的规则如上所述。

• 如果当前Math,abc(target-sum)>=difference时，按照上述规则移动指针

我们对数组的每个元素都这样处理，那么最后的结果即为最接近target的三数之和。

0x3 代码实现

理解了上述思路之后，代码实现就非常简单了，跟求三数之和的代码没有什么大的差别。

因为对数组进行了排序，所以复杂度至少为$O(NlogN)$,而后处理每个元素的复杂度为$O(N^2)$,即最后的复杂度为$O(N^2)$

class Solution {
public int threeSumClosest(int[] nums, int target) {
    if(nums==null || nums.length<3){
        return 0;
    }
    Arrays.sort(nums);
    int result=0;
    int difference=Integer.MAX_VALUE;
    int sum=0;
    int left=0;
    int right=0;
    for(int i=0;i<nums.length;i++){
        if(i-1>-1 && nums[i-1]==nums[i]){
            continue;
        }
        left=i+1;
        right=nums.length-1;
        //差值最小的结果肯定是与sum相等的时候
        sum=target-nums[i];
        while(left<right){
            if(nums[left]+nums[right]==sum){
                return target;
            }
            //如果nums[left]与nums[right]的和与当前目标sum的差值小于最小的差值，那么
            //更新difference与结果
            else if(Math.abs(sum-(nums[left]+nums[right]))<difference){
                result=nums[i]+nums[left]+nums[right];
                difference=Math.abs(sum-(nums[left]+nums[right]));
            }
            //最后统一处理指针的移动
            if(nums[left]+nums[right]<sum){
                left++;
            }
            else{
                right--;
            }
        }
    }
    return result;
}
}

课后总结

这道题与三数之和没有啥大的区别，会求三数之和，这道题稍微写写画画也能做出来。

只不过我最后还要强调一点：在数组中使用双指针及多指针时一般都需要对数组进行排序。