[LeetCode] 15 - 3Sum

문제

• 링크: https://leetcode.com/problems/3sum
• 난이도: Medium
• 태그: 배열, 투포인터, 정렬
• 결과: Time: 35 ms (98.76%), Space: 29.12 MB (45.50%)

풀이

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

        sort(nums.begin(), nums.end());

        for (int i = 0; i < nums.size() && nums[i] <= 0; ++i)
        {
            if (i != 0 && nums[i - 1] == nums[i]) 
            {
                continue;
            }

            int l = i + 1;
            int r = nums.size() - 1;
            while (l < r) 
            {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum < 0) 
                {
                    ++l;
                }
                else if (sum > 0) 
                {
                    --r;
                }
                else 
                {
                    res.push_back({nums[i], nums[l++], nums[r--]});
                    while (l < r && nums[l] == nums[l - 1])
                    {
                        ++l;
                    }
                }
            }
        }

        return res;
    }
};

일단 배열을 정렬하고, 앞에서부터 차례대로 순회하며 수를 ‘고정’한다. 그 수의 오른쪽 영역에서 다음 두 가지 수를 찾으면 된다.

세 개의 수를 더해서 0을 만드는데 성공했으면, 결과 배열에 넣는 것 뿐만 아니라 추가적인 처리가 필요하다.

1. l과 r 모두 한 칸씩 이동시켜야한다.
   • 0을 만드는게 목적이므로 둘 중 하나만 이동시키면 의미가 없다.
2. 기존과 다른 수가 나올 때 까지 l(또는 r도 가능)을 이동시켜야한다.
   • 그렇지 않으면 중복된 triplet이 나온다.
   • 문제에서는 중복된 triplet을 허용하지 않는다.

이 포스트는 달레 스터디(2주차)에서 진행한 Blind 75 문제집 풀이의 일부입니다.