leetcode 015. 三数之和

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

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

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

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

CODE:

class Solution:
    def threeSum(self, nums):
        nums.sort() # 先排序
        n = len(nums)
        left = 0
        right = n - 1
        results = []
        # 固定一个数,另外2个数从两边夹,3个数的和大于0,右边最大值就减少,如果小于0,左右最大值就增加
        # 固定数如果相同的话(因为排序位置会在一起),结果可能会相同,所以直接跳过
        for index in range(0, n):
            if index >= 1 and nums[index] == nums[index - 1]:
                continue
            # 左边从固定数右边最小值开始,右边从最大值开始
            left, right = index + 1, n - 1
            while left < right:
                total = nums[left] + nums[index] + nums[right]
                if total == 0:
                    results.append([nums[index], nums[left], nums[right]])
                    # 如果和为0,左右各前进一步,如果只变left,right其中一个,由于left,index固定,3个数和固定,那么right肯定固定,所以左右都要变
                    left += 1
                    right -= 1
                    # 左右前进的时候,如果前进后的值和原值相同则需要继续前进,不然会重复
                    # 如:[-2, 0, 0, 2, 2],a: index(0,1,4), b:index(0, 2, 3)都是[-2,0,2]会重复
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1
                elif total > 0:
                    right -= 1
                else:
                    left += 1
        return results


su = Solution()
nums = [-2, 0, 0, 2, 2]
res = su.threeSum(nums)
print(res)
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 题目 给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b...
    多彩海洋阅读 169评论 1 1
  • 专业考题类型管理运行工作负责人一般作业考题内容选项A选项B选项C选项D选项E选项F正确答案 变电单选GYSZ本规程...
    小白兔去钓鱼阅读 9,059评论 0 13
  • 1. 两数之和 题目描述 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那...
    黄昏隐修所阅读 661评论 0 0
  • 选择题部分 1.(),只有在发生短路事故时或者在负荷电流较大时,变流器中才会有足够的二次电流作为继电保护跳闸之用。...
    skystarwuwei阅读 13,485评论 0 7
  • 在C语言中,五种基本数据类型存储空间长度的排列顺序是: A)char B)char=int<=float C)ch...
    夏天再来阅读 3,421评论 0 2