剑指offer57-- 和为s的数字

剑指offer57-- 和为s的数字

题目

输入一个递增排序的数组和一个数字s, 在数组中查找两个数,使得它们的和正好是s, 如果有多对的数字的和等于s,则输出任意一对即可。

比如[1,2,4,7,11,15] s=15,那么因为4和11是结果,所以就把[4,11]给返回出来.

解决方法

比较好的方法就是用双指针法,一个从前面开始,一个从后面开始,因为数组是排好序的了,当加起来的和大于给定的数字的时候就让右边的往左移,如果小的话,让左边的往右移,

def main(nums, k):
    left,right = 0, len(nums)-1
    ret = []
    while left<right:
        summ = nums[left]+nums[right]
        if summ == k:
            ret.append([left, right])
        elif summ<k:
            left += 1

        else:
            right -= 1

    return ret

基于此问题还有许多的问法, 比如如果有很多组的话,就返回积最大的那两个,只要得到ret了,其他的都比较容易,不过也可以用一个东西记录下来哪一次保存的各是最大的,然后直接返回ret[i],就不必再对ret进行操作了.

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