LeetCode : 15. 3Sum

Two Pointers 문제이다.

 

[메인 로직]

i, low, high값을 잡아서 3개의 값을 더해준 sum과 0을 비교해서 작을 때, 클 때, 같을 때 조건을 통해 구현해주면 된다.

앞에서 sort를 했기 때문에

0보다 작으면 -> low++

0보다 크면 -> high--

0과 같으면 바로 ans에 넣어주고

혹여나, 중복되는 vector를 ans에 넣을 수 없기 때문에  ex) [-1, 0, 1] == [-1, 0, 1]

low와 high를 같은 값이 아닐때 까지 while문으로 처리해주어야 한다!!

 

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        
        sort(nums.begin(), nums.end());
        
        for(int i=0; i<nums.size(); i++){
            if(i>0 && nums[i]==nums[i-1]) continue;
            
            int low = i+1;
            int high = nums.size()-1;
            
            while(low<high){
                int sum = nums[i]+nums[low]+nums[high];
                if(sum<0){
                    low++;
                }else if(sum>0){
                    high--;
                }else{
                    vector<int> temp;
                    temp.push_back(nums[i]);
                    temp.push_back(nums[low]);
                    temp.push_back(nums[high]);
                    ans.push_back(temp);
 
                    while(low+1<nums.size() && nums[low+1]==nums[low]){
                        low++;
                    }
 
                    while(high-1>=0 && nums[high-1]==nums[high]){
                        high--;
                    }
 
                    // 위에 while문은 같은 것의 끝을 가르키고 있는 것이니 새로운 값이 나오도록 한 번 더 이동해준다.
                    high--;
                    low++;
                }                
            }
        }
        
        return ans;
    }
};