【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:

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

Related Topics: Array、Two Pointers

解題邏輯與實作

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

但這樣做會有兩個問題：

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

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

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

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

處理完固定值數字後，先計算差值（用 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

解題邏輯與實作

其他連結