top-145-#15

[LionCoder4ever]

• double pointer.
• the ans couldn't be duplicated, after sort, the outer loop can omit the duplicated "first" item in item array.
• in the inner loop, when move the "left", "right" pointer, still need to omit the duplicated number. eg. [-1, 0 , 1, 1, ,1 , 3]
  "first" item is -1, init left point is 1, right point is 5, target is 1
  loop times 1 : nums[1] + nums[5] = 3 > target , end--, end = 4
  loop times 2 : nums[1] + nums[4] = 0 = target , find ans, [-1,0,1], but end--, nums[3] still be 1, need to omit until find the nums[end] != 1

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans(0);
        // for(int i=0;i<n;i++) printf("%d ", nums[i]);

        for(int i=0;i<n;i++) {
            // 跳过重复
            if(i>0 && nums[i] == nums[i-1]) continue;

            int l = i + 1,  r = n - 1;
           // 简化为寻找两数之和, 排序后数组有单调性,分别从头尾开始找
            while(l <  r) {
                int sum = nums[l] + nums[r];
                int value = nums[i];
                int target = -nums[i];
                if(sum == target) {
                    vector<int> item(0);
                    item.push_back(nums[i]);
                    item.push_back(nums[l]);
                    item.push_back(nums[r]);
                    ans.push_back(item);
                    while(l < r && nums[l] == nums[l + 1]) {
                        l++;
                    }
                    l++;
                    while(l < r && nums[r] == nums[r-1]) {
                        r--;
                    }
                    r--;
                } else if( sum > target)  {
                    r--;
                } else {
                    l++; 
                }
            }
        }
        return ans;
    }
};