Python三数之和的实现方式

2024-04-11 18:26:52

三数之和题目描述

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，

使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

答案中不允许包含重复的三元组。

示例：

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

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

[
  [-1, 0, 1],
  [-1, -1, 2]
]

思路

1. 首先将数组排序，可以利用Python内置函数，也可以利用另外定义排序算法。

2. 应用双指针算法。固定第一个数,索引为i，遍历整个数组，第一个数也是三个数中最小的数，然后在该数右面设置左右两个指针l和r,l=i+1，r=len(nums)-1,

3. 判断这三个索引指向的元素和与0的大小关系。

和>0,右指针左移一位；和<0，左指针右移一位。

由于要避免重复的三元组，所以移动左右指针的时候要跳过相邻的所有相等的nums[i]。

Python3代码

#导入计算时间的包，调用系统时间
from time import *
#初始时间
t1 = time()
def threeSum(nums):
    nums.sort()
    n = len(nums)
    res = []
    for i in range(n):
        '''如果相邻的两个数相等，跳过,避免重复'''
        if i > 0 and nums[i] == nums[i-1]:
            continue
        l, r = i+1, n-1
        while l < r:
            if nums[i] + nums[l] + nums[r]>0:
                r -= 1
                while nums[r+1] == nums[r]:
                    r -= 1
            elif nums[i] + nums[l] + nums[r]<0:
                l += 1
                while nums[l-1] == nums[l]:
                    l += 1
            else:
                res.append([nums[i],nums[l],nums[r]])
                l += 1
                r -= 1
                while nums[l] == nums[l - 1]: l += 1
                while nums[r] == nums[r + 1]: r -= 1
    return res

if __name__ == '__main__':
    nums = [-1,0,1,2,-1,-4]
    print(threeSum(nums))
#结束时间
t2 = time()
#运行时间
run_time = t2 - t1
print(run_time)

运行结果：

[[-1, -1, 2], [-1, 0, 1]]
#运行时间
0.0010113716125488281

以上代码有一些思想错误：

遗漏了如果三个数全部大于0，则退出循环，因为没有满足条件的结果。

没有严格判断每一次的l<r的条件。

修正后的代码：

from time import *
t1 = time()
def threeSum(nums):
    nums.sort()
    n = len(nums)
    res = []
    for i in range(n-2):
        if nums[i] > 0:break
        '''如果相邻的两个数相等，跳过,避免重复'''
        if i > 0 and nums[i] == nums[i-1]:
            continue
        l, r = i+1, n-1
        while l < r:
            if nums[i] + nums[l] + nums[r]>0:
                r -= 1
                while l < r and nums[r-1] == nums[r]:
                    r -= 1
            elif nums[i] + nums[l] + nums[r]<0:
                l += 1
                while l < r and nums[l] == nums[l-1]:
                    l += 1
            else:
                res.append([nums[i],nums[l],nums[r]])
                l += 1
                r -= 1
                while l < r and nums[l] == nums[l - 1]: l += 1
                while l < r and nums[r] == nums[r + 1]: r -= 1
    return res

if __name__ == '__main__':
    nums = [-2,-3,0,0,-2]
    print(threeSum(nums))
t2 = time()
run_time = t2 - t1
print(run_time)

结果：

[]
#时间
0.0

以上为个人经验，希望能给大家一个参考，也希望大家多多支持我们。

Python基础教程之循环语句（for、while和嵌套循环）

循环可以用来重复执行某条语句,直到某个条件得到满足或遍历所有元素. 1 for循环是for循环,可以把集合数据类型list.tuple.dict.set的元素遍历出来. (1)对list进行循环 city_list = ['广州','深圳','东莞','佛山'] city_list = ['广州','深圳','东莞','佛山'] for city in city_list: print("当前地市为:{0}".format(city)) 当前地市为:广州当前地市为:深圳当前地市为
python 求1-100之间的奇数或者偶数之和的实例

如下所示: i=0 sum1=0 sum2=0 while i<=100: if i%2==0: sum1+=i else: sum2+=i i+=1 print('1-100之间偶数和为:%d' % sum1) print('1-100之间偶数和为:%d' % sum2) 结果: 1-100之间偶数和为:2550 1-100之间奇数和为:2500 以上这篇python 求1-100之间的奇数或者偶数之和的实例就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们.
Python之list对应元素求和的方法

