和为 s 的数字

• 和为 k 的两个数字
  一个递增排序的数组，在其中查找两个数使得其和 k。如果有多组，输出任意一对即可。
  思路：
  可以简单的遍历，确定一个数字，找寻另一个，时间复杂度 O(n^2)，太高；可以使用两个指针，一个指向数组头部，另一个指向数组尾部，判断其和是否等于 k，大于则使尾指针向前移动，即 -1，小于则使头指针向后移动，即 +1

def FindNumbersWithSum(nums, k):
    """
    在给定的数组 nums 中找到任意一对和为 k 的值
    :type nums: list[int]
    :tyoe k: int
    :rtype: None
    """
    if len(nums) < 2:
        return
    end = len(nums) - 1
    head = 0
    while head < end:
        cur_sum = nums[head] + nums[end]
        if cur_sum == k:
            print nums[head], nums[end]
            break
        if cur_sum > k:
            end -= 1
        else:
            head += 1
    else:
        print 'No found'


a = [1, 2, 4, 7, 11, 15]
FindNumbersWithSum(a, 11)

• 和为 s 的连续正整数序列
  输入一个正数，打印所有和为 k 的连续正数序列（至少 2 个）。
  思路：
  两个指针，从 1 和 2 开始，如果小于 k 则第二个指针 +1 ，判断其是否等于 k，小于则继续 +1，找到之后，继续 +1，当 当前序列和大于 k 的时候，减去 第一个指针 的值，然后判断其是否等于 k，继续重复。结束条件为 第一个指针的值要小于 (k+1)/2，因为 k/2 和 k/2 + 1 一定大于或等于 k。

def FindContinuousSequence(k):
    """
    找出连续的正整数使得其和为 k
    :type k: int
    :rtype: None
    """
    if k < 3:
        return
    small, big = 1, 2
    middle = (k + 1) / 2
    cur_sum = small + big
    while small < middle:
        if cur_sum == k:
            print [i for i in range(small, big+1)]
        while cur_sum > k and small < middle:
            cur_sum -= small
            small += 1
            if cur_sum == k:
                print [i for i in range(small, big+1)]
        big += 1
        cur_sum += big
        
FindContinuousSequence(15)