【LeetCode】0015. 3Sum

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.


Note: The solution set must not contain duplicate triplets.


Example 1:

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


Related Topics: ArrayTwo Pointers



解題邏輯與實作

這題是求三數之和為 0,難到題目的瞬間立刻想到之前做過的 Two Sum,所以在一開始我先固定一個數字,那接下來的作法就跟 Two Sum 一樣了。

但這樣做會有兩個問題:

  1. 是答案會出現同結果
  2. 是很容易 Time Limit Exceeded。

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


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

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


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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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. 解題目錄