一、题目描述
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数,使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
示例 1:
输入:nums = [-1,2,1,-4], target = 1
输出:2
解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
示例 2:
输入:nums = [0,0,0], target = 1
输出:0
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/3sum-closest
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
二、运行结果
三、解题思路
这题的思路和力扣第15题的思路几乎是一致的,同样是采用排序+双指针的方式,可以参考另一篇博客:https://blog.csdn.net/LJH132465/article/details/129003854
while循环体内注释掉的内容是为了直接跳过重复的组合,不用再多计算一次,可要可不要,测试发现,加上这部分运行需要的时间好像更长了。。。不知道是什么原因hhhh
四、AC代码
class Solution {public int threeSumClosest(int[] nums, int target) {int len = nums.length;Arrays.sort(nums);//最接近的和, 三数与target最小的差绝对值int ans = nums[0]+nums[1]+nums[2];for(int i=0; i<len-2; ++i){int j = i+1, k = len-1;while(j < k){// if(j > i+1) { // 重复的情况,不用再计算一次// while(nums[j]==nums[j-1] && j<k) j++;// }// if(k < len-1){// while(nums[k] == nums[k+1] && k>j) k--;// }// if(j == k) break;int curSum = nums[i]+nums[j]+nums[k];if(Math.abs(target-curSum) < Math.abs(target-ans)) {ans = curSum;}if(curSum > target) k--; //k前移else if(curSum < target) j++;else return ans; //相等的情况}}return ans;}
}