博文中会简要介绍Leetcode P0016题目分析及解题思路。
“3Sum Closest”是”3Sum”的一道衍生题，这道题也可以划归为”kSum”这样的原型。这道题考察的核心是双指针和指针移动的边界条件。
Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
这道题的思路和p00015的思路基本一致。我们可以得出以下边界条件：
sum3 = nums[left]+nums[med]+nums[right]
fix left
if sum3 > target
move right;
record closest one; right指针指向的是最大值，由于数组排序，right右边的一定更大，所以左移，并且若当前更接近target则记录
else if sum3 < target
move med;
record closest one; 理由同上但相反
else
return target;
以下是Java的题解代码实现。
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int closest = Integer.MIN_VALUE, diff = Integer.MAX_VALUE;
for (int left=0; left<nums.length-2; ++left) {
if (left > 0 && nums[left] == nums[left-1])
continue;
int med = left+1, right = nums.length-1;
while (med < right) {
int sum3 = nums[left]+nums[med]+nums[right];
if (sum3 == target)
return sum3;
else if (sum3 < target) {
if (Math.abs(sum3-target) < diff) {
diff = Math.abs(sum3-target);
closest = sum3;
}
++med;
}
else {
if (Math.abs(sum3-target) < diff) {
diff = Math.abs(sum3-target);
closest = sum3;
}
--right;
}
}
}
return closest;
}
}
以下是C++的题解代码实现。
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int closest = INT_MAX, diff = INT_MAX;
for (int left=0; left<nums.size()-2; ++left) {
if (left > 0 && nums[left] == nums[left-1])
continue;
int med = left+1, right = nums.size()-1;
while (med < right) {
int sum3 = nums[left]+nums[med]+nums[right];
if (sum3 == target)
return sum3;
else if (sum3 < target) {
if (abs(sum3-target) < diff) {
diff = abs(sum3-target);
closest = sum3;
}
++med;
}
else {
if (abs(sum3-target) < diff) {
diff = abs(sum3-target);
closest = sum3;
}
--right;
}
}
}
return closest;
}
};