寻找和为定值的两个或多个数

一、寻找和为定值的两个数

题目：输入一个数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。
要求时间复杂度是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 "
"
	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)