15. 3Sum

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

3Sum - LeetCode

 

정수의 목록이 주어졌을 때, 3개의 정수를 더했을 경우 0이 되는 목록을 2차원 배열에 담아 반환하는 문제다.

단순히 생각하면 O(N^3)이지만 O(N^2)로 낮추는게 핵심인것 같다.

 

일단 받은 정수의 목록을 오름차순으로 정렬해놓고, 첫번째 숫자부터 끝까지 반복하며 나머지 목록을 검사한다.

case를 반환하는 문제기 때문에 중복들은 전부 건너뛰어야 한다.

덧셈할 1,2,3번째 정수 모두 중복은 제외한다.

 

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        vector<int> v;
        v.resize(3);
        
        sort(nums.begin(), nums.end());
        
        for (int i=0; i<nums.size(); ++i)
        {
            // case를 찾는 문제에서 똑같은걸 굳이 재검사 할 필요 없음
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            
            int l = i + 1;
            int r = nums.size() - 1;

            while (l < r)
            {
                int s = nums[i] + nums[l] + nums[r];
                if (s < 0) {
                    ++l;
                }
                else if (s > 0) {
                    --r;
                }
                else
                {
                    v[0] = nums[i];
                    v[1] = nums[l];
                    v[2] = nums[r];
                    ret.push_back(v);
                    
                    // case를 찾는 문제에서 동일한건 재검사 할 필요 없음
                    // && 이전 조건은 [0,0,0] 케이스 문제 발생 수정
                    while (l < r && nums[l] == nums[l+1]) {
                        ++l;
                    }
                    while (l < r && nums[r] == nums[r-1]) {
                        --r;
                    }

                    ++l;
                    --r;
                }
            }
        }
        
        return ret;
    }
};