6.8哈希表

1. 两数之和

题意描述：

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
提示：

2 <= nums.length <= 104

-109 <= nums[i] <= 109

-109 <= target <= 109

只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

思路：

很明显暴力的解法是两层for循环查找，时间复杂度是O(n^2)。

242. 有效的字母异位词 (opens new window)这道题目是用数组作为哈希表来解决哈希问题，349. 两个数组的交集 (opens new window)这道题目是通过set作为哈希表来解决哈希问题。

当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。

本题呢，我就需要一个集合来存放我们遍历过的元素，然后在遍历数组的时候去询问这个集合，某元素是否遍历过，也就是是否出现在这个集合。

那么我们就应该想到使用哈希法了。

因为本题，我们不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适。

再来看一下使用数组和set来做哈希法的局限。

数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。

set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。

此时就要选择另一种数据结构：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 的底层实现是红黑树。

同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。

这道题目中并不需要key有序，选择std::unordered_map 效率更高！

接下来需要明确两点：

map用来做什么

map中key和value分别表示什么

map目的用来存放我们访问过的元素，因为遍历数组的时候，需要记录我们之前遍历过哪些元素和对应的下标，这样才能找到与当前元素相匹配的（也就是相加等于target）

接下来是map中key和value分别表示什么。

这道题我们需要给出一个元素，判断这个元素是否出现过，如果出现过，返回这个元素的下标。

那么判断元素是否出现，这个元素就要作为key，所以数组中的元素作为key，有key对应的就是value，value用来存下标。

所以 map中的存储结构为 {key：数据元素，value：数组元素对应的下标}。

在遍历数组的时候，只需要向map去查询是否有和目前遍历元素匹配的数值，如果有，就找到的匹配对，如果没有，就把目前遍历的元素放进map中，因为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)

AC代码：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map <int,int> map;
        for(int i = 0; i < nums.size(); i++) {
            // 遍历当前元素，并在map中寻找是否有匹配的key
            auto iter = map.find(target - nums[i]); 
            if(iter != map.end()) {
                return {iter->second, i};
            }
            // 如果没找到匹配对，就把访问过的元素和下标加入到map中
            map.insert(pair<int, int>(nums[i], i)); 
        }
        return {};
    }
};

时间复杂度: O(n)
空间复杂度: O(n)

反思：

本题其实有四个重点：

为什么会想到用哈希表（判断target - nums[i]是否出现过）

哈希表为什么用map(要存储值value跟下标，返回下标)

本题map是用来存什么的（key存值，value存下标）

map中的key和value用来存什么的

把这四点想清楚了，本题才算是理解透彻了。

M:454. 四数相加 II

题意描述：

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

0 <= i, j, k, l < n

nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例 1：
输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
示例 2：
输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1
提示：

n == nums1.length

n == nums2.length

n == nums3.length

n == nums4.length

1 <= n <= 200

-228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228

思路：

本题乍眼一看好像和0015.三数之和 (opens new window)，0018.四数之和 (opens new window)差不多，其实差很多。

本题是使用哈希法的经典题目，而0015.三数之和 (opens new window)，0018.四数之和 (opens new window)并不合适使用哈希法，因为三数之和和四数之和这两道题目使用哈希法在不超时的情况下做到对结果去重是很困难的，很有多细节需要处理。

而这道题目是四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况，所以相对于题目18. 四数之和，题目15.三数之和，还是简单了不少！

如果本题想难度升级：就是给出一个数组（而不是四个数组），在这里找出四个元素相加等于0，答案中不可以包含重复的四元组，大家可以思考一下，后续的文章我也会讲到的。

本题解题步骤：

首先定义一个unordered_map，key放a和b两数之和，value 放a和b两数之和出现的次数。

遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中。

定义int变量count，用来统计a+b+c+d = 0出现的次数。

在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。

最后返回统计值 count 就可以了

