[Leetcode] 15. 3Sum 문제풀이

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

3Sum - LeetCode

문제 내용

배열에서 서로 다른 값 3개로 0을 만드는 원소들의 집합구하기

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

 

문제 풀이

변수 1개를 고정하면 2sum문제로 풀 수 있다.

hash를 이용해서 값이 주어지면 값에 맞는 index를 바로 가져올 수 있도록 구성했다.

중복을 방지 해야되기 때문에

hash는 같은 값이면 마지막 값의 index를 가져오게 해서 중복이 안되도록 하였다.

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        if(nums.size() < 3)
            return {};
        
        sort(nums.begin(), nums.end());
        
        map<int, int> hash;
        for (int i = 0; i < nums.size(); ++i)
            hash[nums[i]] = i;
        
        vector<vector<int>> ans;
        for (int i = 0; i < nums.size()-2; ++i) {
            for (int j = i+1; j < nums.size()-1; ++j) {
                int val = -(nums[i] + nums[j]);
                if (hash.count(val)) {
                    int k = hash[val];
                    if (j < k) {
                        ans.push_back({nums[i], nums[j], nums[k]});
                    }
                }
                j = hash[nums[j]];
            }
            i = hash[nums[i]];
        }
        return ans;
    }
};