Jackie's Blog
哈希表
Jackie
  2025-02-10   2025-02-19  5.9k 字  26 分钟

哈希表

定义

根据关键码的值而直接进行访问的数据结构

数组也是一张哈希表

哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素

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

哈希函数

以查询学生名字是否属于该学校为例，枚举的时间复杂度为O(n)，而哈希表只需O(1)。将学生姓名映射到哈希表上就涉及到了哈希函数：

通过hashCode把名字转化为数值，一般hashcode是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把学生名字映射为哈希表上的索引数字了

image

数据规模是dataSize， 哈希表大小是tableSize

对数值取模保证映射出来的索引数值都落在哈希表

以下代码实现了一个简单哈希表。其中，将key和value封装成一个类Pair以表示键值对

/* 键值对 */
struct Pair {
  public:
    int key;
    string val;
    Pair(int key, string val) {
        this->key = key;
        this->val = val;
    }
};

/* 基于数组实现的哈希表 */
class ArrayHashMap {
  private:
    vector<Pair *> buckets;

  public:
    ArrayHashMap() {
        // 初始化数组，包含 100 个桶
        buckets = vector<Pair *>(100);
    }

    ~ArrayHashMap() {
        // 释放内存
        for (const auto &bucket : buckets) {
            delete bucket;
        }
        buckets.clear();
    }

    /* 哈希函数 */
    int hashFunc(int key) {
        int index = key % 100;
        return index;
    }

    /* 查询操作 */
    string get(int key) {
        int index = hashFunc(key);
        Pair *pair = buckets[index];
        if (pair == nullptr)
            return "";
        return pair->val;
    }

    /* 添加操作 */
    void put(int key, string val) {
        Pair *pair = new Pair(key, val);
        int index = hashFunc(key);
        buckets[index] = pair;
    }

    /* 删除操作 */
    void remove(int key) {
        int index = hashFunc(key);
        // 释放内存并置为 nullptr
        delete buckets[index];
        buckets[index] = nullptr;
    }

    /* 获取所有键值对 */
    vector<Pair *> pairSet() {
        vector<Pair *> pairSet;
        for (Pair *pair : buckets) {
            if (pair != nullptr) {
                pairSet.push_back(pair);
            }
        }
        return pairSet;
    }

    /* 获取所有键 */
    vector<int> keySet() {
        vector<int> keySet;
        for (Pair *pair : buckets) {
            if (pair != nullptr) {
                keySet.push_back(pair->key);
            }
        }
        return keySet;
    }

    /* 获取所有值 */
    vector<string> valueSet() {
        vector<string> valueSet;
        for (Pair *pair : buckets) {
            if (pair != nullptr) {
                valueSet.push_back(pair->val);
            }
        }
        return valueSet;
    }

    /* 打印哈希表 */
    void print() {
        for (Pair *kv : pairSet()) {
            cout << kv->key << " -> " << kv->val << endl;
        }
    }
};

哈希表的可视化页面

哈希碰撞

如果学生的数量大于哈希表，此时就算哈希函数计算的再均匀，也避免不了会有几位学生的名字同时映射到哈希表同一个索引下标的位置

image

链式地址

将单个元素转换为链表，将键值对作为链表节点，将所有发生冲突的键值对都存储在同一链表中

image

  • 操作
    • 查询元素：输入key，经过哈希函数得到桶索引，即可访问链表头节点，然后遍历链表并对比key以查找目标键值对
    • 添加元素：首先通过哈希函数访问链表头节点，然后将节点（键值对）添加到链表中
    • 删除元素：根据哈希函数的结果访问链表头部，接着遍历链表以查找目标节点并将其删除
  • 局限性
    • 占用空间增大：链表包含节点指针，它相比数组更加耗费内存空间
    • 查询效率降低：因为需要线性遍历链表来查找对应元素
/* 链式地址哈希表 */
class HashMapChaining {
  private:
    int size;                       // 键值对数量
    int capacity;                   // 哈希表容量
    double loadThres;               // 触发扩容的负载因子阈值
    int extendRatio;                // 扩容倍数
    vector<vector<Pair *>> buckets; // 桶数组