AC代码：

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int, int> umap; //key:a+b的数值，value:a+b数值出现的次数
        // 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中
        for (int a : A) {
            for (int b : B) {
                umap[a + b]++;
            }
        }
        int count = 0; // 统计a+b+c+d = 0 出现的次数
        // 在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就把map中key对应的value也就是出现次数统计出来。
        for (int c : C) {
            for (int d : D) {
                if (umap.find(0 - (c + d)) != umap.end()) {
                    count += umap[0 - (c + d)];
                }
            }
        }
        return count;
    }
};

时间复杂度: O(n^2)
空间复杂度: O(n^2)，最坏情况下A和B的值各不相同，相加产生的数字个数为 n^2

M:15. 三数之和

题意描述：

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
提示：

3 <= nums.length <= 3000

-105 <= nums[i] <= 105

思路：

两层for循环就可以确定 a 和b 的数值了，可以使用哈希法来确定 0-(a+b) 是否在数组里出现过，其实这个思路是正确的，但是我们有一个非常棘手的问题，就是题目中说的不可以包含重复的三元组。

把符合条件的三元组放进vector中，然后再去重，这样是非常费时的，很容易超时，也是这道题目通过率如此之低的根源所在。

去重的过程不好处理，有很多小细节，如果在面试中很难想到位。

时间复杂度可以做到O(n^2)，但还是比较费时的，因为不好做剪枝操作。

大家可以尝试使用哈希法写一写，就知道其困难的程度了。

哈希法：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        // 找出a + b + c = 0
        // a = nums[i], b = nums[j], c = -(a + b)
        for (int i = 0; i < nums.size(); i++) {
            // 排序之后如果第一个元素已经大于零，那么不可能凑成三元组
            if (nums[i] > 0) {
                break;
            }
            if (i > 0 && nums[i] == nums[i - 1]) { //三元组元素a去重
                continue;
            }
            unordered_set<int> set;
            for (int j = i + 1; j < nums.size(); j++) {
                if (j > i + 2
                        && nums[j] == nums[j-1]
                        && nums[j-1] == nums[j-2]) { // 三元组元素b去重
                    continue;
                }
                int c = 0 - (nums[i] + nums[j]);
                if (set.find(c) != set.end()) {
                    result.push_back({nums[i], nums[j], c});
                    set.erase(c);// 三元组元素c去重
                } else {
                    set.insert(nums[j]);
                }
            }
        }
        return result;
    }
};

时间复杂度: O(n^2)
空间复杂度: O(n)，额外的 set 开销

双指针法

其实这道题目使用哈希法并不十分合适，因为在去重的操作中有很多细节需要注意，在面试中很难直接写出没有bug的代码。

而且使用哈希法在使用两层for循环的时候，能做的剪枝操作很有限，虽然时间复杂度是O(n^2)，也是可以在leetcode上通过，但是程序的执行时间依然比较长。

接下来我来介绍另一个解法：双指针法，这道题目使用双指针法要比哈希法高效一些，那么来讲解一下具体实现的思路。

动画效果如下：

拿这个nums数组来举例，首先将数组排序，然后有一层for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。

依然还是在数组中找到 a、b、c 使得a + b +c =0，我们这里相当于 a = nums[i]，b = nums[left]，c = nums[right]。

接下来如何移动left 和right呢，如果nums[i] + nums[left] + nums[right] > 0 就说明此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。

如果 nums[i] + nums[left] + nums[right] < 0 说明此时三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。

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

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        // 找出a + b + c = 0
        // a = nums[i], b = nums[left], c = nums[right]
        for (int i = 0; i < nums.size(); i++) {
            // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
            if (nums[i] > 0) {
                return result;
            }
            // 错误去重a方法，将会漏掉-1,-1,2 这种情况
            /*
            if (nums[i] == nums[i + 1]) {
                continue;
            }
            */
            // 正确去重a方法
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = nums.size() - 1;
            while (right > left) {
                // 去重复逻辑如果放在这里，0，0，0 的情况，可能直接导致 right<=left 了，从而漏掉了 0,0,0 这种三元组
                /*
                while (right > left && nums[right] == nums[right - 1]) right--;
                while (right > left && nums[left] == nums[left + 1]) left++;
                */
                if (nums[i] + nums[left] + nums[right] > 0) right--;
                else if (nums[i] + nums[left] + nums[right] < 0) left++;
                else {
                    result.push_back(vector<int>{nums[i], nums[left], nums[right]});
                    // 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;

                    // 找到答案时，双指针同时收缩
                    right--;
                    left++;
                }
            }

        }
        return result;
    }
};

