哈希表

哈希表基础理论

哈希表（Hash table）又称散列表，是根据关键码的值而直接进行访问的数据结构。

数组就是一张哈希表，关键码对应数组的索引下标，然后通过下标直接访问数组中的元素，如下图所示：

哈希表可以用来快速判断一个元素是否出现在集合里。

哈希函数

哈希函数通过hashCode把名字转化为数值，一般hashCode是同多特定编码方式，可以将其他数据格式转化为不同的数值。

哈希碰撞

如图所示，小李和小王都映射到了索引下标 1 的位置，这一现象叫做哈希碰撞。

一般解决方法有两种，拉链法和线性探测法。

拉链法

小李和小王在索引1的位置发生了冲突，发生冲突的元素都被存储在链表中。 这样就通过索引找到小李和小王了。

（数据规模是dataSize， 哈希表的大小为tableSize）

拉链法要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。

线性探测法

依靠哈希表中的空位来解决碰撞问题。例如冲突的位置，放了小李，那么就向下找一个空位放置小王的信息。

所以要求tableSize一定要大于dataSize ，要不然哈希表上就没有空位来存放冲突的数据了。如图所示：

常见的三种哈希结构

• 数组

• set（集合）

• map（映射）

在C++中，set 和 map 分别提供以下三种数据结构，其底层实现以及优劣如下表所示：

集合	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
std::set	红黑树	有序	否	否
std::multiset	红黑树	有序	是	否
std::unordered_set	哈希表	无序	否	否

• std::unordered_map 底层实现为哈希表
• std::map 和std::multimap 的底层实现是红黑树。
• std::map 和std::multimap 的key是有序的。

set

当使用集合来解决哈希问题的时候

• 优先使用unordered_set，因为它的查询和增删效率是最优的
• 若需集合是有序的，那么就用set
• 若要求不仅有序还要有重复数据的话，用multiset

map

map 是一个key value的数据结构，map中，对key是有限制，对value没有限制的，因为key的存储方式使用红黑树实现的。java里的HashMap ，TreeMap 都是一样的原理。

虽然std::set、std::multiset 的底层实现是红黑树，不是哈希表，std::set、std::multiset 使用红黑树来索引和存储，不过使用方式，还是哈希法的使用方式，即key和value。

unordered_set在C++11的时候被引入标准库了，而hash_set并没有，所以建议使用unordered_set比较好，这就好比一个是官方认证的，hash_set，hash_map 是C++11标准之前民间高手自发造的轮子。

总结

总结一下，当们遇到要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。

但哈希法也是牺牲了空间换取了时间，因为要使用额外的数组，set或map来存放数据，实现快速的查找。

242.有效的字母异位词

力扣题目链接

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1:
输入: s = “anagram”, t = “nagaram”
输出: true

示例 2:
输入: s = “rat”, t = “car”
输出: false

说明:
你可以假设字符串只包含小写字母。

思路

数组就是一个简单哈希表，而且这道题目中字符串只有小写字符，那么就可以定义一个数组，来记录字符串s里字符出现的次数。定一个大小为26的数组，数组的元素分别代表’a‘~’z‘字母，初始化为0，因为字符a到字符z的ASCII也是26个连续的数值。

为了方便举例，判断一下字符串s= “aee”, t = “eae”。

操作动画如下：

C++代码

• 时间复杂度：
• 空间复杂的：

class Solution {
public:
    bool isAnagram(string s, string t) {
		if (s.size() != t.size()) return false;
         vector<int> record(26,0);
        for (int i = 0; i < s.size(); i++){
	        // 用数组记录s中各个字母出现的次数
            record[s[i] - 'a']++;
	        // 计算t中各个字母出现的次数
            record[t[i] - 'a']--;
        }
        // 看数组中各个元素是不是都为0
        for (int i = 0; i < 26; i++){
            if(record[i] != 0 ) return false;
        }
        return true;

    }
};

1002. 查找共用字符

力扣题目链接

给你一个字符串数组 words ，请你找出所有在 words 的每个字符串中都出现的共用字符（ 包括重复字符），并以数组形式返回。你可以按 任意顺序 返回答案。

示例 1：

输入：words = [“bella”,“label”,“roller”]
输出：[“e”,“l”,“l”]
示例 2：

输入：words = [“cool”,“lock”,“cook”]
输出：[“c”,“o”]

提示：

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] 由小写英文字母组成

C++代码

