LeetCode #16 – 3Sum Closest [数组 双指针]

链接:https://leetcode.com/problems/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.

题意:给定一个数组和目标,求某三个数的和,与目标相差最小。

分析:跟上个题目差不多,一个数来枚举,剩下两个数用双指针确定。

代码:

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int best = accumulate(nums.begin(), nums.begin()+3, 0);
        if(nums.size() == 3) return best;
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size()-2; ++i) {
            if(i && nums[i]==nums[i-1]) continue;
            int l = i + 1, r = nums.size()-1;
            while(l < r) {
                if(l != i+1 && nums[l]==nums[l-1]) ++l;
                else if(r != nums.size()-1 && nums[r]==nums[r+1]) --r;
                else {
                    int sum = nums[i] + nums[l] + nums[r];
                    if(abs(best-target) > abs(sum-target))
                        best = sum;
                    if(sum > target) --r;
                    else if(sum < target) ++l;
                    else --r, ++l;
                }
            }
        }
        return best;
    }
};

欢迎留言