题目
输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出任意一对即可。
示例 :
输入:nums = [2,7,11,15], target = 9
输出:[2,7] 或者 [7,2]
输入:nums = [10,26,30,31,47,60], target = 40
输出:[10,30] 或者 [30,10]
python代码
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
slow_p = 0
fast_p = len(nums)-1
while slow_p!=fast_p:
_temp = nums[slow_p]+nums[fast_p]
if _temp<target:
slow_p+=1
elif _temp>target:
fast_p-=1
else:
return [nums[slow_p],nums[fast_p]]
我们先提取题目中的关键字,递增数组(有序性),两个数字之和(需要找两次),自然而然我们就能想到双指针,从数组的两头开始,若和小了,就把左指针往后移动(数组从左往右递增),若和大了,就把右指针往前移动(数组从右往左递减),直到遇到和为s的两个值,当然结束条件就是双指针相遇。
总结
此类题目,我们要能快速定位到题目中的关键条件,并能够联系到可用的算法模型。