[LeetCode] 15. 3Sum (C++)

문제

정수 배열이 주어졌을 때,

1. i ≠ j
2. i ≠ k
3. j ≠ k
4. nums[i] + nums[j] + nums[k] == 0
5. 결과에 중복된 트리플을 포함하지 않는다

즉, 3개의 값이 모두 다르고 합이 0인 정수 3개 묶음을 리턴하기

생각할 것

브루트포스를 사용한다면 O(n^3)의 시간복잡도가 소요된다.

하지만 배열의 최대 인자 개수가 3000개이므로 3000 * 3000 * 3000 = 3 * 3 * 3 * 10^9

최대 10의 9제곱이상의 연산이 필요할 수 있다.

→ 보통 1초 제한이라고 하면 1억개의 연산이 소요된다고 여기며 그 이상일 경우 시간 제한에 걸리는 경우가 많다.

 

다른 방법으로 투포인터를 활용할 수 있다.

1. 가장 먼저 정수 배열을 정렬한다.
2. low 값 하나를 고정하고 다음 값을 투포인터를 활용해 0보다 작으면 작은 수를 키우고, 0보다 크면 큰 수를 줄여나간다.
3. 0인 값을 찾은 경우 결과 배열에 추가하고, 중복된 결과를 피하기 위해 동일한 값의 인덱스를 넘어간다.
4. 그리고 low인덱스도 동일한 값은 건너뛰도록 한다.

코드

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

        sort(nums.begin(), nums.end());
        for(int low = 0; low < nums.size() - 1; low++){
            int mid = low + 1, high = nums.size() - 1;
            while(mid < high){
                if(nums[low] + nums[mid] + nums[high] < 0){
                    mid++;
                }
                else if(nums[low] + nums[mid] + nums[high] > 0){
                    high--;
                }
                else {
                    res.push_back({nums[low], nums[mid], nums[high]});
                    int last_mid = mid, last_high = high;
                    while(mid < high && nums[mid] == nums[last_mid]) mid++;
                    while(mid < high && nums[high] == nums[last_high]) high--;
                }
            }
            while(low + 1 < nums.size() && nums[low] == nums[low+1]) low++;
        }

        return res;
    }
};

아래 코드를 넣지 않는 경우 중복된 결과가 나타났다!

while(low + 1 < nums.size() && nums[low] == nums[low+1]) low++;

이외에도 while문을 통해 동일한 값을 건너뛰어서 중복된 결과를 넣지 않도록 해야한다.