AI 助理
备案控制台
开发者社区 云原生 文章 正文

【代码随想录】第5章：哈希表

2022-10-30 150
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【代码随想录】第5章：哈希表

哈希表

1. 哈希表理论基础


哈希表有一个现象：哈希冲突


解决哈希冲突的方法：拉链法，线性探测法


常见的三种哈希结构：


  1. 数组


  1. set


  1. map


哈希查找：O(1)


枚举查找：O(n)



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



2. 有效的字母异位词


242. 有效的字母异位词【简单】



思路一：sort()函数先对字符串进行排序，在判断两个字符串相等。时间复杂度高


思路二：桶排序；对字符串1进行++计数；对字符串2进行–计数；判断最后桶中是否都为0


思路三：哈希表计数；思路还是桶排序的思路，只是用哈希表实现


代码只记录思路三的，其他两个不写。


时间复杂度：O(n) n为字符串长度


空间复杂度：O(S) S为字符集大小


class Solution {
public:
  bool isAnagram(string s, string t) {
    if (s.size() != t.size())  return false;  //字符串长度不相等  false
    unordered_map<char, int> map;
    for (int i = 0; i < s.size(); i++) {   //计数；一个++；一个--
      map[s[i]]++;
      map[t[i]]--;
    }
    for (auto p : map) {
      if (p.second != 0) return false;  //最后计数必须为0
    }
    return true;
  }
};


383. 赎金信【简单】



题目意思：判断字符串a中的字符能不能构成字符串b


思路一：sort()排序+双for暴力枚举


思路二：暴力枚举+erase()函数


// 时间复杂度: O(n^2)
// 空间复杂度：O(1)
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++) {
                // 在ransomNote中找到和magazine相同的字符
                if (magazine[i] == ransomNote[j]) {
                    ransomNote.erase(ransomNote.begin() + j); // ransomNote删除这个字符
                    break;
                }
            }
        }
        // 如果ransomNote为空，则说明magazine的字符可以组成ransomNote
        if (ransomNote.length() == 0) {
            return true;
        }
        return false;
    }
};


思路三：桶排序；26个桶统计字符个数


思路四：哈希表计数；主串计数++；子串计数–；判断计数后是否有<0的。


下面记录思路二的代码


class Solution {
public:
  bool canConstruct(string ransomNote, string magazine) {
    if (magazine.size() < ransomNote.size())  return false;   //排除子串长度大于主串的情况
    unordered_map<char, int> map;
    for (auto i : magazine) {
      map[i]++;
    }
    for (auto i : ransomNote) {
      map[i]--;
    }
    for (auto p : map) {
      if (p.second < 0)  return false;
    }
    return true;
  }
};


49. 字母异位词分组【中等】



思路：哈希表


这题有点难度；前序后的作为模板，即作为键；排序前的作为能匹配到模板的值


class Solution {
public:
  vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> map;
    for (auto str : strs) {
      string key = str;
      sort(key.begin(), key.end());    //排序后的作为键     //这句代码可以换成其他的实现排序
      map[key].emplace_back(str);       //排序前的作为值
    }
    vector<vector<string>> res;
    for (auto p : map) {
      res.push_back(p.second);   //一下子插入一个vector<string>
    }
    return res;
  }
};


438. 找到字符串中所有字母异位词【中等】



思路一：用一个桶计数并滑动窗口


//滑动窗口：一边延伸，一边缩进
//用一个桶计数
class Solution {
public:
  bool equal(int* tong) {
    for (int i = 0; i < 26; i++) {
      if (tong[i] != 0) return false;
    }
    return true;
  }
  vector<int> findAnagrams(string s, string p) {
    if (p.size() > s.size())  return vector<int>();   //排除子串比主串长的情况
    vector<int> ans;  //用于存储索引
    int tong[26] = { 0 };
    for (int i = 0; i < p.size(); i++) {
      tong[p[i] - 'a']--;
      tong[s[i] - 'a']++;
    }
    for (int i = p.size(); i <= s.size(); i++) {
      if (equal(tong)) {
        ans.push_back(i - p.size());
      }
      if (i != s.size()) {    //防止索引越界
        tong[s[i] - 'a']++;               //实现滑动
        tong[s[i - p.size()] - 'a']--;
      }
    }
    return ans;
  }
};



