15. 3Sum

题目：

解答：

先排序，然后通过遍历第一个数，对后两个数，使用有序序列和的查找方法两头逼近即可。注意一些细节可以加速代码运行。

代码：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int len = nums.size();
        vector<vector<int>> result;
        for(int i = 0;i < len - 2;){
            int begin = i + 1, end = len - 1, target = -1 * nums[i];
            if(nums[i] > 0) break;
            while(begin < end){
                int tmp = nums[begin] + nums[end];
                if(tmp < target){
                    while(begin < len && nums[begin] == nums[begin+1]) ++begin;
                    ++begin;
                }else if(tmp >target){
                    while(end > target && nums[end] == nums[end-1]) --end;
                    --end;
                }else{
                    vector<int> vec({nums[i], nums[begin], nums[end]});
                    result.push_back(vec);
                    while(begin < len && nums[begin] == nums[begin+1]) ++begin;
                    while(end > target && nums[end] == nums[end-1]) --end;
                    ++begin, --end;
                }
            }
            while(i < len - 2 && nums[i] == nums[i+1]) ++i;
            ++i;
        }
        return result;
    }
};

更新会同步在我的网站更新(https://zergzerg.cn/notes/webnotes/leetcode/index.html)