【leetcode刷題】20T10-三數之和

• 2020 年 2 月 16 日
• 筆記

木又同學2020年第10篇解題報告

leetcode第15題：三數之和

https://leetcode-cn.com/problems/3sum/

【題目】

給定一個包含 n 個整數的數組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？找出所有滿足條件且不重複的三元組。

注意：答案中不可以包含重複的三元組。

示例：  給定數組 nums = [-1, 0, 1, 2, -1, -4]，  滿足要求的三元組集合為：  [    [-1, 0, 1],    [-1, -1, 2]  ]

【思路】

暴力解法，三層循環，判斷三數相加是否為0；要想得到唯一的三元組，還需要再次判斷。

當然可以優化，遇到時間複雜度太高的，一般可以先排個序。排序以後，即使是三層循環，第一個數大於0，由於後兩個數均大於0，不可能三數之和等於0；同理，前兩個數之和大於0，第三個數肯定大於0，三數之和也肯定不等於0。

再次優化，使用字典存儲元素及該元素在數組中最後位置。這樣，對於一組nums[p1]和nums[p2]，查找nums[p2+1:]是否存在-nums[p1]-nums[p2]只需要O(1)的複雜度，時間複雜度降為O(n^2)

本來以為OK了，但是每次判斷結果res中是否存在某個三元組，需要O(m)的時間，導致一直通不過所有case。其實，由於nums已經排序，得到的nums[p1]，nums[p2]以及p2之後的-nums[p1]-nums[p3]肯定升序排列的。因此，只要保證nums[p1]和nums[p2]不同即可。

【代碼】

python版本

class Solution(object):      def threeSum(self, nums):          """          :type nums: List[int]          :rtype: List[List[int]]          """          res = []          if len(nums) < 3:              return res            nums.sort()          # 存儲下標，降低查找的時間複雜度          d = {}          for i, n in enumerate(nums):              d[n] = i            for i in range(len(nums)-2):              # 重複元素              if i > 0 and nums[i] == nums[i-1]:                  continue              # 最小的數大於0，其餘的不用判斷              if nums[i] > 0:                  break                for j in range(i+1, len(nums)-1):                  # nums[i] + nums[j] > 0，j後續元素都大於0，不用判斷                  if nums[i] + nums[j] > 0:                      break                  if j > i+1 and nums[j] == nums[j-1]:                      continue                  if d.get(-nums[i]-nums[j], -1) > j:                      res.append([nums[i], nums[j], -nums[i]-nums[j]])          return res