//滑动窗口：一边延伸，一边缩进
//用一个桶计数
class Solution {
public:
  bool equal(int* tong) {
    for (int i = 0; i < 26; i++) {
      if (tong[i] != 0) return false;
    }
    return true;
  }
  vector<int> findAnagrams(string s, string p) {
    if (p.size() > s.size())  return vector<int>();   //排除子串比主串长的情况
    vector<int> ans;  //用于存储索引
    int tong[26] = { 0 };
    for (int i = 0; i < p.size(); i++) {
      tong[p[i] - 'a']--;
      tong[s[i] - 'a']++;
    }
    if (equal(tong)) ans.push_back(0);
    for (int i = 0; i < s.size() - p.size(); i++) {
      tong[s[i] - 'a']--;               //实现滑动
      tong[s[i + p.size()] - 'a']++;
      if (equal(tong))   ans.push_back(i + 1);
    }
    return ans;
  }
};


或者用两个容器，其实都一样，只是判断相等的语句换了


class Solution {
public:
  vector<int> findAnagrams(string s, string p) {
    if (s.size() < p.size())   return vector<int>();
    vector<int> ans;
    vector<int> sCount(26);
    vector<int> pCount(26);
    for (int i = 0; i < p.size(); ++i) {
      sCount[s[i] - 'a']++;
      pCount[p[i] - 'a']++;
    }
    if (sCount == pCount)   ans.emplace_back(0);
    for (int i = 0; i < s.size() - p.size(); i++) {    //需要滑动的次数
      sCount[s[i] - 'a']--;
      sCount[s[i + p.size()] - 'a']++;
      if (sCount == pCount)   ans.emplace_back(i + 1);
    }
    return ans;
  }
};


思路：滑动窗口哈希表


时间复杂度和空间复杂度都很高；这里不推荐此方法


class Solution {
public:
  bool equal(unordered_map<char, int> map) {
    for (auto p : map) {
      if (p.second != 0) return false;
    }
    return true;
  }
  vector<int> findAnagrams(string s, string p) {
    if (p.size() > s.size())  return vector<int>();
    unordered_map<char, int> map;
    for (int i = 0; i < p.size(); i++) {
      map[p[i]]--;
      map[s[i]]++;
    }
    vector<int> res;
    if (equal(map))  res.push_back(0);
    for (int i = p.size(); i < s.size(); i++) {
      map[s[i]]++;
      map[s[i - p.size()]]--;
      if (equal(map))  res.push_back(i - p.size() + 1);
    }
    return res;
  }
};


滑动窗口优化


都是在优化判断相等的方法：统计不为0的个数来判断相等


class Solution {
public:
  vector<int> findAnagrams(string s, string p) {
    int sLen = s.size(), pLen = p.size();
    if (sLen < pLen) {
      return vector<int>();
    }
    vector<int> ans;
    vector<int> count(26);
    for (int i = 0; i < pLen; ++i) {
      ++count[s[i] - 'a'];
      --count[p[i] - 'a'];
    }
    int differ = 0;
    for (int j = 0; j < 26; ++j) {
      if (count[j] != 0) {
        ++differ;
      }
    }
    if (differ == 0) {
      ans.emplace_back(0);
    }
    for (int i = 0; i < sLen - pLen; ++i) {
      if (count[s[i] - 'a'] == 1) {  // 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同
        --differ;
      }
      else if (count[s[i] - 'a'] == 0) {  // 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同
        ++differ;
      }
      --count[s[i] - 'a'];
      if (count[s[i + pLen] - 'a'] == -1) {  // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从不同变得相同
        --differ;
      }
      else if (count[s[i + pLen] - 'a'] == 0) {  // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从相同变得不同
        ++differ;
      }
      ++count[s[i + pLen] - 'a'];
      if (differ == 0) {
        ans.emplace_back(i + 1);
      }
    }
    return ans;
  }
};


3. 两个数组的交集


