面试题57：和为s的数字

题目一：
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

思路：
这道题目需要用两个指针，一个从第一位开始后移，一个从最后一位前移，如果和大于sum，后面指针前移，如果和小于sum指针前移，如果相等，输出结果。

代码实现：

# -*- coding:utf-8 -*-
class Solution:
    def FindNumbersWithSum(self, array, tsum):
        # write code here
        #特殊情况
        if len(array)<2:
            return []
        #定义两个指针
        small= 0
        big =len(array)-1

        #开始循环
        while small<big:
            if array[big] + array[small] ==tsum:
                return array[small],array[big]
            elif array[big] + array[small] < tsum:
                small+=1
            else:
                big -=1
        return []

提交结果：

image.png

题目二：
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

思路：
这道题目可以看作题目一的延续，只不过不再规定序列的个数，可以设置small和big两个指针依次向后，因为至少需要两个数，所以small最大可以到和的一半middle。当small小于middle时候一直循环，当small到big之和等于sum时，输出small到big间的数；当大于sum时，需要进入内层循环，每次减掉最小的数然后再次计算和，直到等于时输出；当和小于sum时，big加1，和加上big。

代码实现：

# -*- coding:utf-8 -*-
class Solution:
    def FindContinuousSequence(self, tsum):
        # write code here
        #特殊情况
        if tsum < 3:
            return []
        #一般情况
        small = 1
        big = 2
        middle = (tsum+1)//2
        curSum = small + big
        res = []   #保存符合条件的序列
        while small < middle:
            if curSum == tsum:
                res.append(list(range(small,big+1)))
            while curSum > tsum and small<middle:
                curSum -= small
                small+=1
                if curSum == tsum:
                    res.append(list(range(small,big+1)))
            big+=1
            curSum+=big
        return res

提交结果：

image.png