C++LeetCode 구현(18.4 수의 합)

[LeetCode]18.4 Sum 4 수의 합
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)
LeetCode 에서 숫자 와 다른 몇 가지 가 있 는데 각각  Two Sum  ， 3Sum  ， 3Sum Closest난이도 가 점점 높 아 지고 있 지만 전체적인 방식 은 똑 같 습 니 다.여기 서 중복 항목 을 피하 기 위해 STL 에 있 는 TreeSet 을 사 용 했 습 니 다.중복 되 지 않 는 것 이 특징 입 니 다.새로 추 가 된 숫자 가 TreeSet 에 원래 존재 하면 삽입 작업 이 실패 하고 중복 항목 의 존 재 를 잘 피 할 수 있 습 니 다.이 문제 의 O(n^3)해법 의 사고방식 과  3Sum  기본적으로 별 차이 가 없습니다.for 순환 을 한 층 더 넣 었 습 니 다.다른 것 은 모두 같 습 니 다.코드 는 다음 과 같 습 니 다.
해법 1:

class Solution {
public:
    vector<vector<int>> fourSum(vector<int> &nums, int target) {
        set<vector<int>> res;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < int(nums.size() - 3); ++i) {
            for (int j = i + 1; j < int(nums.size() - 2); ++j) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                int left = j + 1, right = nums.size() - 1;
                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        vector<int> out{nums[i], nums[j], nums[left], nums[right]};
                        res.insert(out);
                        ++left; --right;
                    } else if (sum < target) ++left;
                    else --right;
                }
            }
        }
        return vector<vector<int>>(res.begin(), res.end());
    }
};

그러나 트 리 셋 으로 중복 처 리 를 하 는 것 은 우연 한 일이 다.자바 에서 이렇게 할 수 없 을 수도 있다.그러면 비교적 정통 적 인 방법 을 살 펴 보고 수 동 으로 중복 처 리 를 하 는 것 이 좋 겠 다.주로 진행 할 수 있 는 것 은 세 가지 가 있 습 니 다.먼저 두 개의 for 순환 에서 각각 하 나 를 놓 을 수 있 습 니 다.현재 의 숫자 가 위 에서 처리 한 숫자 와 같 으 면 찾 아 보면 중복 되 기 때 문 입 니 다.그 다음 에 sum 이 target 과 같 을 때 네 개의 숫자 를 결과 res 에 추가 한 후에 left 와 right 는 모두 중복 처리 해 야 합 니 다.각각 각 방면 을 옮 겨 다 니 면 됩 니 다.코드 는 다음 과 같 습 니 다.
해법 2:

class Solution {
public:
    vector<vector<int>> fourSum(vector<int> &nums, int target) {
        vector<vector<int>> res;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n - 3; ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < n - 2; ++j) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                int left = j + 1, right = n - 1;
                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        vector<int> out{nums[i], nums[j], nums[left], nums[right]};
                        res.push_back(out);
                        while (left < right && nums[left] == nums[left + 1]) ++left;
                        while (left < right && nums[right] == nums[right - 1]) --right;
                        ++left; --right;
                    } else if (sum < target) ++left;
                    else --right;
                }
            }
        }
        return res;
    }
};

C++구현 LeetCode(18.4 수의 합)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 4 수의 합 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 도 많은 응원 부 탁 드 리 겠 습 니 다!