  public:
    /* 构造方法 */
    HashMapChaining() : size(0), capacity(4), loadThres(2.0 / 3.0), extendRatio(2) {
        buckets.resize(capacity);
    }

    /* 析构方法 */
    ~HashMapChaining() {
        for (auto &bucket : buckets) {
            for (Pair *pair : bucket) {
                // 释放内存
                delete pair;
            }
        }
    }

    /* 哈希函数 */
    int hashFunc(int key) {
        return key % capacity;
    }

    /* 负载因子 */
    double loadFactor() {
        return (double)size / (double)capacity;
    }

    /* 查询操作 */
    string get(int key) {
        int index = hashFunc(key);
        // 遍历桶，若找到 key ，则返回对应 val
        for (Pair *pair : buckets[index]) {
            if (pair->key == key) {
                return pair->val;
            }
        }
        // 若未找到 key ，则返回空字符串
        return "";
    }

    /* 添加操作 */
    void put(int key, string val) {
        // 当负载因子超过阈值时，执行扩容
        if (loadFactor() > loadThres) {
            extend();
        }
        int index = hashFunc(key);
        // 遍历桶，若遇到指定 key ，则更新对应 val 并返回
        for (Pair *pair : buckets[index]) {
            if (pair->key == key) {
                pair->val = val;
                return;
            }
        }
        // 若无该 key ，则将键值对添加至尾部
        buckets[index].push_back(new Pair(key, val));
        size++;
    }

    /* 删除操作 */
    void remove(int key) {
        int index = hashFunc(key);
        auto &bucket = buckets[index];
        // 遍历桶，从中删除键值对
        for (int i = 0; i < bucket.size(); i++) {
            if (bucket[i]->key == key) {
                Pair *tmp = bucket[i];
                bucket.erase(bucket.begin() + i); // 从中删除键值对
                delete tmp;                       // 释放内存
                size--;
                return;
            }
        }
    }

    /* 扩容哈希表 */
    void extend() {
        // 暂存原哈希表
        vector<vector<Pair *>> bucketsTmp = buckets;
        // 初始化扩容后的新哈希表
        capacity *= extendRatio;
        buckets.clear();
        buckets.resize(capacity);
        size = 0;
        // 将键值对从原哈希表搬运至新哈希表
        for (auto &bucket : bucketsTmp) {
            for (Pair *pair : bucket) {
                put(pair->key, pair->val);
                // 释放内存
                delete pair;
            }
        }
    }

    /* 打印哈希表 */
    void print() {
        for (auto &bucket : buckets) {
            cout << "[";
            for (Pair *pair : bucket) {
                cout << pair->key << " -> " << pair->val << ", ";
            }
            cout << "]\n";
        }
    }
};

开放寻址

不引入额外的数据结构，而是通过多次探测来处理哈希冲突，探测方式主要包括线性探测、平方探测和多次哈希等

开放寻址哈希表都存在不能直接删除元素的问题

线性探测

前提：tableSize>dataSize。需要依靠哈希表中的空位来解决碰撞问题

采用固定步长的线性搜索来进行探测

  • 插入元素：通过哈希函数计算桶索引，若发现桶内已有元素，则从冲突位置向后线性遍历（步长通常为1），直至找到空桶，将元素插入其中
  • 查找元素：若发现哈希冲突，则使用相同步长向后进行线性遍历，直到找到对应元素，返回value即可；如果遇到空桶，说明目标元素不在哈希表中，返回None

image

  • 局限

线性探测容易产生聚集现象

数组中连续被占用的位置越长，这些连续位置发生哈希冲突的可能性越大，从而进一步促使该位置的聚堆生长，形成恶性循环，最终导致增删查改操作效率劣化

不能在开放寻址哈希表中直接删除元素

删除元素会在数组内产生一个空桶None，而当查询元素时，线性探测到该空桶就会返回，因此在该空桶之下的元素都无法再被访问到，程序可能误判这些元素不存在

