文档讲解：代码随想录
难度：一般嗷~~
1. 两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
视频：《代码随想录》算法视频公开课 (opens new window)：梦开始的地方，Leetcode：1.两数之和 (opens new window)
思路
首先再强调一下 什么时候使用哈希法，当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。
因为本题，我们不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适。
再来看一下使用数组和set来做哈希法的局限。
- 数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
- set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。
此时就要选择另一种数据结构：map ，map是一种key value的存储结构，可以用key保存数值，用value再保存数值所在的下标。
此时就要选择另一种数据结构：map ，map是一种key value的存储结构，可以用key保存数值，用value再保存数值所在的下标。
C++中map，有三种类型：
| 映射 | 底层实现 | 是否有序 | 数值是否可以重复 | 能否更改数值 | 查询效率 | 增删效率 |
|---|---|---|---|---|---|---|
| std::map | 红黑树 | key有序 | key不可重复 | key不可修改 | O(log n) | O(log n) |
| std::multimap | 红黑树 | key有序 | key可重复 | key不可修改 | O(log n) | O(log n) |
| std::unordered_map | 哈希表 | key无序 | key不可重复 | key不可修改 | O(1) | O(1) |
std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。
这道题目中并不需要key有序，选择std::unordered_map 效率更高！
接下来需要明确两点：
- map用来做什么
- map中key和value分别表示什么
map目的用来存放我们访问过的元素，因为遍历数组的时候，需要记录我们之前遍历过哪些元素和对应的下标，这样才能找到与当前元素相匹配的（也就是相加等于target）
接下来是map中key和value分别表示什么。
这道题 我们需要 给出一个元素，判断这个元素是否出现过，如果出现过，返回这个元素的下标。
那么判断元素是否出现，这个元素就要作为key，所以数组中的元素作为key，有key对应的就是value，value用来存下标。
所以 map中的存储结构为 {key：数据元素，value：数组元素对应的下标}。
在遍历数组的时候，只需要向map去查询是否有和目前遍历元素匹配的数值，如果有，就找到的匹配对，如果没有，就把目前遍历的元素放进map中，因为map存放的就是我们访问过的元素。
过程如下：
补充：
在Java中，
Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();这行代码定义了一个类型为Integer的键和值的Map集合，并初始化为HashMap类型。这行代码的具体含义如下：
Map<Integer, Integer>：定义了一个Map集合，其中键和值的数据类型都是Integer。hashtable：是该Map集合的变量名。new HashMap<Integer, Integer>()：初始化了一个HashMap对象，并将其赋值给hashtable变量。HashMap是Map接口的一个实现类，允许使用null键和null值，并且不保证映射的顺序。在Java中，Map接口的实现类有多种，如
HashMap、TreeMap、LinkedHashMap等。这些实现类有不同的特性和用途，例如：
HashMap：基于哈希表的Map接口实现。它不保证映射的顺序，但允许使用null键和null值。TreeMap：基于红黑树的Map接口实现，能够确保其键值按照排序顺序进行存储。LinkedHashMap：基于哈希表的Map接口实现，维护着一个双向链表记录插入顺序或最近访问顺序（取决于访问顺序模式）。这些实现类可以根据具体需求选择使用，例如如果需要保持插入顺序，可以使用
LinkedHashMap；如果需要排序的Map，可以使用TreeMap
图片来自：Map<String,Integer> map=new HashMap<>(); - CSDN文库
containsKey方法——判断是否包含指定的键名
get() 方法获取指定 key 对应对 value。
get() 方法的语法为：
hashmap.get(Object key)
put() 方法将指定的键/值对插入到 HashMap 中。
put() 方法的语法为：
hashmap.put（K key，V value）
- 定义了一个类型为
Integer的键和值的Map集合，并初始化为HashMap类型。 - 记录当前的目标值的余数
- 查找当前的map中是否有满足要求的值
- 如果有，返回目标值
- 如果没有，把访问过的元素和下标加入map中
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; ++i) {
if (hashtable.containsKey(target - nums[i])) {
return new int[]{hashtable.get(target - nums[i]), i};
}
hashtable.put(nums[i], i);
}
return new int[0];
}
}
第454题.四数相加II
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。
例如:
输入:
- A = [ 1, 2]
- B = [-2,-1]
- C = [-1, 2]
- D = [ 0, 2]
输出:
2
解释:
两个元组如下:
- (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
- (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
视频：《代码随想录》算法视频公开课 (opens new window)：学透哈希表，map使用有技巧！LeetCode：454.四数相加II
思路：
Java中的getOrDefault()方法是Map接口中的一个默认方法，它用于获取指定键的值，如果键不存在，则返回一个默认值。
方法签名： V getOrDefault(Object key, V defaultValue)
参数说明：
- key：要获取值的键
- defaultValue：键不存在时返回的默认值
返回值：
- 如果键存在，则返回与键关联的值；
- 如果键不存在，则返回默认值。
- 首先定义 一个map，key放a和b两数之和，value 放a和b两数之和出现的次数。
- 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中。（map.getOrDefault(sum, 0) + 1中由于第一次运行时并没有sum键是值，故赋值为0并+1之后每次加一就可以统计和为相同的sum的次数，而且在后面的计算判断过程中一定会有：如果一个sum可以满足要求，就可以直接将该sum出现的次数记录用于求有多少个元组 满足要求）
- 再遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就用res把map中key对应的value也就是出现次数统计出来。
- 最后返回统计值 res 就可以了
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
int res = 0;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
//统计两个数组中的元素之和，同时统计出现的次数，放入map
for (int i : nums1) {
for (int j : nums2) {
int sum = i + j;
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
}
//统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数
for (int i : nums3) {
for (int j : nums4) {
res += map.getOrDefault(0 - i - j, 0);
}
}
return res;
}
}