1. 两数之和
暴力法
思路
两层for循环，外层for循环i遍历数组元素，内层for循环j遍历[i+1, n-1]范围内剩余元素，若nums[i]+nums[j] = target，返回[i,j]。
哈希表(map)
思路
一层for循环i遍历数组元素，判断当前元素nums[i]的另一半（target - nums[i]）是否在哈希表map中。
若在，返回这两个元素下标；
若不在，将当前元素nums[i]及下标i加入map中。
本质是用哈希表(map)优化了暴力法中的第二层for循环，本解法使用 unordered map数据结构，从map中查找元素时间复杂度为O(1)，相当于用空间换取时间，将暴力法第二层for循环时间复杂度降到O(1)。
进阶
-
为什么想到用哈希表？
哈希表适用场景：（1）判断一个元素是否在集合中。（2）判断一个元素是否在集合中出现过。
暴力法第二层for循环目的是从子数组中查找一个元素。 -
为什么用哈希表(map)？
可用三种数据结构实现哈希表：数组、set、map。
数组：数组长度固定，初始化后不能更改。数组长度必须大于元素最大数量。
set：元素不重复，可增删元素。
map：存储（key, value）键值对，key不重复。
本题nums元素最多为10^4，若采用数组实现哈希表，浪费存储空间。若使用set，则无法同时存储数组元素及下标。使用map实现哈希表，key存储数组元素，value存储下标。 -
map中存储什么？
map中存储(key, value)对，key不重复。 -
map的key存储什么？value存储什么？
key存储数组元素，value存储下标。
class Solution {public int[] twoSum(int[] nums, int target) {// 哈希表(unordered map)，key 存储数组元素，value 存储下标Map<Integer, Integer> map = new HashMap<>();int[] res = new int[2]; // 存储和为 target 的元素下标for (int i = 0; i < nums.length; i++) {// 判断 nums[i] 的另一半（target - nums[i]）是否在 map 中int key = target - nums[i];if (map.containsKey(key)) { // 在 map 中查找是否有与 nums[i] 匹配的 keyres[1] = i;res[0] = map.get(key);break;} else {map.put(nums[i], i); // 不匹配，把当前访问的元素及下标加入 map 中}}return res;}
}