微课做动画的网站,江西住房和城乡建设部网站,wordpress标题不能空,网站图片描述怎么写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] 方法一、暴力解法 该解法即对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]方法二、二分查找法 在暴力解法中第二层遍历是对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]方法三、双指针 在上面二分查找的优化中可发现“有序”可以极大的优化内层循环的时间复杂度 发散思维摒弃内外层循环的思路“有序”是否还可以发挥更大的作用呢 答案是可以的即使用双指针算法
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