class Solution {
 public:
  vector<string> commonChars(vector<string>& words) {
    vector<int> minCount(26, INT_MAX); 
    for (const string& word : words) { 
      vector<int> currentCount(26, 0); 
      
      for (char c : word) {
        currentCount[c - 'a']++;
      }

      for (int i = 0; i < 26; ++i) {
        minCount[i] = min(minCount[i], currentCount[i]);
      }
    }

    vector<string> result;
    for (int i = 0; i < 26; ++i) {
      if (minCount[i] > 0) {
        result.insert(result.end(), minCount[i], string(1, 'a' + i));
      }
    }

    return result;
  }
};

1. 初始化 minCount

   • minCount 是一个长度为 26 的向量，用于记录每个字母在所有字符串中出现的最小次数。初始化时，将所有位置的值设置为 INT_MAX，表示尚未确定最小值。

2. 处理每个字符串

   • 通过 for 循环遍历 words 中的每一个字符串 word。

   • currentCount 是一个局部向量，用于记录当前字符串中每个字母的出现次数。初始化时，每个字母的计数都为 0。

   • 对于字符串 word 中的每个字符 c，更新 currentCount 向量中对应字母的计数。c - 'a' 将字符 c 转换为字母表中的索引（0 到 25）。

   • 遍历 currentCount 中的每个计数值，并更新 minCount 向量中的最小值。minCount[i] 保存了在所有处理过的字符串中字符 i 的最小出现次数。

3. 构建结果向量

   • 初始化结果向量 result，用于存储最终的结果。

   • 遍历 minCount 向量，对于每个位置 i，如果 minCount[i] 大于 0，说明该字母在所有字符串中都有出现。

   • 使用 result.insert(result.end(), minCount[i], string(1, 'a' + i)) 将字符 i 添加到 result 向量中，数量为 minCount[i]。string(1, 'a' + i) 生成一个长度为 1的字符串，内容是字符 ‘a’ + i。

4. 返回结果

   • 返回最终的 result 向量，它包含了所有在所有字符串中共同出现的字符，并按照出现次数排序。

总结

这段代码的主要目的是找到多个字符串中共同出现的字符，并且根据它们在所有字符串中的最小出现次数生成结果。通过维护一个全局的最小计数向量和一个逐字符串更新的计数向量，代码实现了一个高效且通用的解决方案。

349. 两个数组的交集

力扣题目链接

题意：给定两个数组，编写一个函数来计算它们的交集。

说明：
输出结果中的每个元素一定是唯一的。可以不考虑输出结果的顺序。

std::unordered_set 是 C++ 标准库中的一个容器，它是一个集合（Set）的实现，用于存储不重复的元素，且内部元素没有特定的顺序。这意味着在 unordered_set 中，元素的插入、查找和删除操作的时间复杂度都是 O(1)，即平均情况下的操作效率非常高。

思路

之前两道题使用数组来做哈希的题目，是因为题目都限制了数值的大小。而这道题目没有限制数值的大小，就无法使用数组来做哈希表了。而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。

此时就要使用另一种结构体了，set ，C++ 给提供了如下三种可用的数据结构：

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

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

思路如图所示：

以下是对 std::unordered_set 的详细解释：

1. 无序集合的特点：
   • 存储唯一的元素：unordered_set 中不能有重复的元素，每个元素只能出现一次。
   • 内部无序：unordered_set 不会维护元素的顺序，因此不能通过索引访问元素。
   • 基于哈希表：unordered_set 的实现基于哈希表，这使得插入、查找和删除操作具有常数时间复杂度的优势。
   • 元素类型：可以存储任意支持哈希函数的元素类型，例如内置整数类型、自定义结构体、字符串等。
2. 使用方法：
   • 创建 unordered_set 对象：可以通过多种方式创建 unordered_set，比如使用默认构造函数，或者传递其他容器（如 vector、list）的迭代器范围来初始化。
   • 插入元素：使用 insert() 方法将新的元素插入到 unordered_set 中，如果元素已经存在，则插入操作不会改变集合。
   • 删除元素：使用 erase() 方法可以删除指定元素，或者使用迭代器删除一个元素。
   • 查找元素：可以使用 find() 方法来查找指定元素是否存在于集合中，如果找到了，find() 方法会返回该元素的迭代器；否则返回 unordered_set::end()。
   • 大小和清空：size() 方法可以返回集合中的元素个数，而 clear() 方法可以清空集合中的所有元素。

总结：unordered_set 是 C++ 中用于存储不重复元素的无序集合，其内部实现基于哈希表，具有高效的插入、查找和删除操作。使用 unordered_set 可以快速解决查找唯一元素的问题，并且适用于各种元素类型。

