剑指Offer(Python多种思路实现):和为s的数字
190 浏览量
2020-12-22
12:02:41
上传
评论
收藏 25KB PDF 举报
剑指剑指Offer(Python多种思路实现多种思路实现):和为和为s的数字的数字
剑指剑指Offer(Python多种思路实现多种思路实现):和为和为s的数字的数字
面试57题：
题目：和为s的数字
题目描述题目描述
输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两
个数的乘积最小的。
解题思路一：使用解题思路一：使用while循环从两端向中间扫描数组，时间复杂度为循环从两端向中间扫描数组，时间复杂度为O(n)
class Solution:
def FindNumbersWithSum(self, array, tsum):
# write code here
if len(array)<2:
return [] found=False
fst,lst=0,len(array)-1
while fst<lst:
sum_total=array[fst]+array[lst] if sum_total==tsum:
found=True
return [array[fst],array[lst]] elif sum_total<tsum:
fst +=1
else:
lst -=1
return []
解题思路二：解题思路二：
def FindNumbersWithSum(self, array, tsum):
l, r = 0, len(array)-1
while l < r:
if array[l] + array[r] tsum:
r -= 1
else:
return array[l], array[r] return []
作者：雾行
资源评论
