题目描述：输入一个递增排序的数组和一个数字 S，在数组中查找两个数，使得他们的和正好是 S，如果有多对数字的和等于 S，输出两个数的乘积最小的。
Solutions
第一种采用暴力法，$O(n^2)$：
# -*- coding:utf-8 -*-
class Solution:
def FindNumbersWithSum(self, array, tsum):
# write code her
if array is None or len(array) < 2:
return []
n = len(array)
for i in range(n-1):
for j in range(i, n):
if array[i] + array[j] == tsum:
return array[i], array[j]
return []
# 运行时间：23ms
# 占用内存：5752k
因为要找数，于是想用字典存数，能够在 $O(1)$ 时间找到，结果在 OJ 上效果不是很理想：
# -*- coding:utf-8 -*-
class Solution:
def FindNumbersWithSum(self, array, tsum):
# write code her
if array is None or len(array) < 2:
return []
index_dict = {}
for num in array:
if num in index_dict:
index_dict[num] += 1
else:
index_dict[num] = 1
for num in array:
res = tsum - num
if res in array:
if res == num and index_dict[res] < 2:
return []
else:
return num, res
return []
# 运行时间：49ms
# 占用内存：5648k
第三种方法原本也是不难想到的才对，为什么自己就没有第一时间反应过来呢？！采用两个指针，一个从头一个自尾向中间遍历，如果加和比要求的小，那么就挪动前指针增大加和，如果加和比要求的大，那么挪动后指针减小加和，直到两个指针碰头。
# -*- coding:utf-8 -*-
class Solution:
def FindNumbersWithSum(self, array, tsum):
# write code her
if array is None or len(array) < 2:
return []
p_left = 0
p_right = len(array) - 1
while p_left < p_right:
if array[p_left] + array[p_right] == tsum:
return array[p_left], array[p_right]
elif array[p_left] + array[p_right] > tsum:
p_right -= 1
else:
p_left += 1
return []
# 运行时间：23ms
# 占用内存：5728k