LeetCode15三数之和

发表于 | 更新于 | 分类于 |
又是双指针问题，但是双指针就需要考虑指针的移动问题，想清楚如何移动指针

题目描述：

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

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

1
2
3
4
5
6
7
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

解题思路：

这题肯定要写循环遍历数组的。

  1. 想到的第一种办法就是：遍历数组，每次都与其后面的数组进行相加，如果得到的结果的倒数，在剩余数组中能够找到，则成功。

    存在的问题：

    - 如何快速的定位两数之和的倒数仍在剩余的数组中

- 如果有重复的结果，如何有效的去重

    第一个问题，我采用的办法是使用

    list```中的```in```方法，因为list是使用线性结构存储的，其查询复杂度是$O(n)$，整个程序的时间复杂度就达到了$O(n^3)$。列表与字典的存储结构不同，字典使用Hash表结构来存储，其存取效率要高很多，时间复杂度是$O(1)​$。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19

    第二个问题，去重也是使用的```in```方法判断是否在列表其中，在其中，则不添加。

    ```python
            if len(nums) < 3:
                return []

            result = []
            for i in range(len(nums)-1):
                for j in range(i+1, len(nums)):
                    sum = nums[i] + nums[j]
                    if -sum in nums:
                        k = nums.index(-sum)
                        if k != i and k != j:
                            temp = sorted([nums[i], nums[j], nums[k]])
                            if temp not in result:
                                result.append(temp)

            return result

  2. 所以想的是，为了提高遍历效率，要考虑使用双指针。

    Tips : 一般遍历问题，都考虑一下是否可以使用双指针，然后想清楚双指针的移动条件。

    先对数组排序，使用双指针从首尾两端对数组进行遍历。每次都得到首尾两端数字的和，然后判断两数字和的倒数是否在剩余的列表切片中即可。如果在的话，则加到结果集中。如果不在的话…. 额(⊙o⊙)…是个问题。

    如果两数字之和大于0，则需要右边（大于0）的指针左移

    如果两数之和小于0…

    好像这样讲不出道理。。。GG

  3. 虽然上一种做法有问题，不过双指针的想法还是正确的。所以，应该换个思路。

    先对列表进行排序，然后从头到尾遍历。这样每次都固定住一个值，而不是用双指针来解决三值问题，好像是可行的。

    在固定一个值之后，剩下的有序列表中，用双指针法寻找两个值的和是否是固定值的负数。这样指针移动的标准也就出来了。如下图：

    • 当两值之和大于固定值的负数时，右边的指针左移
    • 当两值之和小于固定值的负数时，左边指针右移
    • 当两值之和恰好为固定值负数，保存结果。此时有个很有必要的操作：判断 start+1的值，end-1的值，是否与上一个一样，相同的话，则跳过处理，我一开始就没处理，想偷懒最后保存结果的时候去重即可，但是去重要使用
      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
      45
      46
      47
      48
      49
      50

      ### 解答：

      实现是使用的Python3写的。代码地址在GitHub，可调试：https://github.com/zhangdianlei/LeetCode_python/blob/master/src/c15.py

      实现：

      ```python
              if len(nums) < 3:
                  return []
              result = []

              nums = sorted(nums)

              for index, item in enumerate(nums):

                  target = -item
                  start = index + 1
                  end = len(nums) - 1

                  if item > 0 or nums[end] < 0:
                      break

                  if index > 0 and item == nums[index-1]:
                      continue

                  while start < end:

                      if nums[end] < 0:
                          break

                      if nums[start] + nums[end] == target:
                          temp_list = [nums[index], nums[start], nums[end]]
                          result.append(temp_list)

                          while start < end and nums[start] == nums[start+1]:
                              start = start + 1
                          while start < end and nums[end] == nums[end-1]:
                              end = end - 1

                          start = start + 1
                          end = end - 1

                      elif nums[start] + nums[end] < target:
                          start = start + 1

                      else:
                          end = end - 1

              return result