LeetCode 15 - 3Sum (Medium)

출처: https://leetcode.com/problems/3sum/

// LeetCode 15 - 3Sum (Medium)
// https://leetcode.com/problems/3sum/

// 문제 설명
// 정수 배열 nums에서 i != j, i != k, j != k 이고
// nums[i] + nums[j] + nums[k] == 0 인 모든 트리플 [nums[i], nums[j], nums[k]]를 반환하라.
// 단, 결과에 중복된 트리플이 들어가면 안 된다.

// 제약 조건
// 3 <= nums.length <= 3000
// -10^5 <= nums[i] <= 10^5

// Example 1
// Input : nums = [-1,0,1,2,-1,-4]
// Output: [[-1,-1,2],[-1,0,1]]
//
// Example 2
// Input : nums = [0,1,1]
// Output: []
//
// Example 3
// Input : nums = [0,0,0]
// Output: [[0,0,0]]

// 접근 — 정렬 후 (고정 + 투 포인터)
// 세 수를 다 도는 O(n^3)을 정렬로 O(n^2)까지 줄인다.
// 1) 오름차순 정렬해 두면 중복 처리와 투 포인터 이동 방향이 단순해진다.
// 2) 첫 수 nums[i]를 고정하고, 그 오른쪽 구간을 l·r 두 포인터로 좁힌다.
//    - 합이 음수면 더 큰 값이 필요하니 l++
//    - 합이 양수면 더 작은 값이 필요하니 r--
//    - 합이 0이면 정답에 담고 양쪽에서 같은 값은 모두 건너뛴다.
// 3) 중복 트리플 방지: i와 l, r 각각에서 직전 값과 같으면 스킵.
// 시간 O(n^2), 공간 O(1) (정렬·결과 제외)

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        int n = (int)nums.size();

        for (int i = 0; i < n - 2; ++i) {
            if (nums[i] > 0) break;                       // 최소값이 양수면 합 0 불가
            if (i > 0 && nums[i] == nums[i - 1]) continue; // 첫 수 중복 스킵

            int l = i + 1, r = n - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum < 0)      ++l;
                else if (sum > 0) --r;
                else {
                    ans.push_back({nums[i], nums[l], nums[r]});
                    while (l < r && nums[l] == nums[l + 1]) ++l; // 둘째 수 중복 스킵
                    while (l < r && nums[r] == nums[r - 1]) --r; // 셋째 수 중복 스킵
                    ++l;
                    --r;
                }
            }
        }
        return ans;
    }
};

정리

• 세 수를 모두 중첩 순회하면 O(n³)이라 n=3000에서 너무 느리다. 정렬해 두면 첫 수를 하나 고정한 뒤 나머지 두 수를 양끝 투 포인터로 한 번에 좁힐 수 있어 O(n²)로 떨어진다. 정렬이 곧 투 포인터의 전제다.
• 합 sum의 부호가 곧 이동 방향이다. 정렬돼 있으니 음수면 왼쪽을 키우고(l++), 양수면 오른쪽을 줄인다(r–). 합이 0이면 트리플 하나를 확정한다.
• 까다로운 부분은 중복 제거 세 군데다. ① 첫 수 nums[i]가 직전과 같으면 건너뛰고, ② 정답을 담은 직후 둘째·셋째 수도 같은 값이 이어지는 동안 모두 건너뛴다. set 같은 추가 자료구조 없이 정렬 순서만으로 중복을 막는다.
• nums[i] > 0이면 그 뒤 값들은 모두 더 크므로 세 수의 합이 0이 될 수 없어 break로 끊는다. 큰 양수 구간을 통째로 건너뛰는 가지치기다.
• 검증: 예제 [-1,0,1,2,-1,-4] → [[-1,-1,2],[-1,0,1]], [0,1,1] → [], [0,0,0] → [[0,0,0]] 모두 통과(MSVC /std:c++17 컴파일·실행).