原题
给一个整数数组，找到两个数使得他们的和等于一个给定的数target。
你需要实现的函数twoSum需要返回这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是1到n，不是以0开头。
numbers=[2, 7, 11, 15], target=9, return [1, 2]
解题思路
- 对撞型指针
- 由于要返回下标，所以先建立一个hash map储存每个值得下标
- 两个指针分别从数组的头跟尾向中间扫描，如果两个数的和等于target则回到hash map中找到相应最小的下标返回，否则相应的移动头指针或者尾指针，知道两个指针相撞，结束
完整代码
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
index = {}
for i, num in enumerate(nums):
if num not in index:
index[num] = [i]
else:
index[num].append(i)
sortedNums = sorted(nums)
i, j = 0, len(nums) - 1
while i < j:
if sortedNums[i] + sortedNums[j] == target:
if sortedNums[i] == sortedNums[j]:
return [index[sortedNums[i]][0], index[sortedNums[i]][1]]
else:
res = [index[sortedNums[i]][0], index[sortedNums[j]][0]]
return sorted(res)
elif sortedNums[i] + sortedNums[j] > target:
j -= 1
else:
i += 1
