[LeetCode] 016. 3Sum Closest (Medium) (C++/Java/Python)

索引：[LeetCode] Leetcode 题解索引 (C++/Java/Python/Sql)Github: https://github.com/illuz/leetcode

016.3Sum_Closest (Medium)链接：

题目：https://oj.leetcode.com/problems/3sum-closest/代码(github)：https://github.com/illuz/leetcode

题意：

在给定数列中找出三个数，，使和最接近 target。

分析：

与 015. 3Sum (Medium) 类似，甚至更简单。还是先排序，再左右夹逼。

代码：

C++:

class Solution {public:int threeSumClosest(vector<int> &num, int target) {int ret = num[0] + num[1] + num[2];int len = num.size();sort(num.begin(), num.end());for (int i = 0; i <= len – 3; i++) {// first number : num[i]int j = i + 1;// second numberint k = len – 1;// third numberwhile (j < k) {int sum = num[i] + num[j] + num[k];if (abs(sum – target) < abs(ret – target))ret = sum;if (sum < target) {++j;} else if (sum > target) {–k;} else {++j;–k;}}}return ret;}};

Java:

public class Solution {public int threeSumClosest(int[] num, int target) {Arrays.sort(num);int ret = num[0] + num[1] + num[2];int len = num.length;for (int i = 0; i <= len – 3; i++) {// first number : num[i]int j = i + 1;// second numberint k = len – 1;// third numberwhile (j < k) {int sum = num[i] + num[j] + num[k];if (Math.abs(sum – target) < Math.abs(ret – target))ret = sum;if (sum < target) {++j;} else if (sum > target) {–k;} else {++j;–k;}}}return ret;}}

Python:

class Solution:# @return an integerdef threeSumClosest(self, num, target):if not len(num):return 0ret = num[0] + num[1] + num[2]num.sort()for i in range(len(num) – 2):j = i + 1k = len(num) – 1while j < k:tsum = num[i] + num[j] + num[k]if abs(tsum – target) < abs(ret – target):ret = tsumif tsum < target:j += 1elif tsum > target:k -= 1else:j += 1k -= 1return ret

其实你已经错过了旅行的意义。