[LeetCode] C++ 15. 3Sum

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

 

문제

 

문제 분석

1. Brute force를 이용하면 문제는 풀리긴 하겠지만 분명 시간 초과가 날 것이라 생각했습니다.

2. 정렬을 한 뒤에 Two pointer를 사용하는 방식을 생각했습니다. 기준 숫자, 기준 숫자 + 1 (left), 배열의 끝(right)에서 시작을 하여 이 합이 0보다 작다면 left를 이동시키고, 0보다 크다면 right를 이동시키는 방식을 이용하면 보다 효율적으로 계산할 수 있습니다.

3. 같은 숫자를 가진 것에 대해서는 또 계산할 필요는 없기 때문에 건너뛰도록 하였습니다. 이외에도 배열 사이즈가 3보다 작던가, 이미 더이상 계산하는 것이 무의미한 케이스들에 대해서 검사하여 불필요한 계산을 줄이도록 하였습니다.

 

풀이 1

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;

        int left;
        int right;
        int size = nums.size();

        if (size < 3) return result; 

        sort(nums.begin(), nums.end());

        
        for(int i = 0; i < size - 2; ++i){
            if(i > 0 && nums[i] == nums[i-1]){
                continue;
            }

            int left = i + 1;
            int right = size - 1;

            if (left + 1 < size && nums[i] + nums[left] + nums[left + 1] > 0) break;
            if (right - 1 > 0 && nums[i] + nums[right] + nums[right - 1] < 0) continue;
    
            while(left < right){
                int sum_result = nums[i] + nums[left] + nums[right];
                if(sum_result == 0){
                    result.push_back({nums[i], nums[left], nums[right]});
                    while((left < right) && nums[left] == nums[left + 1])
                        left++;
                    
                    while((left < right) && nums[right] == nums[right - 1])
                        right--;
                    
                    left++;
                    right--;
                } else if (sum_result > 0){
                    right--;
                } else{
                    left++;
                }
                
            }
        }
        
    return result;
    }
};