哈希：两数之和

问题描述：在一个整数数组中，找到两数之和为target的两个值，返回找到的两个值的下标。

nums=[3,3]

target=6

返回：[0,1]

说明：返回结果，索引无顺序要求；有唯一的答案；不能使用两次相同的元素，比如上述例子中不能返回[0,0]或者[1,1]。

---

求解思路1：暴力解法

两层for循环

时间复杂度：O(n^2)

空间复杂度：O(1)

class Solution {public int[] twoSum(int[] nums, int target) {int[] indexArr = new int[2];for(int i = 0;i < nums.length;i++){for(int j = i + 1;j < nums.length;j++){if(nums[i] + nums[j] == target){indexArr[0] = i;indexArr[1] = j;break;}}}return indexArr;}
}

---

求解思路2：使用哈希

把所有值都存到哈希表中，key为num，value为index。找两数，其实就是遍历的时候查找target-nums[i]，去哈希表中查找即可。

时间复杂度：O(1)

空间复杂度：O(n)

class Solution {public int[] twoSum(int[] nums, int target) {int[] indexArr = new int[2];HashMap<Integer,Integer> hashMap = new HashMap<>();// 把所有的数都存放到hashMap中for(int i = 0;i < nums.length;i++){hashMap.put(nums[i],i);}for(int i = 0;i < nums.length;i++){int curNum = nums[i];int another = target - curNum;// 寻找另一个数时，必须要有i != hashMap.get(another)// 否则[3,2,4]这种情况会返回[0,0]而报错if(hashMap.containsKey(another) && i != hashMap.get(another)){indexArr[0] = i;indexArr[1] = hashMap.get(another);break;}}return indexArr;}
}

上面的代码是构建hash表、遍历查找另一个数，分开了两步，也可以在一个for循环里进行，如下：

class Solution {public int[] twoSum(int[] nums, int target) {int[] indexArr = new int[2];HashMap<Integer,Integer> hashMap = new HashMap<>();hashMap.put(nums[0],0);for(int i = 0;i < nums.length;i++){int curNum = nums[i];int another = target - curNum;if(hashMap.containsKey(another) && i != hashMap.get(another)){indexArr[0] = i;indexArr[1] = hashMap.get(another);break;}hashMap.put(nums[i],i);}return indexArr;}
}

练习地址：1. 两数之和 - 力扣（LeetCode）