Leetcode 16 最接近的三数之和 ( 3Sum Closest *Medium* ) 题解分析
题目介绍
Given an integer array nums
of length n
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.
简单解释下就是之前是要三数之和等于目标值,现在是找到最接近的三数之和。
示例
Example 1:
Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
Example 2:
Input: nums = [0,0,0], target = 1
Output: 0
Constraints:
3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-10^4 <= target <= 10^4
简单解析
这个题思路上来讲不难,也是用原来三数之和的方式去做,利用”双指针法”或者其它描述法,但是需要简化逻辑
code
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
// 当前最近的和
int closestSum = nums[0] + nums[1] + nums[nums.length - 1];
for (int i = 0; i < nums.length - 2; i++) {
if (i == 0 || nums[i] != nums[i - 1]) {
// 左指针
int left = i + 1;
// 右指针
int right = nums.length - 1;
// 判断是否遍历完了
while (left < right) {
// 当前的和
int sum = nums[i] + nums[left] + nums[right];
// 小优化,相等就略过了
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
// 这里判断,其实也还是希望趋近目标值
if (sum < target) {
left++;
} else {
right--;
}
// 判断是否需要替换
if (Math.abs(sum - target) < Math.abs(closestSum - target)) {
closestSum = sum;
}
}
}
}
return closestSum;
}