时间复杂度: O(n^2)
空间复杂度: O(1)

去重逻辑的思考

说到去重，其实主要考虑三个数的去重。 a, b ,c, 对应的就是 nums[i]，nums[left]，nums[right]

a的去重

a 如果重复了怎么办，a是nums里遍历的元素，那么应该直接跳过去(continue)。

但这里有一个问题，是判断 nums[i] 与 nums[i + 1]是否相同，还是判断nums[i] 与 nums[i-1]是否相同。

有同学可能想，这不都一样吗。其实不一样！

都是和 nums[i]进行比较，是比较它的前一个，还是比较它的后一个。

如果我们的写法是这样：
if (nums[i] == nums[i + 1]) { // 去重操作
    continue;
}
那我们就把三元组中出现重复元素的情况直接pass掉了。例如{-1, -1 ,2} 这组数据，当遍历到第一个-1 的时候，判断下一个也是-1，那这组数据就pass了。

我们要做的是不能有重复的三元组，但三元组内的元素是可以重复的！

所以这里是有两个重复的维度。

那么应该这么写：
if (i > 0 && nums[i] == nums[i - 1]) {
    continue;
}
这么写就是当前使用 nums[i]，我们判断前一位是不是一样的元素，在看 {-1, -1 ,2} 这组数据，当遍历到第一个 -1 的时候，只要前一位没有-1，那么 {-1, -1 ,2} 这组数据一样可以收录到结果集里。

这是一个非常细节的思考过程。

b与c的去重

很多同学写本题的时候，去重的逻辑多加了对right 和left 的去重：（代码中注释部分）
while (right > left) {
    if (nums[i] + nums[left] + nums[right] > 0) {
        right--;
        // 去重 right
        while (left < right && nums[right] == nums[right + 1]) right--;
    } else if (nums[i] + nums[left] + nums[right] < 0) {
        left++;
        // 去重 left
        while (left < right && nums[left] == nums[left - 1]) left++;
    } else {
    }
}
但细想一下，这种去重其实对提升程序运行效率是没有帮助的。

拿right去重为例，即使不加这个去重逻辑，依然根据 while (right > left) 和 if (nums[i] + nums[left] + nums[right] > 0) 去完成right-- 的操作。

多加了 while (left < right && nums[right] == nums[right + 1]) right--; 这一行代码，其实就是把需要执行的逻辑提前执行了，但并没有减少判断的逻辑。

最直白的思考过程，就是right还是一个数一个数的减下去的，所以在哪里减的都是一样的。

所以这种去重是可以不加的。仅仅是把去重的逻辑提前了而已。

思考

既然三数之和可以使用双指针法，之前的1.两数之和 (opens new window)，可不可以使用双指针法呢？

两数之和不能使用双指针法，因为1.两数之和 (opens new window)要求返回的是索引下标，而双指针法一定要排序，一旦排序之后原数组的索引就被改变了。

如果1.两数之和 (opens new window)要求返回的是数值的话，就可以使用双指针法了。

M:18. 四数之和

题意描述：

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n

a、b、c 和 d 互不相同

nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案。

示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]
提示：

1 <= nums.length <= 200

-109 <= nums[i] <= 109

-109 <= target <= 109

思路：

四数之和，和15.三数之和 (opens new window)是一个思路，都是使用双指针法, 基本解法就是在15.三数之和 (opens new window)的基础上再套一层for循环。

