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].方法一：暴力求解 O(n²)
class Solution(object): def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ for i in range(len(nums)): for j in range(i+1, len(nums)): if nums[i]+nums[j] == target: return [i,j] return None
方法二：增加hash表，以空间换时间，思路就是：因为target由两个元素组成，我们在遍历寻找a的匹配元素的时候需要知道a的位置，所以hash表存储a的位置，key为元素值，value为index，容易理解的思路是遍历两遍，第一遍存储所有元素对应的index,hash[num[i]]=i，第二遍遍历如果target-num[i]存在于hash表里，即满足要求，并返回hash[target-num[i]],i, O(n)
方法三:
在方法二的基础上遍历一遍，一边存到hash表，一边查找：
class Solution(object): def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ hashtmp = dict() for i in range(len(nums)): if target-nums[i] in hashtmp: return [hashtmp[target-nums[i]], i] hashtmp[nums[i]] = i return None