3num

three number question:

• sort array
• loop the array , treat each element as a target ,then to find two number whose sum is -target
• so now the question is 2num, find 2 number in the following subarray
• use two pointer leftand right point to nums[begin] and nums[end]
• when the sum < -target , left++ ,when sum > -target , right-- else it is answer , and go on to find other answers.
• about how to handle repetitive answer , cause the array is sorted, so from left to right ,we just need to handle the first element of the repetitive element ,cause the answers set of handling first element already include all answer , so just skip other repetitive element.
• about how to handle repetitive answer in finding the two number , cause if one number is the same so the other one must be the same ,so no matter which one is the same ,we will skip the number ,left++ or right--

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {

        vector<vector<int>> res;
        sort(nums.begin(),nums.end());

        int len = nums.size();

        if(nums.size() < 3)  return res;
        //notice the edge case 
        for(int i=0;i<nums.size()-2;i++)
        {

            int target = nums[i];
            int diff = -target;

            int left = i+1;
            int right = nums.size()-1;

            //skip the repetitive number
            if(i > 0 && nums[i] == nums[i-1])  continue;


            while(left < right)
            {

                if((nums[left] + nums[right]) < diff)
                {
                    left++;
                    // skip the repetitive element 
                    while(nums[left] == nums[left-1]) left++;
                }
                else if((nums[left] + nums[right]) > diff)
                {
                    right--;
                    // skip the repetitive element 
                    while(nums[right] == nums[right+1])  right--;
                }
                else
                {
                    vector<int> v ;
                    v.push_back(target);
                    v.push_back(nums[left]);
                    v.push_back(nums[right]);
                    res.push_back(v);

                    left++;
                    // skip the repetitive element 
                    while(nums[left] == nums[left-1]) left++;

                    right--;
                    // skip the repetitive element 
                    while(nums[right] == nums[right+1]) right--;

                }
            }
        }
        return res;
    }
};