但是有一些细节需要注意，例如：不要判断nums[k] > target 就返回了，三数之和可以通过 nums[i] > 0 就返回了，因为 0 已经是确定的数了，四数之和这道题目 target是任意值。比如：数组是[-4, -3, -2, -1]，target是-10，不能因为-4 > -10而跳过。但是我们依旧可以去做剪枝，逻辑变成nums[i] > target && (nums[i] >=0 || target >= 0)就可以了。

15.三数之和 (opens new window)的双指针解法是一层for循环num[i]为确定值，然后循环内有left和right下标作为双指针，找到nums[i] + nums[left] + nums[right] == 0。

四数之和的双指针解法是两层for循环nums[k] + nums[i]为确定值，依然是循环内有left和right下标作为双指针，找出nums[k] + nums[i] + nums[left] + nums[right] == target的情况，三数之和的时间复杂度是O(n²)，四数之和的时间复杂度是O(n³) 。

那么一样的道理，五数之和、六数之和等等都采用这种解法。

对于15.三数之和 (opens new window)双指针法就是将原本暴力O(n³)的解法，降为O(n²)的解法，四数之和的双指针解法就是将原本暴力O(n⁴)的解法，降为O(n³)的解法。

之前我们讲过哈希表的经典题目：454.四数相加II (opens new window)，相对于本题简单很多，因为本题是要求在一个集合中找出四个数相加等于target，同时四元组不能重复。

而454.四数相加II (opens new window)是四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况，所以相对于本题还是简单了不少！

我们来回顾一下，几道题目使用了双指针法。

双指针法将时间复杂度：O(n^2)的解法优化为 O(n)的解法。也就是降一个数量级，题目如下：

27.移除元素(opens new window)

15.三数之和(opens new window)

18.四数之和(opens new window)

链表相关双指针题目：

206.反转链表(opens new window)

19.删除链表的倒数第N个节点(opens new window)

面试题 02.07. 链表相交(opens new window)

142题.环形链表II(opens new window)

双指针法在字符串题目中还有很多应用，后面还会介绍到。

AC代码：

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
      vector<vector<int>> res;
      sort(nums.begin() , nums.end());
      for(int i = 0 ; i < nums.size() ; i++){
        //剪枝处理
        if(nums[i] > target && nums[i] > 0)  break;// 这里使用break，统一通过最后的return返回
        // 对nums[i]去重
        if(i > 0 && nums[i] == nums[i - 1])  continue;

        for(int j = i + 1 ; j < nums.size() ; j++){
           // 二级剪枝处理
          if(nums[i] + nums[j] > target && nums[i] + nums[j] >= 0)   break;

         // 对nums[i]去重
          if(j > i + 1 && nums[j] == nums[j - 1])  continue;
        int left = j + 1, right = nums.size() - 1;
        while(right > left){
          // nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出
          if((long)nums[i] + nums[j] + nums[left] + nums[right] > target)  right --;

          // nums[k] + nums[i] + nums[left] + nums[right] < target 会溢出
          else if((long)nums[i] + nums[j] +nums[left] + nums[right] < target)  left++;

          else  {res.push_back(vector<int>{nums[i] ,nums[j] , nums[left] , nums[right]});
          
          // 对nums[left]和nums[right]去重
          while(right > left && nums[right] == nums[right - 1]) right --;
          while(right > left && nums[left] == nums[left + 1])  left ++;
          // 找到答案时，双指针同时收缩
          right --;
          left ++;
        }

        }
        }
      }
      return res;
    }
};


时间复杂度: O(n^3)
空间复杂度: O(1)

补充

二级剪枝的部分：
if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
    break;
}
可以优化为：

if (nums[k] + nums[i] > target && nums[i] >= 0) {
    break;
}
因为只要 nums[k] + nums[i] > target，那么 nums[i] 后面的数都是正数的话，就一定不符合条件了。

不过这种剪枝其实有点小绕，大家能够理解文章给的完整代码的剪枝就够了。

哈希表总结篇

常见的三种哈希结构：

数组
set（集合）
map（映射）

什么时候用std::set，什么时候用std::multiset，什么时候用std::unordered_set，都是很有考究的。

