【LeetCode算法练习（C++）】3Sum Closest

本文主要是介绍【LeetCode算法练习（C++）】3Sum Closest，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

链接：3Sum Closest

解法：排序，用一对指针j,k搜索，三个数的和如果大于target，需要左移k,如果小于target，需要右移j，遍历i从最小到最大。时间O(n^2)

class Solution {
public:int threeSumClosest(vector<int>& nums, int target) {int sum = 0, ans = INT_MAX / 2, len = nums.size();sort(nums.begin(), nums.end());for (int i = 0; i < len - 2; i++) {int j = i + 1, k = len - 1;while (j < k) {int sum = nums[i] + nums[j] + nums[k];ans = abs(sum - target) < abs(ans - target) ? sum : ans;if (sum < target) {++j;} else if (sum > target) {--k;} else {++j;--k;}}}return ans;}
};

Runtime: 16 ms

这篇关于【LeetCode算法练习（C++）】3Sum Closest的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---