来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum-closest
题目描述:
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
思路一:
暴力遍历:
- 出事化三个指针,将数组nums所有3个数组合的和与target进行比较,的到最接近的值(不可能有比相等更接近的值，因此如果三数和等于target也可以直接返回).
代码实现：
class Solution {
public int minNum;
public int result;
public int threeSumClosest(int[] nums, int target) {
int len = nums.length;
int sum = nums[0] + nums[1] + nums[2];
// 初始化最小值.
minNum = Math.abs(sum - target);
result = sum;
for (int i = 0; i < len; i++) {
// 重复元素跳过.
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1;
int right = len - 1;
while (left < right) {
while (left < right) {
if (minNum == 0) return sum;
sum = nums[i] + nums[left] + nums[right];
int abs = Math.abs(sum - target);
if (abs <= minNum) {
minNum = abs;
result = sum;
}
right--;
}
left++;
right = len - 1;
}
}
return result;
}
}
思路二:
- 对数组进行排序，保证数组从左往右单调递增.
- 初始化三个指针，i从0开始遍历,left = i + 1,right = nums.length - 1;
- 计算三数和sum,如果sum == target，直接返回
- sum > target，则right--,因为数组单调递增,左移right指针可以使三数和sum减小
- sum < target, 则left++,因为数组单调递增,右移left指针可以使三数和sum增加
代码实现:
class Solution {
public int minNum;
public int result;
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int len = nums.length;
int sum = nums[0] + nums[1] + nums[2];
// 初始化最小值.
minNum = Math.abs(sum - target);
result = sum;
for (int i = 0; i < len; i++) {
// 重复元素跳过.
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1;
int right = len - 1;
while (left < right) {
sum = nums[i] + nums[left] + nums[right];
int abs = Math.abs(sum - target);
if (abs <= minNum) {
minNum = abs;
result = sum;
}
// 三数和等于target,直接返回
if (sum == target) return result;
// 三数和小于tagrget,增加left(因为数组从左到右递增)
if (sum < target) left++;
// 三数和大于tagrget,减小right(因为数组从左到右递增)
else right--;
}
}
return result;
}
}
