LeetCode16. 3Sum Closest（对撞指针）

Medium
Accepted：245,713
Submissions：694,617

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

链接

https://leetcode.com/problems/3sum-closest/

题意

给定一个包含n个整数的数组和一个整数target，在数组中找三个数，使得它们的和最接近target，返回这三个数的和，保证唯一解。

题解

和LeetCode15. 3Sum（对撞指针）没有什么区别，此外，因为只要找到最接近target的和，所以无需去重，做法一样，排序后一层循环加对撞指针，时间复杂度$O(n^2)$。

代码

Runtime: 12 ms, faster than 97.48% of C++ online submissions for 3Sum Closest.
Memory Usage: 9.3 MB, less than 100.00% of C++ online submissions for 3Sum Closest.

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int ans = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < n - 2; ++i)
        {
            if (i > 0 && nums[i] == nums[i-1])
                continue;
            int l = i + 1, r = n - 1, sum;
            while (l < r)
            {
                sum = nums[i] + nums[l] + nums[r];
                if (sum == target) // 相等直接返回
                    return sum;
                if (abs(sum - target) < abs(ans - target)) // 找到最接近的
                    ans = sum;
                if (sum < target)
                    ++l;
                else if (sum > target)
                    --r;
            }
        }
        return ans;
    }
};

The end.
2019年2月17日星期日