双指针简化数组遍历

16.题目链接-来源:力扣(LeetCode)(中等)

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

示例:

输入:nums = [-1,2,1,-4], target = 1
输出:2
解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

思路:

遍历方式跟上一道题雷同。先快速排序,再一层遍历+一层双指针。修改一下更新最佳值的条件即可,要求target和当前三数和的差值的绝对值尽可能小。
偷懒的话,可以不进行最后的指针优化(跳过重复元素),复杂度还是一样的。
时间复杂度:O(n²)
空间复杂度:O(1)

实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int n = nums.length;
int closestSum = nums[0] + nums[1] + nums[2];
for (int i = 0; i < n; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
for (int j = i + 1, k = n - 1; j < k;) {
int curSum = nums[i] + nums[j] + nums[k];

if (curSum == target) {
return target;
}

if (Math.abs(curSum - target) < Math.abs(closestSum - target)) {
closestSum = curSum;
}

if (curSum > target) {
int k0 = k - 1;
while (j < k0 && nums[k0] == nums[k]) {
--k0;
}
k = k0;
} else {
int j0 = j + 1;
while (j0 < k && nums[j0] == nums[j]) {
++j0;
}
j = j0;
}
}
}
return closestSum;
}
}