欢迎访问Python教程网,我们的网址www.041b.com
Python|双指针解决三数之和问题 – python教程 - python编程学习交流
Python|双指针解决三数之和问题 – python教程 - python编程学习交流

Python|双指针解决三数之和问题

admin2020-08-18 发布 python教程

这里将告诉您Python|双指针解决三数之和问题,具体操作过程:

问题描述

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

例如:nums=[-1,0,1,2,-1,-4]

输出:

[

[-1,0,1 ]

[-1,-1,2]

]

时间限制:48ms

解决方案

对于数组中数字组合的问题,最简单的方法就是遍历所有情况,然后将满足情况的组合输出。这道题的大致思路也是这样,但是还需要注意,本题要组合三个数字,如果采取for循环,需要三个这样的循环,时间复杂度是很高的,同时还遍历了很多重复项,耗时会很大,所以为满足题目的时间限制,这里介绍优于多层for循环的解题方法——双指针。

双指针思路:采取左右两个指针代替两个for循环,在第一层循环下调节指针的位置,设置判断条件就可以排除很多重复项和不满足条件的组合,最终得到满足题目的三元组。

Python代码

def threeSum(nums):

        '''

        算法思路:最外层控制一个元素的循环,内层用双指针,一个从头到尾扫描,另一个从尾到头扫描,判断三个元素的值之和是否为零       

        注意:相同的元素需要跳过

        '''

        nums.sort()# 对列表进行排序

        res = []

        k=0

        for k in range(len(nums) - 2):

            # 如果出现最小元素为正数,则不存在和为0的情况,直接返回

            if nums[k] > 0:

                break

            # 如果出现第一个元素重复的情况,为避免重复结果,跳过后续执行

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

                continue

            # 定义接下来的两个元素的双指针

            i, j = k + 1, len(nums) - 1

            while i < j:

                s = nums[k] + nums[i] + nums[j]

                if s < 0:

                    i += 1

                    # 跳过重复元素

                    while i < j and nums[i] == nums[i - 1]:

                        i += 1

                elif s > 0:

                    j -= 1

                    # 跳过重复元素

                    while i < j and nums[j] == nums[j + 1]:

                        j -= 1

                else:

                    # 当出现元素满足条件时,将结果加入到列表

                    res.append([nums[k], nums[i], nums[j]])

                    # 接着更新索引(注意跳过相同元素)

                    i += 1

                    j -= 1

                    while i < j and nums[i] == nums[i - 1]:

                        i += 1

                    while i < j and nums[j] == nums[j + 1]:

                        j -= 1

        return res

思路推广

双指针广泛用于求数组中满足一定条件的元素组合案例,该思路最大的特点就是减少循环的次数和方便去除重复项,从而减少代码耗时,优化代码。

END

主 编 | 王文星

责 编 | 饶龙江

where2go 团队

Python|双指针解决三数之和问题就为您介绍到这里.欢迎访问python自学网 www.041b.com

转载原创文章请注明,转载自: python教程 - Python|双指针解决三数之和问题 (https://www.041b.com/40095.html)

留言

写下你的评论吧

近期评论