41、和为s的两个数字VS和为s的连续正数序列

和为s的两个数字

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

代码实现：

# -*- coding:utf-8 -*-
class Solution:
    def FindNumbersWithSum(self, array, tsum):
        #题目没有对于特殊情况的输入做解释，那么也就先满足基本功能吧
        length = len(array)
        p1 = 0
        p2 = length - 1
        while p1 < p2:
            #若有答案，则返回答案
            if array[p1] + array[p2] == tsum:
                return array[p1],array[p2]
            elif array[p1] + array[p2] < tsum:
                p1 += 1
            else:
                p2 -= 1

        #若运行至此，说明没有答案，因此返回空列表
        return []

和为s的连续正数序列

参考上面的做法，我们可以令small=1,big=2,然后sum小于target，就增大small的值，大于target就减小big的值。
那么既然有多个结果，什么时候停止呢？
注意到，是连续的正数序列，并且最小只能有两个数。那么small就应该在(1+target)//2处停止。比如，对于15来说，当small到8时，最少也是8+9等于17了。因此，当small等于middle时，就可以终止了。

注意的地方：
不知道指针small和big指针怎么操作的话，可以举例子，比如15，走一遍就知道了。
初始化small 为1，big为2，curSum为1+2=3

• 当curSum比tarSum小时，应该向右移动big指针。
• 当curSum比tarSum大时，应该向左移动small指针。
• 当curSum等于tarSum时，此时应该输出从small到big的序列。
  但是需要注意的是，此时我们仍然想要找别的解，那么怎么移动呢？经过写的例子，很容易推出，此时应该向右移动big指针，去推动循环的继续实现。

代码实现：

# -*- coding:utf-8 -*-
class Solution:
    def outList(self,small,big):
        out = []
        for i in range(small,big+1):
            out.append(i)
        return out

    def FindContinuousSequence(self, tsum):
        if tsum < 3:
            return []

        small = 1
        big = 2
        middle = (1+tsum)//2
        curSum = small + big
        res = []

        while small < middle:
            if curSum < tsum:
                big += 1
                curSum += big

            elif curSum >  tsum:
                curSum -= small
                small += 1

            else:
                out = self.outList(small,big)
                res.append(out)
                big += 1
                curSum += big
        return res

S = Solution()
print(S.FindContinuousSequence(15))