可以采用懒删除机制：它不直接从哈希表中移除元素，而是利用一个常量TOMBSTONE来标记这个桶。该机制下，None和TOMBSTONE都代表空桶，都可以放置键值对。但不同的是，线性探测到TOMBSTONE时应该继续遍历，因为其之下可能还存在键值对

懒删除可能会加速哈希表的性能退化。这是因为每次删除操作都会产生一个删除标记，随着TOMBSTONE的增加，搜索时间也会增加，因为线性探测可能需要跳过多个TOMBSTONE才能找到目标元素

为此，考虑在线性探测中记录遇到的首个TOMBSTONE的索引，并将搜索到的目标元素与该TOMBSTONE交换位置。这样做的好处是当每次查询或添加元素时元素会被移动至距离理想位置（探测起始点）更近的桶，从而优化查询效率

/* 开放寻址哈希表 */
class HashMapOpenAddressing {
  private:
    int size;                             // 键值对数量
    int capacity = 4;                     // 哈希表容量
    const double loadThres = 2.0 / 3.0;     // 触发扩容的负载因子阈值
    const int extendRatio = 2;            // 扩容倍数
    vector<Pair *> buckets;               // 桶数组
    Pair *TOMBSTONE = new Pair(-1, "-1"); // 删除标记

  public:
    /* 构造方法 */
    HashMapOpenAddressing() : size(0), buckets(capacity, nullptr) {
    }

    /* 析构方法 */
    ~HashMapOpenAddressing() {
        for (Pair *pair : buckets) {
            if (pair != nullptr && pair != TOMBSTONE) {
                delete pair;
            }
        }
        delete TOMBSTONE;
    }

    /* 哈希函数 */
    int hashFunc(int key) {
        return key % capacity;
    }

    /* 负载因子 */
    double loadFactor() {
        return (double)size / capacity;
    }

    /* 搜索 key 对应的桶索引 */
    int findBucket(int key) {
        int index = hashFunc(key);
        int firstTombstone = -1;
        // 线性探测，当遇到空桶时跳出
        while (buckets[index] != nullptr) {
            // 若遇到 key ，返回对应的桶索引
            if (buckets[index]->key == key) {
                // 若之前遇到了删除标记，则将键值对移动至该索引处
                if (firstTombstone != -1) {
                    buckets[firstTombstone] = buckets[index];
                    buckets[index] = TOMBSTONE;
                    return firstTombstone; // 返回移动后的桶索引
                }
                return index; // 返回桶索引
            }
            // 记录遇到的首个删除标记
            if (firstTombstone == -1 && buckets[index] == TOMBSTONE) {
                firstTombstone = index;
            }
            // 计算桶索引，越过尾部则返回头部
            index = (index + 1) % capacity;
        }
        // 若 key 不存在，则返回添加点的索引
        return firstTombstone == -1 ? index : firstTombstone;
    }

    /* 查询操作 */
    string get(int key) {
        // 搜索 key 对应的桶索引
        int index = findBucket(key);
        // 若找到键值对，则返回对应 val
        if (buckets[index] != nullptr && buckets[index] != TOMBSTONE) {
            return buckets[index]->val;
        }
        // 若键值对不存在，则返回空字符串
        return "";
    }

    /* 添加操作 */
    void put(int key, string val) {
        // 当负载因子超过阈值时，执行扩容
        if (loadFactor() > loadThres) {
            extend();
        }
        // 搜索 key 对应的桶索引
        int index = findBucket(key);
        // 若找到键值对，则覆盖 val 并返回
        if (buckets[index] != nullptr && buckets[index] != TOMBSTONE) {
            buckets[index]->val = val;
            return;
        }
        // 若键值对不存在，则添加该键值对
        buckets[index] = new Pair(key, val);
        size++;
    }

    /* 删除操作 */
    void remove(int key) {
        // 搜索 key 对应的桶索引
        int index = findBucket(key);
        // 若找到键值对，则用删除标记覆盖它
        if (buckets[index] != nullptr && buckets[index] != TOMBSTONE) {
            delete buckets[index];
            buckets[index] = TOMBSTONE;
            size--;
        }
    }

