[LeetCode] 3Sum

문제 설명

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

제한사항

• 3 <= nums.length <= 3000
• $-10^5$ <= nums[i] <= $10^5$

---

풀이

실패
map 자료구조를 이용해서 (더한값) : (index 1, index 2) 의 형태로 모두 저장해둔 뒤,
배열을 순회하며 (배열값 * -1)를 Key로 나머지 두 인덱스를 찾아 3개의 인덱스를 정렬하여 쌓아두고, 아래의 방법으로 중복을 제거하였는데,

sort(res.begin(), res.end());
res.erase(unique(res.begin(), res.end()), res.end());

이 방식으로는 시간 제한을 통과하지 못하는 테스트 케이스가 있었다. 이 문제의 핵심은 중복을 피하는 방법임을 늦게 알아차렸다. 다른 사람의 풀이를 참고해보니 map을 사용하지 않고 푸는 방식도 있어서 참고하여 풀이하였고, map 방식으로도 중복을 피하는 방법에 대한 힌트를 찾아서 다시 풀어보았다.
정렬된 vector에 대해서 map에 index를 업데이트 하다보면 같은 값에 대해서는 마지막 원소에 대한 index가 저장되므로, 이를 고려하여 loop문을 짜면 중복으로 조합하는 것을 피할 수 있다.

코드

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        
        sort(nums.begin(), nums.end());
        
        for(int i = 0; i < nums.size(); ++i){
            int target = nums[i] * -1;
            int left = i + 1,right = nums.size() - 1;
            
            while(left < right){
                int sum = nums[left] + nums[right];
                
                if(sum < target){
                    left += 1;
                } else if(sum > target){
                    right -= 1;
                } else{
                    res.push_back({nums[i],nums[left],nums[right]});
                    int left_num = nums[left], right_num = nums[right];
                    
                    while(left < right && nums[left] == left_num) left += 1;
                    while(left < right && nums[right] == right_num) right -= 1;
                }
            }
            while(i < nums.size() - 1 && nums[i + 1] == nums[i]) i += 1;
        }
        
        return res;
    }
};

다른 코드

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        map<int, int> m;
        
        sort(nums.begin(), nums.end());
        
        for(int i = 0; i < nums.size(); ++i){
            m[nums[i]] = i;
        }
        
        for(int i = 0; i < nums.size(); ++i){
            for(int j = i + 1; j < nums.size(); ++j){
                int twosum = nums[i] + nums[j];
                if(m.find(twosum * -1) != m.end() && m[twosum * -1] > j){
                    res.push_back({nums[i], nums[j], twosum * -1});
                }
                j = m[nums[j]];
            }
            i = m[nums[i]];
        }
        
        return res;
    }
};