[leet_code] 15. '3Sum' TwoPointer 기법을 활용한 시간복잡도 개선

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

3Sum - LeetCode

 

세 원소를 더했을 때 Sum이 0이어야한다는 조건속에서 완전탐색이 필수적인 조건이라 생각하여, 작성한 초안 코드는 아래와 같다.

재귀호출을 통해 모든 원소를 시도하는 N^3의 코드이다.

class Solution {
public:
    void recursive_sum(const vector<int>& nums, int count_sum, int current_sum, int base_index, vector<int>& select_nums, vector<vector<int>>& results)
    {
        for (int i = base_index; i < nums.size(); ++i)
        {
            if (i > base_index && nums[i] == nums[i - 1]) continue;

            if (count_sum < 2)
            {
                int new_current_sum = current_sum + nums[i];
                auto new_select_nums = select_nums;
                new_select_nums.push_back(nums[i]);

                recursive_sum(nums, count_sum + 1, new_current_sum, i + 1, new_select_nums, results);
            }
            else
            {
                if (0 == (current_sum + nums[i]))
                {
                    results.push_back({ select_nums[0], select_nums[1], nums[i] });
                }
            }
        }
    }

    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());

        vector<vector<int>> final_result{};

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

            vector<vector<int>> results{};
            vector<int> select_nums{ nums[i] };

            recursive_sum(nums, 1, nums[i], i + 1, select_nums, results);

            for (auto& triplet : results)
            {
                final_result.push_back(triplet);
            }
        }

        return final_result;
    }
};

 

위의 코드는 테스트케이스는 통과하지만 시간초과로 제출은 실패하였다.

속도 개선을 위해서는 '정렬된 수'라는 조건을 통해서 추가적인 최적화를 거쳐야한다.

아래는 투 포인터 기법을 통해 위의 재귀호출 과정을 한번의 루프문으로 개선할 수 있다.

 

투 포인터 방식은 A + B + C = 0식에서 A 하나를 고정(nums[i])하고, 나머지B(nums[left])와 C(nums[right])를 양쪽 끝에서 좁혀오며 찾는 방식이다.

• 정렬의 역할: 배열이 오름차순 정렬되어 있으므로, 세 수의 합(sum)에 따라 포인터를 움직일 방향이 명확해진다..
  • sum < 0: 합을 늘려야 하므로 left를 오른쪽으로 이동 (더 큰 값 선택)
  • sum > 0: 합을 줄여야 하므로 right를 왼쪽으로 이동 (더 작은 값 선택)

코드는 아래와 같다.

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

        sort(nums.begin(), nums.end());
        for (int i = 0; i < n - 2; ++i) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int left = i + 1;
            int right = n - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 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 < 0) {
                    // 합이 0보다 작으면 더 큰 값이 필요하므로 left 오른쪽으로 이동
                    ++left;
                }
                else { // sum > 0
                    // 합이 0보다 크면 더 작은 값이 필요하므로 right 왼쪽으로 이동
                    --right;
                }
            }
        }

        return result;
    }
};