    /* 扩容哈希表 */
    void extend() {
        // 暂存原哈希表
        vector<Pair *> bucketsTmp = buckets;
        // 初始化扩容后的新哈希表
        capacity *= extendRatio;
        buckets = vector<Pair *>(capacity, nullptr);
        size = 0;
        // 将键值对从原哈希表搬运至新哈希表
        for (Pair *pair : bucketsTmp) {
            if (pair != nullptr && pair != TOMBSTONE) {
                put(pair->key, pair->val);
                delete pair;
            }
        }
    }

    /* 打印哈希表 */
    void print() {
        for (Pair *pair : buckets) {
            if (pair == nullptr) {
                cout << "nullptr" << endl;
            } else if (pair == TOMBSTONE) {
                cout << "TOMBSTONE" << endl;
            } else {
                cout << pair->key << " -> " << pair->val << endl;
            }
        }
    }
};
平方探测

发生冲突时，平方探测跳过“探测次数的平方”的步数，即1、4、9…步

  • 优势

平方探测通过跳过探测次数平方的距离，试图缓解线性探测的聚集效应

平方探测会跳过更大的距离来寻找空位置，有助于数据分布得更加均匀

  • 局限

仍然存在聚集现象，即某些位置比其他位置更容易被占用

由于平方的增长，平方探测可能不会探测整个哈希表，这意味着即使哈希表中有空桶，平方探测也可能无法访问到它

多次哈希

使用多个哈希函数f1(x)、f2(x)、f3(x)…进行探测

  • 插入元素：若哈希函数f1(x)出现冲突，则尝试f2(x)，以此类推，直到找到空位后插入元素
  • 查找元素：在相同的哈希函数顺序下进行查找，直到找到目标元素时返回；若遇到空位或已尝试所有哈希函数，说明哈希表中不存在该元素，则返回None

多个哈希函数会带来额外的计算量

常见的三种哈希结构

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

map的空间消耗比数组大一些，因为map要维护红黑树或者哈希表，而且还要做哈希函数，会更加费时

set

使用集合来解决哈希问题优先使用unordered_set

它的查询和增删效率是最优的

集合有序用set

集合不仅有序还有重复数据用multiset

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

std::unordered_set底层实现为哈希表，std::set和std::multiset的底层实现是红黑树

红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加

虽然std::set和std::multiset的底层实现基于红黑树而非哈希表，它们通过红黑树来索引和存储数据。不过给我们的使用方式，还是哈希法的使用方式，即依靠键（key）来访问值（value）。所以使用这些数据结构来解决映射问题的方法，我们依然称之为哈希法。std::map也是一样的道理

Q：hash_set、hash_map与unordered_set、unordered_map的关系？

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

image

map

映射 底层实现 是否有序 数值是否可以重复 能否更改数值 查询效率 增删效率
std::map 红黑树 key有序 key不可重复 key不可修改 O(logn) O(logn)
std::multimap 红黑树 key有序 key可重复 key不可修改 O(logn) O(logn)
std::unordered_map 哈希表 key无序 key不可重复 key不可修改 O(1) O(1)

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

同理，std::map和std::multimap的key也是有序的

map是一个key value的数据结构，map中对key有限制，对value没有限制

因为key的存储方式使用红黑树实现的

unordered_map的迭代器iterator遍历容器中的键值对。迭代器指向的是一个键值对（pair），可以通过迭代器访问键和值：

  • iter->first：表示键（key）
  • iter->second：表示值（value）

总结

数据小用数组，数据大用set，数据比较散用map

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

哈希法牺牲了空间换取了时间

因为要用额外的数组set或map来存数据才能实现快速查找

有效的字母异位词

242. 有效的字母异位词

字母异位词：通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次

同分异构体

image

