---
title: 【LeetCode】0018. 4Sum
date: 2019-06-17
is_modified: false
disqus: cynthiahackmd
categories:
- "面試刷題"
tags:
- "LeetCode"
---

{%hackmd @CynthiaChuang/Github-Page-Theme %}
<br>

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`.

<!--more-->
<br>

> **Note:**
>The solution set must not contain duplicate quadruplets.

<br>

**Example 1:**

Given array nums = [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]
]

<br>

**Related Topics:** `Array`、`Two Pointers`、`Hash Table`

## 解題邏輯與實作

### Two Pointers
我這題一開始直接偷懶使用 [3Sum](/XXy3Mz4DToygP2t_0ljjLA) 來回作答。

class Solution:
   def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
      nums.sort()
      length = len(nums)
      answers = []
      for head_idx, head in enumerate(nums[:-3]):
         if head_idx > 0 and head == nums[head_idx-1]:
            continue
                        
         self.threeSum(nums[head_idx+1:], target-head, head, answers)                  
      return answers
            
   def threeSum(self, nums: List[int], target: int, head: int, answers:List[List[int]]) -> List[List[int]]:
      if not nums:
         return []

      length = len(nums) 

      for first_idx, first in enumerate(nums[:-2]):
         if first_idx > 0 and first == nums[first_idx-1]:
            continue


         diff = target - first
         second_idx = first_idx + 1
         third_idx = length -1	

         while(second_idx < third_idx): 
            second =   nums[second_idx] 
            third = nums[third_idx]
                              
            summation = second + third   

            if summation < diff:
                second_idx += 1
            elif summation > diff:
                third_idx -= 1
            else:				
                answers.append([head, first,second,third]) 
                while(second_idx < third_idx and nums[second_idx] == nums[second_idx+1]):
                   second_idx += 1

                while(second_idx < third_idx and nums[third_idx] == nums[third_idx-1]):
                   third_idx -= 1

                second_idx += 1
                third_idx -= 1

      return answers

結果比我想像中好一點，我原本預期會超時，不過也沒好到哪裡去就是了只跑出了 **804 / 47.58%**。

<br>

上面這個勉強算是 Two Pointers ，但這題的 Tag 中還有一個 Hash Table 解法，先欠著吧，我好想睡 Orz

## 其他連結
1. [【LeetCode】0000. 解題目錄](/x62skqpKStKMxRepJ6iqQQ)

<br><br>

> **本文作者**： 辛西亞．Cynthia
> **本文連結**： [辛西亞的技能樹](https://cynthiachuang.github.io/LeetCode-0018-4Sum) / [hackmd 版本](https://hackmd.io/@CynthiaChuang/LeetCode-0018-4Sum)
> **版權聲明**： 部落格中所有文章，均採用 [姓名標示-非商業性-相同方式分享 4.0 國際](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.en) (CC BY-NC-SA 4.0) 許可協議。轉載請標明作者、連結與出處！