---
title: 【LeetCode】0015. 3Sum
date: 2019-06-11
is_modified: false
disqus: cynthiahackmd
categories:
- "面試刷題"
tags:
- "LeetCode"
---

{%hackmd @CynthiaChuang/Github-Page-Theme %}

<br>

Given an array `nums` of _n_ integers, are there elements _a_, _b_, _c_ in `nums` such that _a_+ _b_ + _c_ = 0? Find all unique triplets in the array which gives the sum of zero.

<!--more-->
<br>

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

<br>

**Example 1:**

Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

<br>

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

## 解題邏輯與實作
這題是求三數之和為 0，難到題目的瞬間立刻想到之前做過的 [Two Sum](/vRcWrdrJRw-ZHjABFOAgGg)，所以在一開始我先固定一個數字，那接下來的作法就跟 Two Sum 一樣了。

但這樣做會有兩個問題：
1. 是答案會出現同結果
2. 是很容易 Time Limit Exceeded。

看來這題並不期望我們用 Two Sum 的解法來實做。

<br> 所以這邊改變了一下實做方法，一樣先對陣列依序尋訪，以選擇一個固定數字作為計算起始，只是需要稍微注意一下尋訪到**倒數第三個元素**就應該停止了。

另外為了方便進行剪枝及流程的優化，在尋訪前應先對陣列由小到大進行排序，如果排序結果第一個數為正數或最後一個數為負數，可以直接回傳空陣列，因為若第一個數為正，在陣列已排序的情況下，在其之後的數必為正，因此不可能找出三數之合為 0 的答案；最後一個數為負數也是同樣的情況，在其之前也都是負數，也不可能找到三數之合為 0 的答案。另外，在尋訪時也是，一旦我們固定的數字為正數可以直接中止了。除了剪枝外，還需要做避免重複的處理，一旦與先前的數字相同就跳過處理。

<br> 處理完固定值數字後，先計算差值（用 0 減掉這個固定數字），並在剩餘的陣列使用兩個指針分別指向剩餘陣列的頭尾，若和大於差，則移動右邊指標；反之，則移動左邊；若指針指向的兩數合等於差值，則這三個數字記入答案，記入後左右指標都移動，只是移動前先做避免重複的處理，將指標先移到連續相同值得最末端，完整程式碼如下：

class Solution:
   def threeSum(self, nums: List[int]) -> List[List[int]]:
      nums.sort()
      if not nums   or (nums[0] > 0 or nums[-1] < 0) :
         return []


      length = len(nums)
      answers = []

      for first_idx, first in enumerate(nums[:-2]):
         if first > 0 :
            break 

         if first_idx > 0 and first == nums[first_idx-1]:
            continue


         diff = 0 - 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([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

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

<br><br>

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