Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum 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 (both index1 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
解题思路：此题的关键是对给定数组进行排序,把排好序的数组首尾开始查找，两个数的和大于给定值则right--，否则则left++
1 class Solution: 2 # @return a tuple, (index1, index2) 3 def twoSum(self, num, target): 4 5 #sort the array, and remeber the index 6 #can do from the start and the end to the middle 7 numbers=sorted(num) 8 9 length=len(numbers) 10 11 index=[] 12 13 left=0 14 right=length-1 15 16 while(left<right): 17 sum_data=numbers[left]+numbers[right] 18 if(sum_data>target): 19 right=right-1 20 elif(sum_data<target): 21 left=left+1 22 else: 23 for i in xrange(length): 24 if(num[i]==numbers[left]): 25 index.append(i+1) 26 elif(num[i]==numbers[right]): 27 index.append(i+1) 28 29 if (len(index)==2): 30 break 31 break 32 result=tuple(index) 33 return result
原文：http://www.cnblogs.com/echo-lsh/p/3986849.html