Leetcode 16. 最接近的三数之和 ゝ一纸荒年。 2022-09-15 15:49 133阅读 0赞 ## 题目重述 ## 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。 ### 示例: ### 输入:nums = [-1,2,1,-4], target = 1 输出:2 解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。 ### 提示: ### 3 <= nums.length <= 10^3 -10^3 <= nums[i] <= 10^3 -10^4 <= target <= 10^4 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/3sum-closest 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 ## 思路 ## 类似于三数之和这道题,思路是一样的,只不过不是找到等于target的,而是不断更新,找到最接近的那个数。 ## Java实现 ## class Solution { public int threeSumClosest(int[] nums, int target) { // -4 -1 1 2 Arrays.sort(nums); int res = nums[0]+nums[1]+nums[2]; for(int i=0;i<nums.length;i++){ if(i>0 && nums[i]==nums[i-1]){ continue; } // 双指针 int left = i+1,right = nums.length-1; while(left<right){ int t = nums[i]+nums[left]+nums[right]; if(t==target){ return t; } if(Math.abs(target-t)<Math.abs(target-res)){ res = t; } if(t>target){ right--; }else{ left++; } } } return res; } }
还没有评论,来说两句吧...