【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