一、寻找和为定值的两个数
题目：输入一个数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。
要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。
例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。
详情参考http://blog.csdn.net/v_july_v/article/details/6419466
用一个hash表，储存每一个数的下标。时间复杂度O(N)，空间复杂度为O(N).
#!/usr/bin/env python
# -*- coding: utf-8 -*
#查找数组中两个数为指定值的两个数
def twoSum(A, s):
'''找到数组中和为定值的两个数，返回其对应的下标'''
l = len(A)
mHash,res = {},[]
for i in xrange(l):
mHash[A[i]] = i
for i in xrange(l):
t = s - A[i]
if mHash.has_key(t):
res.append(i)
res.append(mHash[t])
break
return res
if __name__ == '__main__':
A = [1, 2, 4, 7, 11, 15]
s = 15
print 'the index are :' ,twoSum(A,s)
方法二：先排序，然后左右夹逼。排序O(N*logN)，夹逼O(N)，总的时间复杂度为O(N*logN)，空间复杂度为O(1)。 也可以采用二分查找，但是总的时间复杂度不变。
#!/usr/bin/env python
# -*- coding: utf-8 -*
#查找数组中两个数为指定值的两个数
def partition(s, m, n):
#s is a list
key = s[n-1]
l,r = m,n-2
while True:
while l <= n-2 and s[l] <= key:
l += 1
while r>= m and s[r] > key:
r -= 1
if l < r:
s[l],s[r] = s[r],s[l]
else:
break
s[l],s[n-1] = s[n-1],s[l]
return l
def medin3(s, m, n):
md = m + (n-m)/2
if s[m] > s[md]:
s[m],s[md] = s[md],s[m]
if s[m] > s[n]:
s[m],s[n] = s[n],s[m]
if s[md] > s[n]:
s[md],s[n] = s[n],s[md]
s[md],s[n-1] = s[n-1],s[md]
return s[n-1]
def quicksort(s, m, n):
#s is a list
if m < n:
medin3(s, m, n)
k = partition(s, m, n)
quicksort(s, m, k)
quicksort(s, k+1, n)
def twoSumd(A, s):
'''快速排序，夹逼, 返回两个数'''
lens = len(A)
quicksort(A, 0, lens-1)
l,r = 0,lens-1
while l<r:
if A[l] + A[r] < s:
l += 1
elif A[l] + A[r] > s:
r -= 1
else:
return (A[l],A[r])
return False
if __name__ == '__main__':
A = [1, 2, 4, 7, 11, 15]
s = 15
print 'the index are :' ,twoSumd(A,s)
二、寻找和为定值的多个数
题目：输入两个整数 n 和 m，从数列1，2，3.......n 中 随意取几个数,
使其和等于 m ,要求将其中所有的可能组合列出来
#!/usr/bin/env python
# -*- coding: utf-8 -*
#查找数组中和为指定值的多个数
mlist = []
def find_factor(s, n):
'''找到和为s的1...n中的序列'''
if n <= 0 or s <= 0:
return ;
if s == n:
print n,
for i in mlist:
print ' + ', i,
print '\n'
mlist.insert(0, n)
find_factor(s-n, n-1) #包含有n的序列
del mlist[0]
find_factor(s, n-1) #不包含有n的序列
if __name__ == '__main__':
m = int(raw_input('input the sum :'))
n = int(raw_input('input the n :'))
find_factor(m, n)