专栏首页数据分析与挖掘【python-leetcode15-双指针】三个数之和为零

【python-leetcode15-双指针】三个数之和为零

问题描述:

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

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

示例:

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

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

代码:

class Solution:
    def threeSum(self, nums):
        #数组长度
        n = len(nums)
        if (not nums or n < 3):
            return []
        #先将数组进行排序
        nums.sort()
        #保存结果
        res = []
        #从左开始遍历数组
        for i in range(n):
            #当遍历到正数时就可以返回结果了
            if (nums[i] > 0):
                return res
            #如果i>0且相邻两个值相等,则继续
            if (i > 0 and nums[i] == nums[i - 1]):
                continue
            #左指针指向i的下一位
            L = i + 1
            #右指针指向数组右端
            R = n - 1
            #循环条件
            #核心就是在第i位时,考虑从i+1位到末尾,不断通过增加左指针指向的值大小
            #和减少右指针指向的值的大小来找到一个平衡位置使三者之和为0
            while (L < R):
                #如果这三个数加起来为0
                if (nums[i] + nums[L] + nums[R] == 0):
                    #加入结果
                    res.append([nums[i], nums[L], nums[R]])
                    #此时对左指针的下一位进行判断,如果和其相同,左指针继续右移
                    while (L < R and nums[L] == nums[L + 1]):
                        L = L + 1
                    #同理,右指针继续左移
                    while (L < R and nums[R] == nums[R - 1]):
                        R = R - 1
                    #如果不相同直接左指针右移一位
                    L = L + 1
                    #如果不相同直接右指针左移一位
                    R = R - 1
                elif (nums[i] + nums[L] + nums[R] > 0):
                    #如果大于0,右指针左移一位
                    R = R - 1
                else:
                    #如果小于0,左指针右移一位
                    L = L + 1
        return res

结果:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【python-leetcode448-循环排序】找到所有数组中消失的数字

    给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组,数组中的元素一些出现了两次,另一些只出现一次。

    绝命生
  • python-快速排序

    核心思想:取一个初始值,将数组中比该值小的放在其左边,比其大的放在右边, 再对左、右子数组进行相同操作,直到数组排好序。

    绝命生
  • 【python-leetcode287-循环排序】寻找重复的数

    给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个...

    绝命生
  • 【LeetCode】面试题 10.11. 峰与谷

    在一个整数数组中,“峰”是大于或等于相邻整数的元素,相应地,“谷”是小于或等于相邻整数的元素。例如,在数组{5, 8, 6, 2, 3, 4, 6}中,{8, ...

    韩旭051
  • LeetCode 16 3Sum Closest

    ShenduCC
  • Leetcode 628. 三个数的最大乘积 (数学)

    解题思路 方法一:排序 我们将数组进行升序排序,如果数组中所有的元素都是非负数,那么答案即为最后三个元素的乘积。

    glm233
  • Leetcode 15 三数之和(双指针,去重)

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

    glm233
  • Q189 Rotate Array

    Rotate an array of n elements to the right by k steps. For example, with n = 7 a...

    echobingo
  • Array - 508. Wiggle Sort

    Given an unsorted array nums, reorder it in-place such that

    用户5705150
  • 【剑指Offer】调整数组顺序使奇数位于偶数前面

    输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。

    小新哟

扫码关注云+社区

领取腾讯云代金券