题目描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

例如 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

Python的4种解法

第一种 ：python，调用1次循环（实际if判断也相当于一次循环），思路和方法一相同，时间复杂度也一样

def twoSum(nums, target): lens = len(nums) j=-1 for i in range(lens): if (target - nums[i]) in nums: #该句的查找范围可以在 if (nums.count(target - nums[i]) == 1)&(target - nums[i] == nums[i]):#如果num2=num1,且nums中只出现了一次，说明找到是num1本身。 continue else: j = nums.index(target - nums[i],i+1) #index(x,i+1)是从num1后的序列后找num2 break if j>0: return [i,j] else: return []

第二种：python的优化版本，主要是对第二种方法，对查找范围做了优化，始终在第一个数的前面的范围找第二个数，也避免了对重复元素(与第1个数重叠)的判断

前两种方式都是暴力解

def twoSum(nums, target): lens = len(nums) j=-1 for i in range(1,lens): temp = nums[:i] if (target - nums[i]) in temp: j = temp.index(target - nums[i]) break if j>=0: return [j,i]

第三种，利用哈希表 个人理解这种办法相较于方法一其实就是字典记录了 num1 和 num2 的值和位置，而省了再查找 num2 索引的步骤

def twoSum(nums, target): hashmap = {} for ind, num in enumerate(nums): hashmap[num] = ind for i, num in enumerate(nums): j = hashmap.get(target - num) if j is not None and i != j: return [i, j]

第四种，在第四种的基础上进行优化，主要还是优化查找范围 类似方法三，不需要 num2 在整个 dict（hashmap） 中去查找。可以在 num1 之前的 dict 中查找，因此就只需要一次循环可解决。

def twoSum(nums, target): hashmap={} for i,num in enumerate(nums): if hashmap.get(target - num) is not None: return [i,hashmap.get(target - num)] hashmap[num] = i #这句不能放在if语句之前，解决list中有重复值或target-num=num的情况

下面的代码，第四种方法类似，但是效率低，因为用了in，相当于用了循环。

from typing import List class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: dict1={} for i,value in enumerate(nums): x=target-value if x in dict1.keys(): #主要是这一句判断不同 return [i,dict1[x]] dict1[value]=i return []

参考链接 https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-2/

https://leetcode-cn.com/problems/two-sum/solution/xiao-bai-pythonji-chong-jie-fa-by-lao-la-rou-yue-j/

2020年7月更新，Java的三种解法

第一种暴力解

暴力法很简单，遍历每个元素 xxx，并查找是否存在一个值与 target−xtarget - xtarget−x 相等的目标元素。

class Solution { public int[] twoSum(int[] nums, int target) { for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[j] == target - nums[i]) { return new int[] { i, j }; } } } throw new IllegalArgumentException("No two sum solution"); } }

复杂度分析：

时间复杂度：O(n2) 对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n)的时间。因此时间复杂度为 O(n2)。

空间复杂度：O(1)

第二种是两遍哈希表 以空间换时间

class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { map.put(nums[i], i); } for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (map.containsKey(complement) && map.get(complement) != i) { return new int[] { i, map.get(complement) }; } } throw new IllegalArgumentException("No two sum solution"); } }

时间复杂度是O（n），空间复杂度也是O（n）

第三种是一遍哈希表

class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (map.containsKey(complement)) { return new int[] { map.get(complement), i }; } map.put(nums[i], i); } throw new IllegalArgumentException("No two sum solution"); } }

时间复杂度是O（n），空间复杂度也是O（n）

此题最优解：一遍哈希表的思路

思路： （1）遍历数组，以value为键，索引index为值创建哈希表d1={ value:index} （2） 当遍历到一个数a的时候，判定target-a是否在哈希表的键当中（排除target-a=a，题设条件），如果在的话输出index(a),和d1[target-a] ， 如果没有的话，则把a和index(a)，放在哈希表的键和值里 （3）最后遍历完都没有则返回[] 参考链接：https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-2/