15. 三数之和

描述

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

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

示例

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

满足要求的三元组集合为：

[

  [-1, 0, 1],

  [-1, -1, 2]

]

思路

思路一

这种数值列表中有加减的题目，排序后可能会更加方便些。

固定两个数，将 target 设置为两个数之和的相反数，看 target 是否在列表中，若在，则为一个结果。

class Solution:

    def threeSum(self, nums):

        """

        :type nums: List[int]

        :rtype: List[List[int]]

        """

        ret = []

        # 数组题，其中有加减操作的，排序后会方便很多

        nums.sort()

        len_nums = len(nums)

        for i in range(len_nums - 1):

            for j in range(i+1, len_nums):

                # 固定下来两个数，如果另外一个数也在数组中，则为一个结果

                if -(nums[i]+nums[j]) in nums[j+1:]:

                    a_ret = [nums[i], nums[j], -(nums[i]+nums[j])]

                    if a_ret not in ret:

                        ret.append(a_ret)

        return ret

但是这种方法有两层循环，果然报了 TLE（Time Limit Exceeded）错误。

思路二

固定一个数，设置 target 为其他两个数之和的相反数，即 0 - 当前数，由两头向中间遍历数组，找到之和符合 target 的两个数即是一个结果。

class Solution:

    def threeSum(self, nums):

        """

        :type nums: List[int]

        :rtype: List[List[int]]

        """

        ret = []

        nums.sort()

        for i in range(0, len(nums)):

            # 若存在相同数，跳过以减少计算

            if i > 0 and nums[i] == nums[i-1]:

                continue

            target = 0 - nums[i]

            start, end = i+1, len(nums)-1

            while start < end:

                # 头尾之和大于目标值，尾向前移一位

                if nums[start] + nums[end] > target:

                    end -= 1

                # 头尾之和小于目标值，头向后移一位

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

                    start += 1

                # 头尾之和等于目标值，是一个结果，添加进去

                # 头尾都移动一位

                else:

                    ret.append([nums[i], nums[start], nums[end]])

                    start += 1

                    end -= 1

                    # 若移动后有重复值，继续移动

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

                        start += 1

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

                        end -= 1

        return ret

GitHub地址：https://github.com/protea-ban/LeetCode

巴特西

LeetCode15. 三数之和

15. 三数之和

描述

示例

思路

思路一

思路二

最新文章

热门文章