Description
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
Solution
时间复杂度：O(n^2)
空间复杂度：O(1)
核心：
第i个元素分别之后的每一个元素（i+1, i+2...., i+n）求和，然后做判断
def twoSum(self, nums, target):
for i in xrange(len(nums)):
for j in xrange(i+1, len(nums)):
if (nums[i] + nums[j] == target):
return i, j
时间复杂度：O(n^2)
空间复杂度：O(n)
核心：
1. 对数组做排序
2. 较小的元素i（取第一个元素）和元素j（取最后一个元素），求和
3. 如何和等于目标值，返回元素的索引即可；如果和小于目标值，那么将元素i的索引加1；反之，那么将元素j的索引减1。
4. 再求和，进入步骤3。
def twoSum(self, nums, target):
index = []
numtosort = nums[:]
numtosort.sort()
i = 0; j = len(numtosort) - 1
while i < j:
if numtosort[i] + numtosort[j] == target:
index.append(nums.index(numtosort[i]))
index.append(len(nums) - nums[::-1].index(numtosort[j]) - 1)
index.sort()
break
elif numtosort[i] + numtosort[j] < target:
i = i + 1
elif numtosort[i] + numtosort[j] > target:
j = j - 1
return (index[0],index[1])
时间复杂度： O(n)
空间复杂度： O(n)
核心：
1. 取第i个元素，计算目标值减去该元素值
2. 判断是否在字典中，如果在那么取字典中该元素的索引即可
3. 否则将元素索引及值存入字典，进入步骤1
def twoSum(self, nums, target):
dict = {}
for i in xrange(len(nums)):
x = nums[i]
if target-x in dict:
return (dict[target-x], i)
dict[x] = i
--EOF--