349. 两个数组的交集【简单】



思路一：枚举暴力破解；时间复杂度O(mn)


思路二：sort函数排序+双指针指向两个数组开始遍历；


时间复杂度O(nlogn+mlogm) ；


空间复杂度：O(logm+logn)； 主要取决于排序使用的额外空间


思路三：哈希表可以实现去重；


时间复杂度O(n+m)


空间复杂度O(n+m)


class Solution {
public:
  //哈希表存数 unordered_set无序，每种元素只能存储一个；   set是有序的
  vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    unordered_set<int> s1, s2;
    for (auto& i : nums1) s1.insert(i);   //存元素且去重，保证唯一
    for (auto& i : nums2) s2.insert(i);
    vector<int>v;
    for (auto& i : s2) {  //遍历s2中的每一个元素  在s1中进行查找
      if (s1.count(i))   v.push_back(i);
    }
    return v;
  }
};


或者以下：


空间复杂度O(m)


class Solution {
public:
  vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    unordered_set<int> set;
    for (auto i : nums1) {     //只存num1的
      set.insert(i);
    }
    vector<int> res;
    for (auto i : nums2) {   //遍历num2中的每一个元素，在set中进行查找  找到了要在哈希表中删除该元素 保证唯一
      if (set.count(i)) {       //查询的时间复杂度也为O(1)
        res.push_back(i);
        set.erase(i);        //删除的时间复杂度为O(1)
      }
    }
        return res;
  }
};


350. 两个数组的交集 II【简单】



思路一：排序+双指针指向两个数组；该方法比349的还要简单了


思路二：哈希表计数。因同种元素要计算次数了，由unordered_set改成unordered_map


class Solution {
public:
  vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
    unordered_map<int, int> map;   //第二个int为元素的次数
    for (auto i : nums1) {
      map[i]++;
    }
    vector<int> res;
    for (auto i : nums2) {
      if (map.count(i) && map[i] > 0) {   //找到了该元素  且个数>0才行
        res.push_back(i);
        map[i]--;                       //消消乐抵消一个
      }
    }
    return res;
  }
};


4. 快乐数


202. 快乐数【简单】



思路：我们可以认为之前出现过的数之后不会出现，即不成环，则总有一天走到1


如果成环，则不是快乐数


主要是看懂题目，看懂了题目就很简单。


class Solution {
public:
  int getSum(int n) {   //获取下一个个数
    int res = 0;
    while (n) {
      res += (n % 10) * (n % 10);
      n = n / 10;
    }
    return res;
  }
  bool isHappy(int n) {
    unordered_set<int> set;
    while (true) {
      int next_sum = getSum(n);  //1的下一个数也是1  所以这句代码可以写前面那
      if (next_sum == 1) return true;
      if (set.count(next_sum))  return false;           //成环
      else                      set.insert(next_sum);   //没成环
      n = next_sum;
    }
  }
};


5. 两数之和


1. 两数之和【简单】



思路一：双for循环暴力枚举


思路二：哈希表+遍历查询，因为返回索引，索引用unordered_map


思路二代码如下：


class Solution {
public:
  vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> map;
    for (int i = 0; i < nums.size(); i++) {
      if (map.count(target - nums[i]))  return { i, map[target - nums[i]] };
      map[nums[i]] = i;   //map插入元素  因为答案唯一，不需要担心插入两个相同的元素
    }
        return {-1,-1};    //这句代码走不到
    }
};


454. 四数相加 II【中等】



思路一：4for暴力枚举；不用多想，肯定超超时


思路二：4for拆开成两个两个，第一个双for存入哈希表，第二个双for查找哈希表


class Solution {
public:
  int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
    unordered_map<int, int> map;
    for (auto num1 : nums1) {
      for (auto num2 : nums2) {
        map[num1 + num2]++;
      }
    }
    int res;
    for (auto num3 : nums3) {
      for (auto num4 : nums4) {
        if (map.count(-num3 - num4)) {
          res += map[-num3 - num4];    //有几个这样的就加几
        }
      }
    }
    return res;
  }
};


15. 三数之和【中等，双指针】




思路：排序+双指针


