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 |