← 전체 글로 돌아가기
competitive-programming2021년 12월 31일1분 분량

[LeetCode] 15. 3 Sum 풀이

수정일: 2021년 12월 31일

Two pointers
지원 언어:enko

#Problem

15. 3 Sum

#Approach

brute force 방식은 O(n3)O(n^3)인데 0≤nums.length≤30000 \le nums.length \le 3000.
계산이 9⋅1099 \cdot 10^9번? (당연히) TLE가 난다.

첫 번째 인덱스 ii 를 정하면 num[l]+num[r]=−num[i]num[l] + num[r] = -num[i]인 l,rl, r 값을 찾는 문제로 변한다.

배열을 정렬하고 각 ii에 대해 two pointers를 아래처럼 수행한다.

구현할때는 l,rl, r 인덱스를 이동했는데 element 값이 그대로면 skip하도록 해서 불필요한 계산을 줄였다.

#Code

/**
 * written: 2021. 12. 31. Fri. 16:46:01 [UTC+9]
 * jooncco의 mac에서.
 **/

typedef vector<int> vi;
typedef vector<vi> vvi;

class Solution {
public:
    vvi threeSum(vi &nums) {
        int n= nums.size();
        if (n < 3) return vvi();

        // 오름차순 정렬
        sort(nums.begin(), nums.end());

        // 순회하면서 two pointers를 수행
        set<vi> ans;
        for (int i=0; i < n-2; ++i) {
            int l= i+1, r= n-1;
            while (l < r) {
                if (nums[i] + nums[l] + nums[r] == 0) {
                    ans.insert({nums[i], nums[l], nums[r]});
                }

                if (nums[i] + nums[l] + nums[r] > 0) {
                    // 같은 값 skip
                    while (l < r-1 && nums[r-1] == nums[r]) --r;
                    // r을 왼쪽으로
                    --r;
                }
                else {
                    // 같은 값 skip
                    while (l+1 < r && nums[l] == nums[l+1]) ++l;
                    // l을 오른쪽으로
                    ++l;
                }

            }
        }
        return vvi(ans.begin(), ans.end());
    }
};

#Complexity

  • Time: O(nlog⁡n+n2)O(n{\log}n + n^2)
  • Space: O(n)O(n)