【LeetCode最详尽解答】15-三数之和 3sum

欢迎收藏Star我的Machine Learning Blog:https://github.com/purepisces/Wenqing-Machine_Learning_Blog。如果收藏star, 有问题可以随时与我交流, 谢谢大家！

链接:

• 15-三数之和

直觉

示例:

输入: nums = [-1, 0, 1, 2, -1, -4]

输出: [[-1, -1, 2], [-1, 0, 1]]

解释:

nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0。

nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0。

nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0。

不同的三元组是 [-1, 0, 1] 和 [-1, -1, 2]。

注意输出的顺序和三元组的顺序无关。

首先，我们应该记住，解决方案集不得包含重复的三元组。考虑这个示例 [-3, 3, 4, -3, 1, 2]，我们需要找到 _+_+_ = 0。如果我们先看索引 0，那么它将填充 -3(索引[0]) + 1 + 2 = 0。但是，当我们到达索引 3 时，它仍然具有相同的组合，即 -3(索引[3]) + 1 + 2 = 0。这就是重复的。因此，我们可以首先对数组进行排序来处理它。在这种情况下，它将排序为 [-3, -3, 1, 2, 3, 4]，当我们遇到第二个 -3 时，我们可以跳过它。

对于 _+_+_ = 0，当我们选择第一个元素时，我们需要在剩余排序数组中找到两个元素，它们的和等于负的第一个元素值。然后它转换为一个两数之和的问题，类似于问题 167-两数之和 II-输入数组已排序，即在排序数组中找到两个数的和。在此示例中，排序后的数组将变为 [-4, -1, -1, 0, 1, 2]，我们应该遍历整个数组，找到 -4 + [-1, -1, 0, 1, 2] = 0，然后 -1 + [-1, 0, 1, 2] = 0，然后跳过第二个 -1，然后 0 + [1, 2] = 0，等等。

当我们遍历整个数组时，我们还应该添加一些基本情况。如果 nums[i] > 0，那么我们中断，因为数组是递增顺序的。如果 nums[i] == nums[i-1]，我们应该继续循环，因为如果我们不进行此操作，答案将重复。考虑 [-1, -1, 0, 1, 2]。对于第一个 -1，它将有 [-1, -1, 2] 和 [-1, 0, 1]。对于第二个 -1，它也将有 [-1, 0, 1]，这会重复答案。因为第一个 -1 的剩余数组包含了第二个 -1 的剩余数组。

然后我们可以处理这个问题。让两个指针指向剩余数组的开始和结束位置：左指针为 i + 1，右指针为数组的末尾位置。如果这三个值小于 0，那么将 l 向右移动。如果这三个值大于 0，那么将 r 向左移动。否则，我们可以将这三个值追加到结果中。之后，我们应该增加左指针并减少右指针，因为数组不仅包含一个解决方案。然而，为了避免重复的解决方案，我们还需要做一个额外的步骤。考虑 -1[0, 0, 0, 1, 1]。如果 left+1，我们移动到第二个 0 和第一个 1。那么，因为第二个 0 与第一个 0 是相同的值，我们不能将其视为额外的解决方案。我们应该继续将左指针向右移动且不超过右指针。最后，左指针将位于第一个 1，与右指针在同一位置，它将不会进入 while l < r 循环，结果不会追加它。

方法

1. 对数组进行排序。
2. 遍历排序后的数组，对于每个索引，将剩余元素转换为两数之和问题。
3. 通过在处理两数之和问题时检查 nums[l] == nums[l-1]，以及在选择基值时检查 nums[i] == nums[i-1] 来避免重复的解决方案。
4. 最后，返回结果。

复杂度

• 时间复杂度:
  $$O(n^2)$$
  • 对数组进行排序需要 $O(n\log n)$，并且在循环中使用双指针方法需要 $O(n^2)$，

复杂度

• 时间复杂度:
  $$O(n^2)$$

  • 对数组进行排序需要 $O(n\log n)$，并且在循环中使用双指针方法需要 $O(n^2)$，因此总体时间复杂度为 $O(n^2)$。

• 空间复杂度:
  $$O(n)$$

  • 如果不考虑用于存储输出的空间，空间复杂度为 $O(1)$。排序是就地完成的，只使用常量量的额外空间。

代码

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        result = []
        for i in range(len(nums)):
            if nums[i] > 0:
                break
            if i > 0 and nums[i] == nums[i-1]:
                continue
            l = i+1
            r = len(nums) - 1
            while l < r:
                if nums[i] + nums[l] + nums[r] < 0:
                    l+=1
                elif nums[i] + nums[l] + nums[r] > 0:
                    r-=1
                else:
                    result.append([nums[i], nums[l], nums[r]])
                    l+=1
                    r-=1
                    while nums[l] == nums[l-1] and l < r:
                        l+=1
        return result