Leetcode刷题记录01——哈希

本系列为笔者的 Leetcode 刷题记录，顺序为 Hot 100 题官方顺序，根据标签命名，记录笔者总结的做题思路，附部分代码解释和疑问解答。

目录

01 两数之和

02 字母异位词分组

03 最长连续序列

注：词汇解释

---

01 两数之和

//基础框架 class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { } };

class这一关键字用来定义一个类，Solution是一个类的名字，public是一个访问修饰符（或访问标识符）。

类是C++中用于创建对象的蓝图或模板。类可以包含数据（成员变量）和函数（成员函数，或方法），这些函数用于操作或访问类的数据。

//方法一：暴力法 class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { int n = nums.size(); for(int i=0; i<n; i++){ for(int j=i+1; j<n; j++){ if(nums[i] + nums[j] == target){ return {i, j}; } } } return {}; } }; //方法二：哈希表法 class Solution { public: vector<int> twoSum(vector<int>& nums, int target){ unordered_map<int, int> hashTable; for(int i=0; i<nums.size(); ++i){ auto it = hashTable.find(target - nums[i]); if(it != hashTable.end()){ return {it->second, i}; } //两数之和 //进行到第二个数的时候能够查到第一个数，因此输出 hashTable[num[i]] = i; //键是数组中的数，值是位置 } return {}; } }

unordered_map是一个容器类，提供键值对的存储，并允许通过键快速查找对应的值。它是标准库的一部分，位于<unordered_map>头文件中。

02 字母异位词分组

class Solution { public: vector<vector<string>> groupAnagrams(vector<string>& strs) { } }; //方法一：排序 class Solution { public: vector<vector<string>> groupAnagrams(vector<string>& strs) { //单个字符串（键）映射到多个字符串集合（值） unordered_map<string, vector<string>> mp; for(string& str:strs){ string key = str; sort(key.begin(), key.end()); mp[key].emplace_back(str); } //将字母异位词映射集合 mp 中的值提取出来 vector<vector<string>> ans; for(auto it = mp.begin(); it != mp.end(); ++it){ ans.emplace_back(it -> second); } return ans; } };

string& str 指的是对集合中每个元素的引用，通过这种引用，你可以直接操作原集合中的元素，而不需要复制它们。

//方法二：计数 class Solution{ public: vector<vector<string>> groupAnagrams(vector<string>& strs){ //自建哈希 auto arrayHash = [fn = hash<int>{}](const array<int, 26>& arr) -> size_t{ return accumulate(arr.begin(), arr.end(), 0u, [&](size_t acc, int num){ return (acc << 1) ^ fn(num); }); }; //单个固定数组（键）映射到多个字符串集合（值） unordered_map<array<int, 26>, vector<string>, decltype(arrayHash)> mp(0, arrayHash); for(string& str: strs){ array<int, 26> counts{}; int length = str.length(); for(int i=0; i<length; ++i){ counts[str[i] - 'a']++; } mp[counts].emplace_back(str); } //将字母异位词映射集合 mp 中的值提取出来 vector<vector<string>> ans; for(auto it = mp.begin(); it != mp.end(); ++it){ ans.emplace_back(it -> second); } return ans; } };

① lambda 表达式是一种内联的、匿名的函数。

[capture](parameters) -> return_type { body }

[capture]：捕获列表，定义了lambda表达式中可以访问的外部变量。可以是以值捕获（=）、引用捕获（&）、特定变量捕获（如 [x, &y]，分别以值和引用捕获）等形式。

(parameters)：参数列表，类似于普通函数的参数列表。

-> return_type：返回类型说明符。

② std::for_each 是 C++ 标准库中的一个算法，定义在 <algorithm> 头文件中。它用于对指定范围内的每个元素应用一个函数（通常是一个函数对象或 lambda 表达式）。

std::for_each(first, last, func);

③ std::hash 是专门为一些基本类型（如整数、指针、字符串等）和自定义类型提供默认的哈希功能。对于 int 类型，std::hash<int> 提供了一种用于生成该整数的哈希值的标准方式。

④ std::array 是一种容器类模板，用于表示具有固定大小的数组。与传统的 C 风格数组（如 int arr[26];）相比，它提供了更高的安全性和功能性。<int, 26> 是模板参数，int 指定了数组中元素的类型，26 是数组的大小。

⑤ std::accumulate 是 C++ 标准库中的一个函数，用于对一个范围内的元素进行累积求和或其他操作，定义在 <numeric> 头文件中。

std::accumulate(numbers.begin(), numbers.end(), 0, ...);

numbers.begin() 和 numbers.end() 定义了我们要累加的范围，0 是我们累加操作的初始值。

[](int acc, int num) { return acc + num; }

acc初始化为0（或我们给定的另一个初始值），并用于在每一步向量中的加法操作，num为从输入容器（如数组或向量）中获取值（例如，1、2、3 等）。

//规范定义 #include <numeric> template<class InputIt, class T> T accumulate(InputIt first, InputIt last, T init); template<class InputIt, class T, class BinaryOperation> T accumulate(InputIt first, InputIt last, T init, BinaryOperation op);

InputIt first, InputIt last: 指定要处理的范围（通常是一个容器的开始和结束迭代器）。

T init: 初始化值，这个值是累积操作开始时的初始值。

BinaryOperation op: 一个二元操作函数，用于自定义累积操作。它接收两个参数：累积值和当前元素，并返回新的累积值。若未提供该操作，则默认使用加法操作。

⑥ (acc << 1) 左移操作符将累加器 acc 向左移动一位，相当于乘以2。

⑦ ^ fn(num) 应用 XOR 运算符将 fn(num)（即 num 的哈希值）和左移后的 acc 进行异或操作。

注意：在参数传递方面，使用 & 主要目的是避免不必要的拷贝，节省内存空间，并允许被调用的函数修改实际参数。然而，如果不希望函数改变参数的值，通常会结合 const 关键字来保护数据的完整性。

总体而言，这个 arrayHash lambda 表达式的目标是在一个固定大小的整数数组上生成一个哈希值，以便能够有效地建立自定义的哈希表或者其他基于哈希的结构。

03 最长连续序列

class Solution { public: int longestConsecutive(vector<int>& nums) { //去重 unordered_set<int> num_set; for(const int& num: nums){ num_set.insert(num); } int longestStreak = 0; for(const int& num: num_set){ //找寻连续序列起点 if(!num_set.count(num-1)){ int currentNum = num; int currentStreak = 1; while(num_set.count(currentNum + 1)){ currentNum += 1; currentStreak++; } } longestStreak = max(currentStreak, longestStreak); } return longestStreak; } }; 注：词汇解释

numeric / nuːˈmerɪk / 数，数字

template / ˈtemplət / 模板

custom 风俗，习惯

anagram / ˈænəɡræm / 同母异位词

作者：力扣官方题解 链接： leetcode /problems/two-sum/solutions/434597/liang-shu-zhi-he-by-leetcode-solution/ 来源：力扣（LeetCode）