寻找和为定值的两个或多个数
一、寻找和为定值的两个数
题目:输入一个数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字。
要求时间复杂度是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)
声明:该文观点仅代表作者本人,牛骨文系教育信息发布平台,牛骨文仅提供信息存储空间服务。
- 上一篇: 计蒜客题目 两数之和
- 下一篇: php查询数据库的优化