class Solution {
public:
    bool isAnagram(string s, string t) {
        int record[26]={0};
        for(int i=0;i<s.size();i++){
            record[s[i]-'a']++;
        }
        for(int i=0;i<s.size();i++){
            record[t[i]-'a']--;
        }
        for(int i=0;i<26;i++){
            if(record[i]!=0){
                return false;
            }
        }
        return true;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

两个数组的交集

349. 两个数组的交集

题目特意说明：输出结果中的每个元素一定是唯一的，即输出的结果的去重的且可不考虑输出结果的顺序

unordered_set

范围for循环

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set;
        unordered_set<int> nums_set(nums1.begin(),nums1.end());
        for(int num:nums2){
            //发现nums2的元素在nums_set里又出现过
            if(nums_set.find(num)!=nums_set.end()){
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(),result_set.end());
    }
};
  • 时间复杂度：O(n+m)，m是最后要把set转成vector
  • 空间复杂度：O(n)

快乐数

202. 快乐数

  • 快乐数

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

无限循环说明求和的过程中sum会重复出现

使用哈希法判断sum是否重复出现，如果重复return false， 否则一直找到sum为1为止

class Solution {
public:
    bool isHappy(int n) {
        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;
        }
    }
    int GetSum(int n){
        int sum=0;
        while(n){
            sum+=(n%10)*(n%10);
            n/=10;
        }
        return sum;
    }
};
  • 时间复杂度：O(logn)
  • 空间复杂度：O(logn)

两数之和

1. 两数之和

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

  • 此题数组&set的局限

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

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

image

image

iterator

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> map;
        for(int i=0;i<nums.size();i++){
            unordered_map<int, int>::iterator iter=map.find(target-nums[i]);
            if(iter!=map.end()){
                return {iter->second,i};
             }
            map.insert(pair<int,int>(nums[i],i));
        }
        return {};
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

四数相加II

454. 四数相加 II

key：a+b的数值，value：a+b数值出现的次数

count：统计a+b+c+d=0出现的次数

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int,int> umap;
        for(int a:nums1){
            for(int b:nums2){
                umap[a+b]++;
            }
        }
        int count=0;
        for(int c:nums3){
            for(int d:nums4){
                if(umap.find(0-(c+d))!=umap.end()){
                    count+=umap[0-(c+d)];
                }
            }
        }
        return count;
    }
};
  • 时间复杂度：O(n2)
  • 空间复杂度：O(n2)，最坏情况下A和B的值各不相同，相加产生的数字个数为n2

赎金信

383. 赎金信

  • “为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思”这里说明杂志里面的字母不可重复使用
  • “你可以假设两个字符串均只含有小写字母”说明只有小写字母

暴力法

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        for(int i=0;i<magazine.length();i++){
            for(int j=0;j<ransomNote.length();j++){
                if(magazine[i]==ransomNote[j]){
                    ransomNote.erase(ransomNote.begin()+j);
                    break;
                }
            }
        }
        if(ransomNote.length()==0){
            return true;
        }
        return false;
    }
};
  • 时间复杂度：O(n2)
  • 空间复杂度：O(1)

哈希法

只有小写字母，则可以空间换时间，用长度26的数组记录magazine里字母出现的次数

再用ransomNote验证数组是否包含ransomNote所需要的字母

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int record[26]={0};
        if(ransomNote.size()>magazine.size()){
            return false;
        }
        for(int i=0;i<magazine.length();i++){
            record[magazine[i]-'a']++;
        }
        for(int j=0;j<ransomNote.length();j++){
            record[ransomNote[j]-'a']--;
            if(record[ransomNote[j]-'a']<0){
                return false;
            }
        }
        return true;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

三数之和

15. 三数之和

三元组不重复，但是三元组里面的元素可以重复： {0,0,0}

nums[i]==nums[i-1]：{-1,-1,2}

如果是nums[i]与nums[i+1]

此时把三元组中出现重复元素的情况直接pass掉了。如{-1,-1,2}这组数据，当遍历到第一个-1的时候，判断下一个也是-1，那这组数据就pass了

哈希法

