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 ms | 37.4 MB | Java |
