[leetcode 15] 3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Notice that the solution set must not contain duplicate triplets.

 

two sum 진화문제. 3개의 숫자를 합해서 0이 되는 조합을 찾는다.

 

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: []

 

풀이:

- 투포인터 사용

- 인덱스값을 리턴하라고 하지 않았음. 정렬을 해서 사용한다.

- two sum과 동일하게 푼다. 숫자 하나를 미리 정하고(X) 나머지 두 수의 합을 투포인터를 이용해 찾고 -X가 되는지 확인한다.

- 정렬을 해서 i위치 뒤에 있는 숫자들만 따진다. 따라서 i가 0보다 크면(정렬되어 있는 상태이므로) 더 이상 찾지 않는다.

- 중복 체크를 해줘야한다.(문제 조건)

- 투포인터로 계산 시에도 중복된 숫자를 고려해줘야 한다.

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> answer;
        
        if(nums.size() < 3){
            return answer;
        }
        
        int n = nums.size();
        int start,end;
        sort(nums.begin(), nums.end());
        for(int i=0; i<n-2; i++){
             
            int val = nums[i];
            if(val > 0){
                break;
            }
            
            //duplicate
            if(i>0 && val==nums[i-1]){
                continue;
            }
            
            start = i+1, end = n-1;
            
            while(start<end){
                
                int a = nums[start], b = nums[end];
                int sum = a + b;

                if(val + sum == 0){
                    answer.push_back({val, a, b});
                    
                    while(start<end && nums[++start] == a); //무조건 한번은 start 증가
                    while(start<end && nums[--end] == b); //무조건 한번은 end 감소
                   
                }else if(val + sum < 0){
                    start++;
                }else {
                    end--;
                }
               
            }
            
        }
       return answer;

    }
};