vector<vector<int>> result

剪枝：减少搜索空间，提高算法的效率

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size();i++){
            if(nums[i]>0){//第一个最小的元素都大于0，则后面的数不可能三个数相加为0
                break;
            }
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            unordered_set<int> set;
            for(int k=i+1;k<nums.size();k++){
                if(k>i+2&&nums[k]==nums[k-1]&&nums[k-1]==nums[k-2]){
                    continue;
                }
                int target=0-(nums[i]+nums[k]);
                if(set.find(target)!=set.end()){
                    result.push_back({nums[i],target,nums[k]});
                    set.erase(target);
                }else{
                    set.insert(nums[k]);
                }
            }
        }
        return result;
    }
};
  • 时间复杂度：O(n2)
  • 空间复杂度：O(n)，额外的set开销

双指针法

这道题目使用双指针法要比哈希法高效

image

将数组排序，这里相当于a=nums[i]，b=nums[left]，c=nums[right]

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size();i++){
            if(nums.size()<3||nums[i]>0){
                break;
            }
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            int left=i+1;
            int right=nums.size()-1;
            while(right>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]});
                    //0 -1 -1 -1 -1 1 1 1 1
                    //i  l                r
                    //去重的逻辑一定要放在收获结果的下面，即至少要收获一个符合条件的结果
                    while(right>left&&nums[right]==nums[right-1]){
                        right--;
                    }
                    while(right>left&&nums[left]==nums[left+1]){
                        left++;
                    }
                    right--;
                    left++;
                }
            }
        }
        return result;
    }
};
  • 时间复杂度：O(n2)
  • 空间复杂度：O(logn)排序额外使用了空间

四数之和

18. 四数之和

双指针法

在三数之和基础上多加一层循环及一级二级剪枝、去重

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(),nums.end());
        for(int k=0;k<nums.size();k++){
            if(nums[k]>target&&nums[k]>=0){//traget可能为负数
                break;
            }
            if(k>0&&nums[k]==nums[k-1]){
                continue;
            }
            for(int i=k+1;i<nums.size();i++){
                if(nums[k]+nums[i]>target&&nums[k]+nums[i]>=0){
                    break;
                }
                if(i>k+1&&nums[i]==nums[i-1]){//对nums[i]去重
                    continue;
                }
                int left=i+1;
                int right=nums.size()-1;
                while(right>left){
                    if(nums[k]+nums[i]+nums[left]+nums[right]>target){
                        right--;
                    }else if(nums[k]+nums[i]+nums[left]+nums[right]<target){
                        left++;
                    }else{
                        result.push_back(vector<int>{nums[k],nums[i],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 result;
    }
};
  • 时间复杂度：O(n3)
  • 空间复杂度：O(logn)排序额外使用了空间
 评论
评论插件加载失败
正在加载评论插件
  1. 哈希表
    1. 定义
      1. 哈希函数
      2. 哈希碰撞
        1. 链式地址
        2. 开放寻址
          1. 线性探测
          2. 平方探测
          3. 多次哈希
      3. 常见的三种哈希结构
        1. set
        2. map
      4. 总结
    2. 有效的字母异位词
    3. 两个数组的交集
    4. 快乐数
    5. 两数之和
    6. 四数相加II
    7. 赎金信
      1. 暴力法
      2. 哈希法
    8. 三数之和
      1. 哈希法
      2. 双指针法
    9. 四数之和
      1. 双指针法
  1. 哈希表
    1. 定义
      1. 哈希函数
      2. 哈希碰撞
        1. 链式地址
        2. 开放寻址
          1. 线性探测
          2. 平方探测
          3. 多次哈希
      3. 常见的三种哈希结构
        1. set
        2. map
      4. 总结
    2. 有效的字母异位词
    3. 两个数组的交集
    4. 快乐数
    5. 两数之和
    6. 四数相加II
    7. 赎金信
      1. 暴力法
      2. 哈希法
    8. 三数之和
      1. 哈希法
      2. 双指针法
    9. 四数之和
      1. 双指针法