传送门

LC的daily真是越来越骚了，本来打算写一个O(n3)T了后再来优化，结果居然过了，虽然击败感人…

//时间击败6.58%
//空间击败7.14%
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int n = nums.size();
        int minn = INT_MAX;
        int ans;

        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                for(int k = 0; k < n; k++)
                {
                    if(i == j || j == k || i == k) continue;
                    int tmp = nums[i] + nums[j] + nums[k];
                    if(tmp == target) return tmp;
                    if(abs(tmp - target) < minn)
                    {
                        minn = abs(tmp - target);
                        ans = tmp;
                    }
                }

        return ans;
    }
};

这可能是我在LC上A过最低效的算法了。

那么来思考一下怎么优化吧。

上述算法低效的原因是用了三重循环依次枚举每一个数，很直观也很低效，考虑简化这个过程来获取更优的时间复杂度。

对于题述的三个数a,b,c，我们求的是sum=a+b+c与target的相似关系，即a+b+c≈target。如果我们变一下相，则有a=target-b-c，即对于每一个给定的a，所得到的的sum值仅与b和c有关，那么只需要去枚举b和c就好了。

实际实现上，采用双指针来实现。一个外部大循环用来枚举a，然后内部定义两个指针l与r，l指向a之后的第一个元素，r指向最后一个元素。通过比较当前元素和与target的大小关系来不断缩小区间，这样就可以做到同时枚举b与c两个元素。

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++)
        {
            int l = i + 1, r = n - 1;
            while(l < r)
            {
                int tmpsum = nums[l] + nums[r] + nums[i];
                if(abs(tmpsum - target) < abs(ans - target))
                {
                    ans = tmpsum;
                }
                if(tmpsum > target) r--;
                else 
                    if(tmpsum < target) l++;
                    else return tmpsum;
            }
        }

        return ans;
    }
};