# LC 18. 4Sum

### [Problem link](https://leetcode.com/problems/4sum/)

###### tags: `leedcode` `medium` `python` `c++` `Two Pointer`

Given an array <code>nums</code> of <code>n</code> integers, return an array of all the **unique** quadruplets <code>[nums[a], nums[b], nums[c], nums[d]]</code> such that:

- <code>0 <= a, b, c, d< n</code>
- <code>a</code>, <code>b</code>, <code>c</code>, and <code>d</code> are **distinct** .
- <code>nums[a] + nums[b] + nums[c] + nums[d] == target</code>

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]]

**Constraints:**

- <code>1 <= nums.length <= 200</code>
- <code>-10⁹ <= nums[i] <= 10⁹</code>
- <code>-10⁹ <= target <= 10⁹</code>

## Solution 1 - Two Pointer
#### Python

# Mar 22, 2023
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        res = []

        for i in range(n):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            for k in range(i + 1, n):
                if k > i + 1 and nums[k] == nums[k - 1]:
                    continue
                left = k + 1
                right = n - 1

                while left < right:
                    tmp_sum = nums[i] + nums[k] + nums[left] + nums[right]
                    if tmp_sum == target:
                        res.append([nums[i], nums[k], nums[left], nums[right]])
                        while left + 1 < right and nums[left] == nums[left + 1]:
                            left += 1
                        while left < right - 1 and nums[right] == nums[right - 1]:
                            right -= 1
                    if tmp_sum > target:
                        right -= 1
                    else:
                        left += 1

        return res

#### C++

//  Nov 20, 2023
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        if (nums.size() < 4) {
            return res;
        }

        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size() - 3; i++) {
            if (nums[i] > target && nums[i] >= 0) {
                break;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < nums.size() - 2; j++) {
                if (nums[i] + nums[j] > target && nums[i] + nums[j] > 0){
                    break;
                }
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                int left = j + 1;
                int right = nums.size() - 1;
                while (left < right) {
                    long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum < target) {
                        left++;
                    } else if (sum > target) {
                        right--;
                    } else {
                        res.push_back({nums[i], nums[j], nums[left], nums[right]});
                        while (left < right - 1 && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        while (left < right - 1 && nums[right] == nums[right - 1]) {
                            right--;
                        }
                        left++;
                        right--;
                    }
                }
            }
        }
        return res;
    }
};

>### Complexity
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O($n^3$) | O($n^3$) |

## Note
[reference](https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0018.%E5%9B%9B%E6%95%B0%E4%B9%8B%E5%92%8C.md)

從3sum修該一下就可以變4sum了, 優化了reference的寫法, 我覺得這樣寫法更好.