Leetcode - 15. 3Sum

문제

주어진 배열에서 세개의 수를 골라서 더했을때 0이 되는 모든경우의 수는?
결과는 중복이 없어야함.

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

아이디어

230824 다시 풀음.

• 기본적으로 167. Two Sum II - Input Array Is Sorted 을 이용한다.
• 우선 배열을 정렬한다.
• 하나를 pick하고 나머지를 two sum으로 찾기.
• 여기까지만하면 쉬운데, 중복이 없어야한다는 조건때문에, 코드가 약간 까다로워짐.
  • 이미 지나쳐온 값은 다시 선택할 필요없음. 첫번째 값을 선택하고 나머지 값 두개는 그 오른쪽 값들 중에서 선택하면 됨.
  • [-2 -2 0 2] 인 경우, 첫번째 값을 n[0]선택할때 [-2 0 2], n[1]일때 [-2 0 2] 즉, 중복된 결과가 나옴.
    같은 값이면 skip
  • [-4 0 0 4 4] 인 경우, 첫번째 값이 n[0]일때, 나머지 값들로 two sum 2를 수행하면 [-4 0 4], [-4 0 4] 두개가 중복된 결과가 나옴.
    l의 값이 이전값과 다를때까지 l을 증가시켜야함. 아래 풀이 마지막 while문 참고.

풀이

class Solution {
public:
    // -2 0 0 2 2
    // -2 -2 0 2
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        std::sort(nums.begin(), nums.end());
        
        for (int i = 0; i < nums.size(); i++) {
            if (i > 0 && nums[i] == nums[i-1])
                continue;

            int l = i + 1, r = nums.size() - 1;
            int tgt = - nums[i];
            int sum = 0;
            
            while (l < r) {
                sum = nums[l] + nums[r];
                if (sum > tgt) {
                    r--;
                } else if (sum < tgt) {
                    l++;
                } else {
                    ret.push_back({nums[i], nums[l], nums[r]});
                    l++;
                    // for (-2) 0 0 2 2 case
                    // avoid [-2,0,2],[-2,0,2]
                    while (l < r && nums[l-1] == nums[l])
                        l++;
                }
            }
        }
        
        return ret;
    }
};

아래는 이전에 풀었던 비효율적이고 복잡한 풀이방법.

아이디어

배열값을 하나씩 선택하고 선택한 값을 제외한 값으로 two sum을 구하면 됨.
-(num[i] + num[j]) 값이 해시테이블에 존재하면 찾는것임.
해시테이블을 사용해 시간 복잡도는 O(N^2)

해결

O(N^2)으로 풀어도 아무리 개선을 해도 316 / 318 test cases passed. 까지만 맞고 TLE가 발생함. 해설을 살펴보니 첫번째 루프에서 모든 값들을 순회할 필요가 없고 중복되지 않은 값만 순회하면 되는거였다!

        std::unordered_set<int> nums_nodup;
        ...
        for (int i = 0; i < nsize; i++) {
            if (!nums_nodup.insert(nums[i]).second)
                continue;

이부분! TODO: 이코드는 해석이 필요

그리고 처음에 vector<vector>타입 리턴값 벡터에서 중복을 제거하려고 이런저런 시도를 했는데, 결국 std::set을 사용하는게 간편한 방법이라는걸 배움. ret_nodup.insert(save_target); 으로 set에 중복없이 저장한 뒤 마지막에 리턴값에 복사하는 방식으로 해결.

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        std::unordered_map<int, int> table;
        std::set<vector<int>> ret_nodup;
        std::unordered_set<int> nums_nodup;
        int nsize = nums.size();
        int sum = 0;
        
        for (int i = 0; i < nsize; i++)
            table[nums[i]]++;
        
        for (int i = 0; i < nsize; i++) {
            if (!nums_nodup.insert(nums[i]).second)
                continue;

            sum = nums[i];
            table[nums[i]]--;
            for (int j = i + 1; j < nsize; j++) {
                sum += nums[j];
                table[nums[j]]--;
                
                auto t = table.find(-sum);
                if (t != table.end()) {
                    if (t->first == -sum && t->second > 0) {
                        // found
                        std::vector<int> save_target;
                        save_target = {nums[i], nums[j], t->first};
                        std::sort(save_target.begin(), save_target.end());
                        ret_nodup.insert(save_target);
                    }
                }
                table[nums[j]]++;
                sum -= nums[j];
            }
            table[nums[i]]++;
        }
        return vector<vector<int>> (ret_nodup.begin(), ret_nodup.end());
    }
};