C++代码

• 时间复杂度:
• 空间复杂度:

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        //使用unordered_set，存放nums1，然后在去那nums2中的数找，若有添加到res中
        // 存放nums1并去重
        unordered_set<int> set(nums1.begin(), nums1.end());
        unordered_set<int> res;
        for (int i = 0; i < nums2.size(); i++){
            // 若nums1中存在nums2的元素，则为交集
            if (set.find(nums2[i]) != set.end()){
                res.insert(nums2[i]);
            }
        }
        vector<int> result (res.begin(), res.end());
        return result;
    }   
};

202. 快乐数

力扣题目链接

编写一个算法来判断一个数 n 是不是快乐数。

快乐数定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为  1，那么这个数就是快乐数。

如果 n 是快乐数就返回 True ；不是，则返回 False 。

示例：

输入：19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

思路

题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！

**当遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。**所以这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止。

判断sum是否重复出现就可以使用unordered_set。

还有一个难点就是求和的过程，如果对取数值各个位上的单数操作不熟悉的话，做这道题也会比较艰难。

C++代码下：

• 时间复杂度:
• 空间复杂度:

class Solution {
public:
    // 计算n各位的平方和
    int getSum ( int n ){
        int sum = 0;
        while (n){
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }

    bool isHappy(int n) {
        // 用一个set记录平方和
        unordered_set<int> set;
        while (true){
            int sum = getSum(n);
            // 是快乐数
            if (sum == 1) return true;
            // 若集合中存在sum，不是快乐数
            if (set.find(sum) != set.end()){
                return false;
            } else {
                set.insert(sum);
            }
            n = sum; // 别忘了
        }
    }
};

1. 两数之和

力扣题目链接

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

思路

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

若使用数组和set会有局限性。

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

接下来需要明确两点：

• map用来做什么

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

• map中key和value分别表示什么

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

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

在遍历数组的时候，只需要向map去查询是否有和目前遍历元素匹配的数值，如果有，就找到的匹配对，如果没有，就把目前遍历的元素放进map中，因为map存放的就是访问过的元素。

C++代码

• 时间复杂度:
• 空间复杂度:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // 存放（值，索引） 
        unordered_map<int, int> map;

        for (int i = 0; i < nums.size(); i++){
            int num = target - nums[i];
            if (map.count(num)){
                return {map[num], i};
            }
            map.insert(pair(nums[i], i));
            // map[nums[i]] = i;
        }
        return {};
    }
};

总结

本题其实有四个重点：

• 为什么会想到用哈希表
• 哈希表为什么用map
• 本题map是用来存什么的
• map中的key和value用来存什么的

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

解释:

两个元组如下:

1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

思路

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

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

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

本题解题步骤：

1. 首先定义 一个unordered_map，key放a和b两数之和，value 放a和b两数之和出现的次数。
2. 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中。
3. 定义int变量count，用来统计 a+b+c+d = 0 出现的次数。
4. 在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。
5. 最后返回统计值 count 就可以了

C++代码:

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

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;
    }
};

383. 赎金信

力扣题目链接

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。

(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)

注意：

你可以假设两个字符串均只含有小写字母。

canConstruct(“a”, “b”) -> false
canConstruct(“aa”, “ab”) -> false
canConstruct(“aa”, “aab”) -> true

思路

哈希解法

因为题目所只有小写字母，那可以采用空间换取时间的哈希策略， 用一个长度为26的数组还记录magazine里字母出现的次数。

然后再用ransomNote去验证这个数组是否包含了ransomNote所需要的所有字母。

依然是数组在哈希法中的应用。

一些同学可能想，用数组干啥，都用map完事了，其实在本题的情况下，使用map的空间消耗要比数组大一些的，因为map要维护红黑树或者哈希表，而且还要做哈希函数，是费时的！数据量大的话就能体现出来差别了。 所以数组更加简单直接有效！

magazine.at(i)提供了更安全的访问方式，可以确保在索引越界时抛出异常，而magazine[i]则需要在使用时自行确保索引不越界，否则可能导致程序出现不稳定行为。

C++ 代码

• 时间复杂度:
• 空间复杂度:

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        vector<int> record(26,0);

        if (ransomNote.size() > magazine.size()) {
            return false;
        }
        for (int i = 0; i < magazine.size(); i++){
            // 通过recode数据记录 magazine里各个字符出现次数
            record[magazine.at(i) - 'a']++;
        }
        for (int i = 0; i < ransomNote.size(); i++) {
            // 遍历ransomNote，在record里对应的字符个数做--操作
            record[ransomNote.at(i) - 'a']--;
            // 如果小于零说明ransomNote里出现的字符，magazine没有
            if (record[ransomNote.at(i) - 'a'] < 0){
                return false;
            }
        }
        return true;
    }
};

