[leetcode15] sum of three numbers

Personally to , For record review only

Double pointer

problem

Give you one containing n Array of integers nums, Judge nums Are there three elements in a,b,c , bring a + b + c = 0 ？ Please find out all and for 0 Triple without repetition .

Be careful ： Answer cannot contain duplicate triples .

Example 1：

Input ：nums = [-1,0,1,2,-1,-4]
Output ：[[-1,-1,2],[-1,0,1]]
Example 2：

Input ：nums = []
Output ：[]
Example 3：

Input ：nums = [0]
Output ：[]

Tips ：

0 <= nums.length <= 3000
-105 <= nums[i] <= 105

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/3sum
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

  vector<vector<int>> threeSum(vector<int>& nums) {
    
        /* *  The title gives an array . Ask Mei to cite the combination of all three numbers that add up to zero . And the combination cannot be repeated . *  If you use triple loop enumeration directly . Additional judgment is needed to determine whether the combinations are repeated . *  If you're right first nums Sort . The three numbers required to be enumerated are a<=b<=c. Then you can avoid repetition . */
        sort(nums.begin(), nums.end());

        /* obtain nums size . About to start enumerating .*/
        int size = nums.size();

        // Store results 
        vector<vector<int>> ans;

        for (int first = 0; first < size; first++) {
    // stay first=n-1 When . Can't open the second one for loop .
            /* In order to avoid the repetition of the combination of Meiju */
            if (first > 0 && nums[first] == nums[first - 1])
                continue;
            /* The goal is that the sum of three numbers equals zero . Then, along with second This subscript is getting bigger .third It's getting smaller . *  Start with two pointers . Initialize first third */
            int third = size - 1;
            for (int second = first + 1; second < size; second++) {
    
                /* Or to avoid the repetition of the combination of Meiju */
                if (second > first + 1 && nums[second] == nums[second - 1])
                    continue;
                /* Or first avoid the repetition of the combination */
                while (third > second && third < size - 1 && nums[third] == nums[third + 1])
                    third--;
                /* If the conditions are not met , Continue to move left third*/
                while (third > second && nums[third] + nums[second] > -nums[first])
                    third--;
                /* When double pointers overlap .second If the pointer continues to move to the right . It won't satisfy the meaning of the topic anymore  *  however first You can also continue to move right . */
                if (third == second)
                    break;
                if (nums[third] + nums[second] == -nums[first])
                    /* initialization vector<int> An easy way to use {1,2,3}*/
                    ans.push_back({
     nums[first],nums[second],nums[third] });
                /* The case of less than does not need to be considered . Keep moving right second It can be solved */
            }
        }
        return ans;
    }