剑指Offer[57]-和为s的两个数字

题目

输入一个递增排序的数组和一个数字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的两个值,当然结束条件就是双指针相遇。

总结

此类题目,我们要能快速定位到题目中的关键条件,并能够联系到可用的算法模型。

发表评论

电子邮件地址不会被公开。