15. 三数之和

力扣题目链接

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

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

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

思路

双指针

动画效果如下：

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

依然还是在数组中找到 abc 使得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相遇为止。

时间复杂度：。

C++代码

• 时间复杂度:
• 空间复杂度:

class Solution {
  public:
    vector<vector<int>> threeSum(vector<int> &nums) {
        // 排序 + 双指针
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;

        for (int i = 0; i < nums.size() - 2; i++) {
            // 若数组中最小的值大于0
            if (nums[i] > 0) return res;
            // 若i相同
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int left = i + 1;
            int right = nums.size() - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum < 0) left++;
                else if (sum > 0) right--;
                else {
                    res.push_back(vector<int>{nums[i], nums[left], nums[right]});
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    left++;
                    right--;
                }
            }
        }
        return res;
    }
};

a的去重

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

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

但这里有一个问题，是判断 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还是一个数一个数的减下去的，所以在哪里减的都是一样的。

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

18. 四数之和

力扣题目链接

题意：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

思路

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

但是有一些细节需要注意，例如： 不要判断nums[k] > target 就返回了，三数之和 可以通过 nums[i] > 0 就返回了，因为 0 已经是确定的数了，四数之和这道题目 target是任意值，逻辑变成nums[i] > target && (nums[i] >=0 || target >= 0)。

15.三数之和的双指针解法是一层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的情况，三数之和的时间复杂度是，四数之和的时间复杂度是 。

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

对于15.三数之和双指针法就是将原本暴力的解法，降为的解法，四数之和的双指针解法就是将原本暴力的解法，降为的解法。

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

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

C++

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        vector<vector<int>> res;

        for (int i = 0; i < nums.size(); i++){
            // if (nums[i] > target) return res; 错误剪枝，因为值是任意值
            if (nums[i] > target && nums[i] >= 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            for (int k = i + 1; k < nums.size(); k++){
                // 2级剪枝处理
                if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
                    break;
                }
                int left = k + 1;
                int right = nums.size() - 1;
                if (k > i + 1 && nums[k] == nums[k - 1]) continue; // k > i+ 1
                while (left < right) {
                    long sum = (long)nums[i] + nums[k] + nums[left] + nums[right]; // 数值太大超过int了
                    if (sum < target) left++;
                    else if (sum > target) right--;
                    else {
                        res.push_back(vector<int>{nums[i], nums[k], nums[left], nums[right]});
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        left++;
                        right--;
                    }
                }
                                    
            }
        }
        return res;
    }
};

补充

二级剪枝的部分：

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] 后面的数都是正数的话，就一定 不符合条件了。

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

总结

哈希表理论基础

一般来说哈希表都是用来快速判断一个元素是否出现集合里。

对于哈希表，要知道哈希函数和哈希碰撞在哈希表中的作用.

• 哈希函数是把传入的key映射到符号表的索引上。

• 哈希碰撞处理有多个key映射到相同索引上时的情景，处理碰撞的普遍方式是拉链法和线性探测法。

接下来是常见的三种哈希结构：

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

哈希表经典题目

数组作为哈希表

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

• 242.有效的字母异位词中，提到了数组就是简单的哈希表，但是数组的大小是受限的！这道题目包含小写字母，那么使用数组来做哈希最合适不过。

• 383.赎金信中同样要求只有小写字母，那么就给浓浓的暗示，用数组！

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

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

set作为哈希表

在349. 两个数组的交集中给出了什么时候用数组就不行了，需要用set。

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

主要因为如下两点：

• 数组的大小是有限的，受到系统栈空间（不是数据结构的栈）的限制。
• 如果数组空间够大，但哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。

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

关于set，C++ 给提供了如下三种可用的数据结构：（详情请看关于哈希表，你该了解这些！）

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

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

在202.快乐数中，再次使用了unordered_set来判断一个数是否重复出现过。

map作为哈希表

在1.两数之和中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.两数之和中并不需要key有序，选择std::unordered_map效率更高！

在454.四数相加中提到了其实需要哈希的地方都能找到map的身影。

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

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

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

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

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

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

本篇从哈希表的理论基础到数组、set和map的经典应用，把哈希表的整个全貌完整的呈现给大家。

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