前言

剛決定以后將博客同步到csnd和簡(jiǎn)書音念，考慮到將以前的博客遷移到這邊比較麻煩，就不遷移了躏敢。只同步以后的博客闷愤。
所以，如果想了解前面的博客內(nèi)容件余，請(qǐng)移步原博客

Problem

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:
The solution set must not contain duplicate quadruplets.

Examples:

Input:　nums = [1, 0, -1, 0, -2, 2], and target = 0
Output:

A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

Solutions

• 和第15題3Sum思路類似讥脐，十五題是固定一個(gè)數(shù)字，然后雙指針求三數(shù)之和啼器，這題固定兩個(gè)數(shù)字旬渠，然后雙指針求四數(shù)之和。其實(shí)原理和3Sum一樣

C++ Codes

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

Python Codes

為啥我總是不想用python再寫一遍镀首，感覺很沒意思...
附上題解里找到Python版本代碼

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        n = len(nums)
        if n < 4: return []
        nums.sort()
        res = []
        for i in range(n-3):
            # 防止重復(fù) 數(shù)組進(jìn)入 res
            if i > 0 and nums[i] == nums[i-1]:
                continue
            # 當(dāng)數(shù)組最小值和都大于target 跳出
            if nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target:
                break
            # 當(dāng)數(shù)組最大值和都小于target,說(shuō)明i這個(gè)數(shù)還是太小,遍歷下一個(gè)
            if nums[i] + nums[n-1] + nums[n-2] + nums[n-3] < target:
                continue
            for j in range(i+1,n-2):
                # 防止重復(fù) 數(shù)組進(jìn)入 res
                if j - i > 1 and nums[j] == nums[j-1]:
                    continue
                # 同理
                if nums[i] + nums[j] + nums[j+1] + nums[j+2] > target:
                    break
                # 同理
                if nums[i] + nums[j] + nums[n-1] + nums[n-2] < target:
                    continue
                # 雙指針
                left = j + 1
                right = n - 1
                while left < right:
                    tmp = nums[i] + nums[j] + nums[left] + nums[right]
                    if tmp == target:
                        res.append([nums[i],nums[j],nums[left],nums[right]])
                        while left < right and nums[left] == nums[left+1]:
                            left += 1
                        while left < right and nums[right] == nums[right-1]:
                            right -= 1
                        left += 1
                        right -= 1
                    elif tmp > target:
                        right -= 1
                    else:
                        left += 1
        return res

總結(jié)

• 雙指針用法之一：找目標(biāo)數(shù)字，四個(gè)數(shù)可以固定兩個(gè)數(shù)鼠次，另外兩個(gè)數(shù)雙指針求
• 差不多類型的題更哄，，腥寇，要學(xué)會(huì)套路