###### tags: `Leetcode` `medium` `pointer` `python`

# 18. 4Sum

## [題目來源:] https://leetcode.com/problems/4sum/

## 題目:
Given an array ```nums``` of ```n``` integers, return an array of all the ```unique``` quadruplets ```[nums[a], nums[b], nums[c], nums[d]]``` such that:

* 0 <= a, b, c, d < n
* a, b, c, and d are distinct.
* nums[a] + nums[b] + nums[c] + nums[d] == target
* You may return the answer in any order.

**Example 1:**

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

**Example 2:**

Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]

## 解題想法:
兄弟題目: [15. 3Sum](/FLggbFKASMqFH3GYi9wSsg) 、[16. 3Sum Closest](/-2KGuo22S3qNrqbNTpvC_w)

* 四個數字和為target，且組合不能重複
* 數組先排好
* 雙迴圈
* 第一圈:固定i
* 第二圈:固定j=i+1
* k=j+1
* l=len(nums)-1
* i、j、k、l都需注意是否與自己的前一個重複

## Python:

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        nums.sort()
        res = []
        #兩個for固定ij
        #兩個pointer去跑kl
        for i in range(len(nums)-3):
            #去除重複
            if i>0 and nums[i]==nums[i-1]:
                continue
            for j in range(i+1,len(nums)-2):
                #去除重複
                if j>i+1 and nums[j]==nums[j-1]:
                    continue
                k = j+1
                l = len(nums)-1
                while k<l:
                    sum = nums[i]+nums[j]+nums[k]+nums[l]
                    if sum==target:
                        res.append([nums[i],nums[j],nums[k],nums[l]])
                        k+=1
                        l-=1
                        #去除重複
                        while k<l and nums[k]==nums[k-1]:
                            k+=1
                        while k<l and nums[l]==nums[l+1]:
                            l-=1
                    #和過大
                    elif sum>target:
                        l-=1
                    else:
                        k+=1
        return res
                    
if __name__ == '__main__':
    nums = [2,2,2,2,2]
    target = 8
    result = Solution()
    ans = result.fourSum(nums,target)
    print(ans)