用h5做的网站,龙岗附近网站建设,益阳在线官网,家具网站源码1.两数之和
给定一个整数数组 nums 和一个整数目标值 target#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数#xff0c;并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是#xff0c;数组中同一个元素在答案里不能重复出现。 你可以按任…1.两数之和
给定一个整数数组 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], target 6 输出[1,2] 示例 3 输入nums [3,3], target 6 输出[0,1] 方法一、暴力解法 时间复杂度O(n的平方 )空间复杂度O(1) 该解法即对numsnumsnums进行双重遍历将所有两个数组合情况均列举一遍若有符合题意情况直接返回即可
from typing import List
def twoSum(nums: List[int], target: int) - List[int]:for i in range(len(nums)):for j in range(i1,len(nums)):if nums[i]nums[j]target:return [i,j]
nums[2,7,11,15]
target 17
atwoSum(nums,target)
print(a)#[0, 3]方法二、二分查找法 时间复杂度O(nlogn)空间复杂度O(n) 在暴力解法中第二层遍历是对iii后面的元素进行无差别枚举这样会导致非常多的无效枚举。 我们可以借助二分算法来对内层循环从时间上进行优化。 因为二分算法的前提是“有序”则我们需要先对numsnumsnums进行排序。 又因为返回答案需要原numsnumsnums顺序所以我们不妨提前将numsnumsnums中的值与其下标做一个绑定统一排序
import bisect
from typing import Listdef twoSum(nums: List[int], target: int) - List[int]:n len(nums)#print(list(zip(nums, range(n))))#[(2, 0), (11, 1), (7, 2), (15, 3)]nums sorted(zip(nums, range(n))) # O(nlogn)print(nums)#[(2, 0), (7, 1), (11, 2), (15, 3)]# 以下部分时间复杂度为O(nlogn)for i in range(n):t target - nums[i][0]print(t is:,t)j bisect.bisect_left(nums, (t, ), i 1, n)#见如下备注print(j is:,j)if j n and nums[j][0] t:return [nums[i][1], nums[j][1]]#[1, 3]return []nums[2,11,7,15]
target 26
atwoSum(nums,target)
print(a)
# t is: 24 备注 t为24然后在nums中查找24从i为1查到3则查到24在nums中处于第4位置所以j为4
# t is: 19 备注 t为19然后在nums中查找19从i为2查到3则查到19在nums中处于第4位置所以j为4
# t is: 15 备注 t为15然后在nums中查找15从i为3查到3则查到15在nums中处于第3位置所以j为3
# [1, 3]方法三、双指针 时间复杂度O(nlogn)空间复杂度O(n) 在上面二分查找的优化中可发现“有序”可以极大的优化内层循环的时间复杂度 发散思维摒弃内外层循环的思路“有序”是否还可以发挥更大的作用呢 答案是可以的即使用双指针算法
from typing import Listdef twoSum(nums: List[int], target: int) - List[int]:n len(nums)nums sorted(zip(nums, range(n))) # O(nlogn)#一定要排序要不然可能返回不了正确的结果print(nums)#[(2, 0), (6, 6), (7, 2), (9, 7), (11, 1), (12, 5), (15, 3), (26, 4)]# 以下部分时间复杂度为O(n)left, right 0, n - 1while left right:if nums[left][0] nums[right][0] target:return [nums[left][1], nums[right][1]]elif nums[left][0] nums[right][0] target:right - 1else:left 1return []nums[2,11,7,15,26,12,6,9]
target 20
# nums[2,5,1,4,7,3,33,20,9]
# target 36#如果不排序则返回不了正确的结果
atwoSum(nums,target)
print(a)
#总结排序后为[(2, 0), (6, 6), (7, 2), (9, 7), (11, 1), (12, 5), (15, 3), (26, 4)]
#从小到大排好后首先是2262828大于20则right-1因为最小的数加上最大的数target,则这里最大数28舍弃
#因为28和最小的相加都大于20和其它数相加更大于20所以right-1
#接下来就是2151717小于target所以要找更大的数和15相加所以left-1方法四哈希表解法 时间复杂度O(n)空间复杂度O(n) 1.字典是一种典型的键值对类型的数据结构每一个元素都是由一个键值对键key和值value组成 2.这种数据结构可以通过某个键来访问元素所以字典也被称为映射或散列表 3.字典的主要特性是根据键快速查找值也可以自由添加和删除元素这有点像List但跟List不同的是List是连续存储直接定址的。 字典像链表非连续存储所以删除元素不需要移动后续元素就没有在内存中移动后续元素的性能开销 4.通过键来检索值的速度是非常快的接近于 O(1)这是因为 Dictionary 类是作为一个哈希表来实现的Dictionary 没有顺序之分这一点不同于list列表有顺序之分 键必须是唯一的而值不需要唯一 5.字典中的键和值都是object类型所以可以是任何类型比如string、int、自定义类型等等
from typing import Listdef twoSum(nums: List[int], target: int) - List[int]:n len(nums)mp {}for i in range(n):t target - nums[i]print(i为%d时字典为:%s%(i,mp))if t in mp:return [mp[t], i]# 存放nums[i]mp[nums[i]] i#依次把列表放入字典key为列表中的值value为列表中值的下标return []nums[2,11,7,15,26,12,6,9]
target 20
atwoSum(nums,target)
print(a)#[1, 7]#i为7时字典为:{2: 0, 11: 1, 7: 2, 15: 3, 26: 4, 12: 5, 6: 6}方法五、集合视角分类讨论 时间复杂度O(n)空间复杂度O(n) 从集合的角度来看 我们构造两个集合 aaa集合为nums中所有值构成的集合。 bbb集合为nums中所有值与target的距离值构成的集合即target−nums[i]
视角一 假设答案有解那么aaa集合与bbb集合的交集一定有值。
假设答案无解那么有两种情况 aaa集合与bbb集合的交集为空集 aaa集合与bbb集合的交集只有一个值值为target的一半并且nums中该值仅存在一个。
视角二 此外因为题目保证一定有解所以我们还可以再换一个视角。 从答案的构成上来看可以分为两种情况 第一种为nums中两个相同元素的和为target 第二种为nums中两个不同元素的和为target比如列表[2,11,7,15] sum30时
from typing import Listdef twoSum(nums: List[int], target: int) - List[int]:# 分情况讨论# 情况1. nums中有两个相同的值和为targeta target // 2#除以2,然后向下取整print(a)if target % 2 0 and nums.count(a) 2:#count计算列表中参数x出现的次数,这里的条件是出现了2次及以上return [nums.index(a), nums.index(a, nums.index(a) 1)]#index获得参数x在列表中的位置index的第二个参数表示起始位置,第3个参数默认为末位置# 情况2. nums中有两个不同的值和为target#set(nums)把列表转为集合并且去重集合中不能有相同的数据s set(nums) set([target - x for x in nums])##即{2,11,26,12,6,9}和{8, 9, 11, 14, 18, -6}取交集,返回一个集合if s ! set():b s.pop()#返回被删除的集合中一个元素return [nums.index(b), nums.index(target - b)]# 情况3. nums中没有满足题意的情况return []nums[2,11,26,12,6,9]
target 20
atwoSum(nums,target)
print(a)#[5, 1]