只有对这些数据结构的底层实现很熟悉，才能灵活使用，否则很容易写出效率低下的程序。

哈希表经典题目

数组作为哈希表

一些应用场景就是为数组量身定做的。

在242.有效的字母异位词 (opens new window)中，我们提到了数组就是简单的哈希表，但是数组的大小是受限的！

这道题目包含小写字母，那么使用数组来做哈希最合适不过。

在383.赎金信 (opens new window)中同样要求只有小写字母，那么就给我们浓浓的暗示，用数组！

本题和242.有效的字母异位词 (opens new window)很像，242.有效的字母异位词 (opens new window)是求字符串a 和字符串b 是否可以相互组成，在383.赎金信 (opens new window)中是求字符串a能否组成字符串b，而不用管字符串b 能不能组成字符串a。

一些同学可能想，用数组干啥，都用map不就完事了。

上面两道题目用map确实可以，但使用map的空间消耗要比数组大一些，因为map要维护红黑树或者符号表，而且还要做哈希函数的运算。所以数组更加简单直接有效！

set作为哈希表

在349. 两个数组的交集 (opens new window)中我们给出了什么时候用数组就不行了，需要用set。

这道题目没有限制数值的大小，就无法使用数组来做哈希表了。

主要因为如下两点：

数组的大小是有限的，受到系统栈空间（不是数据结构的栈）的限制。

如果数组空间够大，但哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。

所以此时一样的做映射的话，就可以使用set了。

关于set，C++ 给提供了如下三种可用的数据结构：

std::set
std::multiset
std::unordered_set

std::set和std::multiset底层实现都是红黑树，std::unordered_set的底层实现是哈希，使用unordered_set 读写效率是最高的，本题并不需要对数据进行排序，而且还不要让数据重复，所以选择unordered_set。

在202.快乐数 (opens new window)中，我们再次使用了unordered_set来判断一个数是否重复出现过。

map作为哈希表

在1.两数之和 (opens new window)中map正式登场。

来说一说：使用数组和set来做哈希法的局限。

数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。

map是一种<key, value>的结构，本题可以用key保存数值，用value在保存数值所在的下标。所以使用map最为合适。

C++提供如下三种map:

std::map
std::multimap
std::unordered_map

std::unordered_map 底层实现为哈希，std::map 和std::multimap 的底层实现是红黑树。

同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解），1.两数之和 (opens new window)中并不需要key有序，选择std::unordered_map 效率更高！

在454.四数相加 (opens new window)中我们提到了其实需要哈希的地方都能找到map的身影。

本题咋眼一看好像和18. 四数之和 (opens new window)，15.三数之和 (opens new window)差不多，其实差很多！

关键差别是本题为四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑重复问题，而18. 四数之和 (opens new window)，15.三数之和 (opens new window)是一个数组（集合）里找到和为0的组合，可就难很多了！

用哈希法解决了两数之和，很多同学会感觉用哈希法也可以解决三数之和，四数之和。

其实是可以解决，但是非常麻烦，需要去重导致代码效率很低。

在15.三数之和 (opens new window)中我给出了哈希法和双指针两个解法，大家就可以体会到，使用哈希法还是比较麻烦的。

所以18. 四数之和，15.三数之和都推荐使用双指针法！

对于哈希表的知识相信很多同学都知道，但是没有成体系。

同时也强调虽然map是万能的，详细介绍了什么时候用数组，什么时候用set。

标签：map,right,数组,nums,哈希,6.8,left
From： https://www.cnblogs.com/7dragonpig/p/18238941

1. 两数之和

题意描述：

思路：

AC代码：

反思：

M:454. 四数相加 II

题意描述：

思路：

AC代码：

M:15. 三数之和

题意描述：

思路：

哈希法：

双指针法

去重逻辑的思考

a的去重

b与c的去重

思考

M:18. 四数之和

题意描述：

思路：

AC代码：

补充

哈希表总结篇

哈希表经典题目

数组作为哈希表

set作为哈希表

map作为哈希表

相关文章

赞助商

阅读排行