Problem


Key Idea

brute force ๋ฐฉ์‹์€ \(O(n^3)\)์ธ๋ฐ \(0 \le nums.length \le 3000\).
๊ณ„์‚ฐ์ด \(9 \cdot 10^9\)๋ฒˆ? (๋‹น์—ฐํžˆ) TLE๊ฐ€ ๋‚œ๋‹ค.

์ฒซ ๋ฒˆ์งธ ์ธ๋ฑ์Šค \(i\) ๋ฅผ ์ •ํ•˜๋ฉด \(num[l] + num[r] = -num[i]\)์ธ \(l, r\) ๊ฐ’์„ ์ฐพ๋Š” ๋ฌธ์ œ๋กœ ๋ณ€ํ•œ๋‹ค.

๋ฐฐ์—ด์„ ์ •๋ ฌํ•˜๊ณ  ๊ฐ \(i\)์— ๋Œ€ํ•ด two pointers๋ฅผ ์•„๋ž˜์ฒ˜๋Ÿผ ์ˆ˜ํ–‰ํ•œ๋‹ค.

๊ตฌํ˜„ํ• ๋•Œ๋Š” \(l, r\) ์ธ๋ฑ์Šค๋ฅผ ์ด๋™ํ–ˆ๋Š”๋ฐ element ๊ฐ’์ด ๊ทธ๋Œ€๋กœ๋ฉด skipํ•˜๋„๋ก ํ•ด์„œ ๋ถˆํ•„์š”ํ•œ ๊ณ„์‚ฐ์„ ์ค„์˜€๋‹ค.


Implementation

/**
 * 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());
    }
};

  • Time: \(O(n{\log}n + n^2)\)

Leave a comment