#title : Two Sum#Given an array of integers, find two numbers such#that they add up to a specific target number.#The function two Sum should return indices of the#two numbers such that they add up to the target,#where index1 must be less than index2. Please note #that your returned answers (bothindex1 and index2)#are not zero-based.#You may assume that each input would have exactly #one solution.#Input: numbers={2, 7, 11, 15}, target=9#Output: index1=1, index2=2# First method O(n^2)#easy but Time Limit Exceeded# class Solution:# 	# @return a tuple,(index1, index2)# 	def twoSum(self, num, target):# 		for i in range(len(num)):# 			for j in range(i+1,len(num)):# 				if (num[i] + num[j] == target):# 					return (i+1,j+1)#Second method O(n) HashTable#HashTable store the number‘s indexclass Solution:	# @return a tuple,(index1, index2)	def twoSum(self, num, target):		num_hashtable = dict()		result_tuple = tuple()		mul_hash = dict()		for i in range(len(num)):			#the key don‘t repeat 			if num[i] in num_hashtable:				mul_hash[num[i]] = i			else:			#the key do repeat				num_hashtable[num[i]] = i		print mul_hash		print num_hashtable		for i in range(len(num)):			gap = target - num[i]			#two cases			#first : don‘t have same number			if gap >= 0 and gap != num[i]:				if num_hashtable.has_key(gap):					result_tuple = (i+1,num_hashtable[gap]+1)					return result_tuple			#second : have same number			elif gap >= 0 and gap == num[i]:				if gap in mul_hash:					result_tuple = (i+1,mul_hash[gap]+1)					return result_tupleif __name__ == ‘__main__‘:	twoSum = Solution()	num = [3,2,5,7,3]#	num = [0,0,3,2,8,9,7,8,9,7]#	num = 0	target = 6	print twoSum.twoSum(num, target)