LeetCode - 15. 3Sum

15. 3Sum - medium

문제

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.

제한사항

• The solution set must not contain duplicate triplets.

입출력 예

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

풀이

• Sort, Array

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        if (nums.size() < 1) {
            return {};
        }
        
        int len = nums.size();
        std::vector<std::vector<int>> result;
        
        // 정렬
        sort(nums.begin(), nums.end());

        for (auto i = 0 ; i < len - 2 ; ++i) {
            // 중복을 피하기 위해 이전값과 같은 값이면 넘어감
            if (i > 0 && nums[i] == nums[i-1]) {
                continue;
            }
            
            int one = i;
            int two = i + 1;
            int three = len - 1;
            
            // nums[one]의 값을 기준으로 다음 두 인덱스의 값을 찾는데, 
            // 이때 Binary Search와 유사하게 검색
            while (two < three) {
                int val = nums[one] + nums[two] + nums[three];

                // 정렬 되어 있으므로,
                // val < 0 이면 두번재 인덱스를 증가
                // val > 0 이면 세번째 인덱스를 감소
                if (val < 0) {
                    ++two;
                } else if(val > 0) {
                    --three;
                } else {
                    result.push_back({nums[one], nums[two], nums[three]});
                    
                    // 중복을 피하기 위해 같은 값의 인덱스를 넘김
                    while (two < three && nums[two] == nums[two+1]) {
                        ++two;
                    }

                    // 중복을 피하기 위해 같은 값의 인덱스를 넘김
                    while (two < three && nums[three] == nums[three-1]) {
                        --three;
                    }
                    
                    ++two;
                    --three;
                }
            }
        }
        
        return result;
    }
};