算法题：16. 最接近的三数之和（Python Java 详解）

之和（Python Java 详解）"/>

算法题：16. 最接近的三数之和（Python Java 详解）

 解题思路

Step1：先对数组排序，然后设置3个指针，指针1遍历范围为（0~数组长度减2）。

Step2：指针1位置确定时，指针1后面的数组元素首位各放置一个指针（指针2、指针3）。

Step3：如果三数之和=target，则返回target值；如果三数之和<target，则将指针2往后移动，如果三数之和>target，则将指针3往前移动。

Step4：当指针2和指针3重合时，则将指针1往后移动。

Step5：重复 Step2 到 Step4。直到指针1遍历完。

Java代码

import java.util.Arrays;public class ThreeSumClosest {public static void main(String[] args) {Solution sol = new Solution();System.out.println(sol.threeSumClosest(new int[]{-1, 2, 1, -4}, 1));}
}class Solution {public int threeSumClosest(int[] nums, int target) {Arrays.sort(nums);int n = nums.length;int min_diff = Integer.MAX_VALUE;//当前找到的三数之和与target的最小差值int ans = 0;//最小差值对应的三数之和int cur_sum = 0;int cur_diff = 0;for (int i = 0; i < n - 2; i++) {//优化一：如果有重复元素则跳过if (i > 0 && nums[i] == nums[i - 1]) {continue;}//优化二：如果加上最后面两个数依旧没有target大，则判断一下三数之和之后跳过当前循环cur_sum = nums[i] + nums[n - 2] + nums[n - 1];if (target >= cur_sum) {cur_diff = target - cur_sum;if (cur_diff == 0) {return target;}if (cur_diff < min_diff) {ans = cur_sum;min_diff = cur_diff;}continue;}//优化三：前面3个数的和已经>=target，则判断三数之和之后跳出循环cur_sum = nums[i] + nums[i + 1] + nums[i + 2];if (target <= cur_sum) {cur_diff = cur_sum - target;if (cur_diff == 0) {return target;}if (cur_diff < min_diff) {ans = cur_sum;}break;}int j = i + 1, k = n - 1;while(j < k){cur_sum = nums[i] + nums[j] + nums[k];if (cur_sum == target) {return target;}cur_diff = target - cur_sum;if (cur_sum < target) {if (cur_diff < min_diff) {ans = cur_sum;min_diff = cur_diff;}j++;} else {  //cur_sum > targetcur_diff = -cur_diff;if (cur_diff < min_diff) {ans = cur_sum;min_diff = cur_diff;}k--;}}}return ans;}
}

Python代码

class Solution(object):def threeSumClosest(self, nums, target):nums = sorted(nums)  # or nums.sort()n = len(nums)min_diff = float('inf')ans = 0for i in range(n-2):# 优化一：如果有重复元素则跳过if i > 0 and nums[i] == nums[i-1]:continue# 优化二：如果加上最后面两个数依旧没有target大，则判断一下三数之和之后跳过当前循环cur_sum = nums[i] + nums[n - 2] + nums[n - 1]if target >= cur_sum:cur_diff = target - cur_sumif cur_diff == 0:return targetif cur_diff < min_diff:ans = cur_summin_diff = cur_diffcontinue# 优化三：前面3个数的和已经>=target，则判断三数之和之后跳出循环cur_sum = nums[i] + nums[i + 1] + nums[i + 2]if target <= cur_sum:cur_diff = cur_sum - targetif cur_diff == 0:return targetif cur_diff < min_diff:ans = cur_sumbreakj, k = i + 1, n - 1while j < k:cur_sum = nums[i] + nums[j] + nums[k]if cur_sum == target:return targetcur_diff = target - cur_sumif cur_sum < target:if cur_diff < min_diff:ans = cur_summin_diff = cur_diffj += 1else:cur_diff = -cur_diffif cur_diff < min_diff:ans = cur_summin_diff = cur_diffk -= 1return ansif __name__ == '__main__':sol = Solution()print(sol.threeSumClosest([-1, 2, 1, -4], 1))  # 2

完整题目

16. 最接近的三数之和

给你一个长度为 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

提示：

• 3 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000
• -10^4 <= target <= 10^4