Python 中的 3Sum

假設我們有一個數組，用來儲存 n 個整數，陣列中存在元素 a、b、c，且 a + b + c = 0。在滿足該條件的情況下，找出陣列中的所有唯一三元組。因此，如果陣列為 [-1,0,1,2,-1,-4]，結果將為 [[-1, 1, 0], [-1, -1, 2]]

為了解決這個問題，我們將遵循以下步驟 -

• 對陣列 nums 進行排序，並定義一個數組 res
• 對 i 執行範圍 0 至 nums 長度 - 3 的 for 迴圈
  • 如果 i> 0 並且 nums[i] = nums[i - 1]，則跳過下一部分並繼續
  • l := i + 1 和 r := nums 長度 - 1
  • 當 l < r 時
    • sum := nums[i]、nums[l] 和 nums[r] 的總和
    • 如果 sum < 0，則 l := l + 1，否則當 sum > 0 時，r := r - 1
    • 否則將 nums[i]、nums[l]、nums[r] 插入到 res 陣列中
    • 當 l < nums 長度 - 1 並且 nums[l] = nums[l + 1] 時
      • 將 l 增加 1
    • 當 r > 0 並且 nums[r] = nums[r - 1] 時
      • 將 r 減少 1
    • 將 l 增加 1 並將 r 減少 1
• 返回 res

示例（Python）

讓我們仔細看看以下實施方案，以便更好地理解 -

 即時演示

class Solution(object):
   def threeSum(self, nums):
      nums.sort()
      result = []
      for i in range(len(nums)-2):
         if i> 0 and nums[i] == nums[i-1]:
            continue
         l = i+1
         r = len(nums)-1
         while(l<r):
            sum = nums[i] + nums[l] + nums[r]
            if sum<0:
               l+=1
            elif sum >0:
               r-=1
            else:
               result.append([nums[i],nums[l],nums[r]])
               while l<len(nums)-1 and nums[l] == nums[l + 1] : l += 1
               while r>0 and nums[r] == nums[r - 1]: r -= 1
               l+=1
               r-=1
      return result
ob1 = Solution()
print(ob1.threeSum([-1,0,1,2,-1,-4]))

輸入

[-1,0,1,2,-1,-4]

輸出

[[-1,-1,2],[-1,0,1]]

Arnab Chakraborty

更新於： 27-4-2020

6 千+ 瀏覽量

開啟 職業生涯

完成課程，獲得認證

開始