[알고리즘] 10 - 3Sum

Link to the problem

3합 문제는 2합 문제의 몇 가지 아이디어를 사용합니다. 그러나이 문제는 두 합계보다 유효한 솔루션을 찾는 것이 훨씬 더 어렵습니다. 따라서 매우 다른 질문입니다. 이 게시물에서는 이 문제를 해결하기 어렵게 만드는 원인과 해결 방법에 대해서도 살펴보겠습니다.

왜 이것이 2합보다 어려운가요?

해시 맵이나 세트를 사용하는 것은 중복을 포착하기에 충분히 효율적이지 않습니다. 두 가지 합계 문제에서 우리가 해야 할 일은 방문한 요소를 집합으로 푸시하고 요소를 방문했다면 무시하는 것뿐이었습니다.

그러나 3개의 합계에 대해서는 숫자 조합이 고유한지 여부를 확인하기 위해 각 숫자에 대한 배열을 저장해야 합니다. 이것은 구현하기가 매우 어렵고 시간 복잡도 측면에서도 비효율적입니다.

해결책

그렇다면 솔루션에 대한 유효한 접근 방식은 무엇입니까? 첫 번째 핵심은 동일한 조합을 만들지 않도록 정렬 기술을 사용하여 모든 중복 항목을 제거하는 것입니다.

예를 들어 배열이 다음과 같은 경우

[1,-3,5,4,-3,2,2,-3,4,-3]

정렬하면

[-3,-3,-3,-3,1,2,2,4,4,5]

따라서 배열을 정렬하여 합이 0이 되는 유효한 조합을 찾은 후에는 중복된 숫자를 건너뛸 수 있습니다.

두 번째 열쇠는 두 개의 포인터 방법을 사용하여 올바른 숫자를 검색하는 것입니다. 합계가 0보다 작을 때 낮은 포인터를 증가시키고 합계가 0보다 크면 높은 포인터를 줄일 수 있습니다.

문제는 코드에서 구현하기가 약간 까다롭습니다.

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

        // Sort the array first. This is for removing duplicates & two pointer search.
        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[low] + nums[high] + nums[i];
                if(sum < 0) low++;
                else if(sum > 0) high--;
                else{
                    vector<int> tmp = {nums[low], nums[high], nums[i]};
                    res.push_back(tmp);
                    low++;
                    while(nums[low] == nums[low-1] && low < high)low++;
                }
            }
        }

        return res;
    }
};

보시다시피 동일한 값을 가진 요소는 건너뜁니다.

if(i > 0 && nums[i] == nums[i-1])continue;

while(nums[low] == nums[low-1] && low < high)low++;

시간 복잡도 분석

솔루션의 시간 복잡도는 O(n^2)입니다. 두 포인터 방법을 사용하기 때문입니다. 문제에 대해 이진 검색을 사용하고 있다고 생각했기 때문에 처음에는 혼란스러웠습니다. 그러나 우리는 각 루프에 대해 하나씩 낮고 높게 이동하기 때문에 솔루션은 O(nlogn) 대신 O(n^2)를 갖게 됩니다.