哈希表时间复杂度和空间复杂度都很高


难度主要在于降重


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


空间复杂度：O(1)


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;
            // 正确去重方法
            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 这种三元组
                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]});
                    // 去重逻辑应该放在找到一个三元组之后
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;
                    // 找到答案时，双指针同时收缩
                    right--;
                    left++;
                }
            }
        }
        return result;
    }
};


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 (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }
            for (int i = k + 1; i < nums.size(); i++) {
                // 正确去重方法
                if (i > k + 1 && nums[i] == nums[i - 1]) {
                    continue;
                }
                int left = i + 1;
                int right = nums.size() - 1;
                while (right > left) {
                    if (nums[k] + nums[i] > target - (nums[left] + nums[right])) {
                        right--;
                    }
                    else if (nums[k] + nums[i] < target - (nums[left] + nums[right])) {
                        left++;
                    }
                    else {
                        result.push_back(vector<int>{nums[k], nums[i], 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;
    }
};



             else if (nums[k] + nums[i] < target - (nums[left] + nums[right])) {
                    left++;
                }
                else {
                    result.push_back(vector<int>{nums[k], nums[i], 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;
}


文章标签：
容器
机器学习/深度学习
索引
对象存储
zdb呀
目录
相关文章
技术小达人
|
算法
带你读《图解算法小抄》六、哈希表（2）
带你读《图解算法小抄》六、哈希表（2）
技术小达人
58 0
java冯坚持
|
1月前
|
算法 Java 数据库
数据结构与算法学习十五：哈希表
这篇文章详细介绍了哈希表的概念、应用实例、实现思路，并提供了使用Java实现的哈希表代码。
java冯坚持
53 0
数据结构与算法学习十五：哈希表
不摸鱼的程序员
|
6月前
|
存储 Java Serverless
从 0 到 1 读懂：哈希表
从 0 到 1 读懂：哈希表
不摸鱼的程序员
69 0
Bigcrab__
|
6月前
|
存储 算法 安全
数据结构与算法 哈希表
数据结构与算法 哈希表
Bigcrab__
30 0
jjn0703
代码随想录训练营 Day07 - 哈希表（下）
代码随想录训练营 Day07 - 哈希表（下）
jjn0703
54 0
Mylvzi
|
6月前
|
存储
leetcode刷题之哈希表的应用(1)
leetcode刷题之哈希表的应用(1)
Mylvzi
30 0
技术小达人
|
算法 索引
带你读《图解算法小抄》六、哈希表（1）
带你读《图解算法小抄》六、哈希表（1）
技术小达人
54 0
带你读《图解算法小抄》六、哈希表（1）
jjn0703
|
存储
代码随想录训练营 Day06 - 哈希表（上）
代码随想录训练营 Day06 - 哈希表（上）
jjn0703
55 0
枫叶先生_
|
存储 缓存 算法
【C++进阶】九、哈希表
目录 一、哈希概念 二、哈希冲突 三、哈希函数 四、哈希冲突解决 4.1 闭散列（开放定址法） 4.1.1 线性探测 4.1.2 二次探测 4.1.3 研究表明 五、哈希表的闭散列实现 5.1 闭散列哈希表的结构 5.2 闭散列的插入 5.2 闭散列的查找 5.3 闭散列的查找 5.4 哈希表取模问题 5.5 string类型无法取模问题 5.6 完整代码 四、哈希冲突解决 4.2 开散列（链地址法、哈希桶） 六、哈希表的开散列实现（哈希桶） 6.1 哈希桶的结构 6.2 哈希桶的插入 6.3 哈希桶的查找 6.4 哈希桶的删除 6.5 完整代码
枫叶先生_
114 0
【C++进阶】九、哈希表
水滴技术
|
存储 算法 Java
Java数据结构与算法分析（十一）散列表（哈希表）
散列表（Hash Table）也叫哈希表，是根据给定关键字（Key）来计算出该关键字在表中存储地址的数据结构。也就是说，散列表建立了关键字与存储地址之间的一种直接映射关系，将关键字映射到表中记录的地址，这加快了查找速度。
水滴技术
185 0