当前位置：首页 > article >正文

Leetcode 刷题记录 01 —— 哈希

article 2025/3/4 19:40:53

本系列为笔者的 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;
    }
};