본문 바로가기
leetcode

leetcode 15 - 3Sum

by 초특급하품 2020. 10. 29.

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

풀이

nums[i] + nums[j] + nums[k] = 0을 만족하는 i, j, k를 찾는 문제이다.

여러 가지 풀이 방법이 있는 2 sum을 n번 돌리면 되는 것 같아 보이지만 output이 중복을 제거한 정답들의 리스트라는 점에서 제약이 생긴다. 

 

먼저 nums를 정렬을 하고 i < j < k 인 순서대로 답을 찾아보자. j = i+1, k = nums.size()-1로 두 개의 포인터를 초기화를 한 후 아래 조건대로 j, k를 움직인다.

  1. nums[i] + nums[j] + nums[k] < 0  →  j를 증가
  2. nums[i] + nums[j] + nums[k] > 0  → k를 감소

이렇게 j와 k를 좁히다가 nums[i] + nums[j] + nums[k] = 0인 인덱스를 발견하면 중복처리를 시작한다. 중복처리는 답을 찾은 순간 j와 k 중 아무 거나 하나를 잡고 중복이 제거될 때까지 좁히면 된다.

 

set을 사용해도 2 sum은 쉽게 구할 수 있다. 여기에 추가로 중복 제거를 하기 위해서 어떤 값이 정답으로 사용됐는지 따로 저장하는 set을 둬서 한번 더 검증한다.

 

 

코드

두 개의 포인터

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        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;

            while(l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if(sum == 0) {
                    ans.push_back({ nums[i], nums[l], nums[r] });
                    while(l < nums.size() - 1 && nums[l] == nums[l+1]) l++;
                    l++;
                }
                else if(sum < 0) l++;
                else r--;
            }
        }
        return ans;
    }
};

 

set으로 중복검사

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end()); 
        
        for(int i = 0; i < nums.size(); i++) {
            if(i > 0 && nums[i] == nums[i-1]) continue;
            
            unordered_set<int> check, s;
            for(int j = i+1; j < nums.size(); j++) {
                if(check.find(nums[j]) == check.end() && s.find(-nums[i]-nums[j]) != s.end()) {
                    ans.push_back({ nums[i], nums[j], -nums[i]-nums[j] });
                    check.insert(nums[j]);
                    check.insert(-nums[i]-nums[j]);
                }
                s.insert(nums[j]);
            }
        }
        return ans;
    }
};

 

댓글