本次分享将讲述如何在Python中对多个list的对应元素求和,前提是每个list的长度一样.比如:a=[1,2,3], b=[2,3,4], c=[3,4,5], 对a,b,c的对应元素求和,输出应为[6,9,12]. 方法一: 直接求解,按照对应元素相加的原则,可先定义一个函数. def list_add(a,b): c = [] for i in range(len(a)): c.append(a[i]+b[i]) return c if __name__ == '__main__': a
Python三数之和的实现方式

目录三数之和题目描述思路 Python3代码三数之和题目描述给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c , 使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组. 答案中不允许包含重复的三元组. 示例: 给定数组 nums = [-1, 0, 1, 2, -1, -4], 满足要求的三元组集合为: [ [-1, 0, 1], [-1, -1, 2] ] 思路 1. 首先将数组排序,可以利用Python内置函数,也可
C++实现LeetCode（三数之和）

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c) The solut
关于PHP求解三数之和问题详析

三数之和给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组. 注意:答案中不可以包含重复的三元组. 示例: 给定数组 nums = [-1, 0, 1, 2, -1, -4], 满足要求的三元组集合为: [ [-1, 0, 1], [-1, -1, 2] ] 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/3sum 解题思路
C++实现LeetCode(16.最近三数之和)

[LeetCode] 16. 3Sum Closest 最近三数之和 Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly on
IOS 算法三数之和求解问题

目录 IOS 算法三数之和求解问题 1.三数求和简单介绍 2.代码 IOS 算法三数之和求解问题 1.三数求和简单介绍对于一个整数的数组, 是否存在a, b, c 使得 a + b + c = 0, 返回a b c 数组,相同数组只返回一个,: 例如: [-1, -2, 6, 5, 0, 1, 2, -1, -1] 返回 [[-1, 0, 1], [-2, 0, 2], [-1, -1, 2]] 关键点: ① 找到和为0的三个数 ② 去除相同项, 比如: 上面的数组其实 [-1, 0, 1]
java算法题解Leetcode15三数之和实例

目录题目解题思路题目 15. 三数之和给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组. 注意:答案中不可以包含重复的三元组. 示例 1:输入:nums = [-1,0,1,2,-1,-4]输出:[[-1,-1,2],[-1,0,1]]示例 2:输入:nums = []输出:[]示例 3:输入:nums = [0]输出:[]提示:0 <= nums.length <=
python实现三种随机请求头方式

相信大家在爬虫中都设置过请求头 user-agent 这个参数吧? 在请求的时候,加入这个参数,就可以一定程度的伪装成浏览器,就不会被服务器直接识别为spider.demo.code ,据我了解的,我很多读者每次都是直接从network 中去复制 user-agent 然后把他粘贴到代码中, 这样获取的user-agent 没有错,可以用, 但是如果网站反爬措施强一点,用固定的请求头可能就有点问题, 所以我们就需要设置一个随机请求头,在这里,我分享一下我自己一般用的三种设置随机请求头方式思路介
使用python实现两数之和的画解算法

题目描述给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出和为目标值 target 的那两个整数,并返回它们的数组下标. 你可以假设每种输入只会对应一个答案.但是,数组中同一个元素在答案里不能重复出现. 你可以按任意顺序返回答案. 示例 1: 输入:nums = [2,7,11,15], target = 9 输出:[0,1] 解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] . 示例 2: 输入:nums = [3,2,4],
Python拼接字符串的7种方式详解

忘了在哪看到一位编程大牛调侃,他说程序员每天就做两件事,其中之一就是处理字符串.相信不少同学会有同感. 几乎任何一种编程语言,都把字符串列为最基础和不可或缺的数据类型.而拼接字符串是必备的一种技能.今天,我跟大家一起来学习Python拼接字符串的七种方式. 1.来自C语言的%方式 print('%s %s' % ('Hello', 'world')) >>> Hello world %号格式化字符串的方式继承自古老的C语言,这在很多编程语言都有类似的实现.上例的%s是一个占位符,它仅代表
Java实现LeetCode（两数之和）

给定一个整数数组和一个目标值,找出数组中和为目标值的两个数. 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用. 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回[0, 1] 思路一:最直接的思维,两次遍历查询,时间复杂度O(N*N). 代码: public static int[] twoSum1(int[] nums, int target) { int[] label =

Python三数之和的实现方式

目录

三数之和题目描述

思路

Python3代码

相关推荐

随机推荐