[leetcode] 18. 4 Sum 문제 풀이 보고서

제목 링크:https://leetcode.com/problems/4sum/
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:
Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
The solution set must not contain duplicate quadruplets.

    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)

사고방식: 가장 직접적인 방법 은 DFS 폭력 검색 이다. 시간의 복잡 도 는 O (n ^ 4) 이다. 이런 방식 은 시간 을 초과 할 수 있 기 때문에 우 리 는 다른 방법 을 찾 아야 한다.
첫 번 째 와 두 번 째 수 를 매 거 한 다음 에 세 번 째 네 번 째 수 를 찾 는 문 제 는 2sum 의 문제 가 되 었 다.
2sum 문제 에서 우리 의 목 표 는 두 개의 수의 합 과 같은 주어진 수 를 찾 는 것 입 니 다. 그래서 우 리 는 좌우 포인터, left = 0, right = len - 1 을 사용 해 야 합 니 다.좌우 지침 을 사용 하려 면 배열 이 질서 가 있어 야 하기 때문에 우 리 는 먼저 배열 을 정렬 해 야 한다.
좌우 포인터 의 이동 규칙 은:
1. 현재 nums [left] + nums [right] > target 이 우리 가 target 과 같 게 하려 면 right 포인터 가 한 자 리 를 왼쪽으로 옮 겨 야 합 니 다. 현재 와 너무 크기 때 문 입 니 다.
２. 현재 nums [left] + nums [right] < target, 우리 가 target 과 같 게 하려 면 left 포인터 가 오른쪽으로 한 자 리 를 옮 겨 야 합 니 다. 현재 와 너무 작 기 때 문 입 니 다.
3. 현재 nums [left] + nums [right] = target 이면 결 과 를 저장 하고 좌우 바늘 을 한 번 씩 이동 할 수 있 습 니 다.그리고 주의해 야 할 것 은 무 거 운 것 을 제거 하 는 것 입 니 다. 만약 nums [left + 1] = nums [left] 또는 nums [right - 1] = nums [right],
이 값 을 건 너 뛰 어야 합 니 다. 이 방안 들 은 모두 검색 되 었 기 때 문 입 니 다.
네, 생각 은 아마 이 겁 니 다. 4sum 은 2sum 보다 첫 번 째 와 두 번 째 숫자 도 무 거 운 절 차 를 밟 아야 합 니 다.이 시간 복잡 도 는 O (n ^ 3) 입 니 다.
코드 는 다음 과 같 습 니 다:

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int len = nums.size(), i = 0;
        while(i < len -3)//      
        {
            int j = i+1;
            while(j < len -2)//      
            {
                int left = j+1, right = len-1;
                while(left < right)//        
                {
                    int val = nums[i] + nums[j] + nums[left] + nums[right];
                    if(val < target) left++;
                    else if(val > target) right--;
                    else if(nums[i] + nums[j] + nums[left] + nums[right] == target)//      
                    {
                        vector<int> tem;
                        tem.push_back(nums[i]);
                        tem.push_back(nums[j]);
                        tem.push_back(nums[left]);
                        tem.push_back(nums[right]);
                        result.push_back(tem);
                        while(nums[left+1] == nums[left]) left++;//  
                        while(nums[right-1] == nums[right]) right--;
                        left++;
                        right--;
                    }
                }
                
                while(nums[j+1] == nums[j]) j++;//       
                j++;
            }
            while(nums[i+1] == nums[i]) i++;//       
            i++;
        }
        return result;
    }
private:
    vector<vector<int>> result;
};