[LeetCode] 15. 3Sum

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

3Sum - LeetCode

3Sum

 

int 배열(벡터)이 주어졌을때, 그 안에서 세 개를 더했을때 0 이 되는 조합을 모두 찾아내는 문제이다.

이 때, 조합은 중복이 되면 안된다.

 

2Sum 문제에서는 투 포인터를 이용해 문제를 해결한다.

먼저 배열을 오름차순으로 정렬한 후, 왼쪽끝과 오른쪽끝을 포인터로 두고,

target보다 클 경우 오른쪽 포인터를 --, 작을 경우 왼쪽포인터를 ++ 해준다.

세개를 더하는 문제도 첫번째 수를 고정시켜놓으면 2Sum 문제와 같다.

중복체크만 주의하자.

 

전체 풀이 코드

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        set<vector<int>> chk;
        if (nums.size()<3) return ret;
        sort(nums.begin(), nums.end());
        for (int i=0; i<nums.size()-2; i++) {
            int l=i+1, r=nums.size()-1;
            while (l<r) {
                if (nums[l] + nums[r]==-nums[i]) {
                    if (chk.find({nums[i],nums[l],nums[r]})==chk.end()) {
                        ret.push_back({nums[i],nums[l],nums[r]});
                        chk.insert({nums[i],nums[l],nums[r]});
                    }
                    l++;
                    r--;
                } else if (nums[l] + nums[r]>-nums[i]) r--;
                else l++;
            }
        }
        return ret;
    }
};