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).

思路：

最开始想法是要排序，这样可以为以后剪枝做方便。虽然最后证明排序和剪枝毛线关系都没有，但就是这一步直觉让我做出了这道题目。

排序后，就是三个数怎么选择了。第一个很好定，那就是遍历一遍容器，所以第一个数构成了第一层循环。第二个数和第三个数也可以按顺序选取，三个数的和由最小到最大，可是更直观的方法是一个取最小的，一个取最大的，这样三个数的和就位于最小与最大之间（第一个数是固定的，改变第二个和第三个数的值）。举个例子，[1,2,3,4,5]。a1=1, a2=2, a3=5,这三个数和为8，位于1+2+3=6（最小），1+4+5=10之间。这样做的目的是方便后面的逻辑组织，使得逻辑更加直观。

将三个数的和与目标比较，比目标小，左边加1使接下来三个数的和增加，比目标大，右边减1是接下来三个数的和减小。如此构成了第二层循环。

题解：

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

View Code

[leetcode] 3Sum Closest