leetcode-hot-100（哈希）

写在前面

这部分官方标记为哈希，下面的代码使用的都是 C++ 进行实现，说到 C++ 中的哈希，需要了解一下 C++ 中的 hashtable（std::unordered_map或std::unordered_set）。

std::unordered_map

std::unordered_map 是一个存储键值对的容器，它允许通过键快速访问元素。这里的“快速”是指平均情况下常数时间复杂度O(1)的操作，因为它是基于哈希表实现的。

std::unordered_set

std::unordered_set与std::unordered_map类似，但它只存储键而不存储对应的值，适用于需要唯一键的场景。

1. 两数之和

题目链接：两数之和
题目描述：
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

解答：

第一种，暴力破解：

对于这种题目，第一的想法就是上双重循环，然后进行判断，也就是上双重循环，然后设置两个指针，进行查找，对应的代码如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int len = nums.size();
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                if (nums[i] + nums[j] == target)
                    return {i, j};
            }
        }
        return {}; // 没找到时返回空数组
    }
};

显然，要是学过数据结构的知道，这样的话，时间复杂度就比较的高。
复杂度分析

• 时间复杂度：$O(N^2)$，其中 $N$ 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。
• 空间复杂度：$O(1)$。

第二种，排序后求解

第一种的结果虽然可行，但是其时间复杂度比较高，因此我们还需优化，于是我们不得不考虑其他的方式了，学过排序的我们又想到一种方式，能不能使用高效的排序将 vector& nums 中的数据进行排序后再操作啊？，好，于是基于上述思想，编写代码如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end()); // 排序
        int left = 0;
        int right = nums.size() - 1;
        while (left < right) {
            if (nums[left] + nums[right] == target)
                return {left, right};
            else if (nums[left] + nums[right] < target)
                left++;
            else
                right--;
        }
        return {};
    }
};

嗯，逻辑非常清晰，但是结果提交，发现，错了！！？
为啥，我们看题目，发现需要返回的是原数组的原始下标，但是结果你上述将数组中数据的位置给改变了，虽然相加确实等于目标值，但是在原数组中的位置就被改变了。

要是我们还是想使用这个排序，又该当如何呢？
答：可以先将每个元素及其原始索引保存为一个 pair，然后排序这些 pair，再用双指针找答案
如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<pair<int, int>> pairs; // {value, index}
        for (int i = 0; i < nums.size(); ++i) {
            pairs.push_back({nums[i], i});
        }

        // 按照数值排序 pairs，原始的 nums 不能动
        sort(pairs.begin(), pairs.end());

        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int sum = pairs[left].first + pairs[right].first;
            if (sum == target) {
                return {pairs[left].second, pairs[right].second};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }

        return {};
    }
};

上述代码就可以了。下面大致看看复杂度：

• 时间复杂度: $O(nlogn)$: 整体的时间复杂度主要由排序步骤决定
• 空间复杂度: $O(n)$ : 需要额外的 $O(n)$ 空间来存储 $pairs$ 向量

第三种，哈希

OK，要是你的要求比较高，觉得上述 $O(nlogn)$ 时间复杂度还是高了，那有没有更低的时间复杂度？有的，兄弟，下面就是最主要的解题方式了。
可以利用一个 哈希表（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) {
            int complement = target - nums[i];
            if (map.count(complement)) {
                return {map[complement], i};
            }
            map[nums[i]] = i;
        }
        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[nums[i]] = i;
        }
        return {};
    }
};

比较一下上述编写的三种方式及适用场景：

2. 字母异位词分组

题目链接：字母异位词分组
题目描述：
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

解答：

看到这题，我首先想到的思路就是将每个字符串中的字符按照从 $a$ 到 $z$ 的先后顺序进行排列。（当然这个排列也是不能再原来的数据结构上进行操作的，需要复制原来的数据结构，然后在复制好的基础上进行操作。），然后要是排列后字符串相同的就放在一起。
但是，思想有了，不知道如何编码，哎。
别急，要是我们实在是不会，可以看看官方的题解，只要将官方的题解吃透，也就是相当于算法是我们想出来的。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        // 创建一个哈希表（unordered_map），键是排序后的字符串，值是一个字符串向量，
        // 用于存储所有字母相同但顺序不同的字符串（即异位词）。
        unordered_map<string, vector<string>> mp;

        // 遍历输入的字符串数组
        for (string& str : strs) {
            // 复制当前字符串，避免对原有的数据结构进行操作
            string key = str;

            // 对复制的字符串进行排序，这样所有的异位词在排序后都会变成相同的字符串。
            sort(key.begin(), key.end());

            // 将原始字符串添加到哈希表中对应的排序字符串的列表里。
            // 这样，所有排序结果相同的字符串将被分组在一起。
            mp[key].emplace_back(str);
        }

        // 创建一个二维字符串向量，用于存储最终的结果。
        vector<vector<string>> ans;

        // 遍历哈希表中的所有元素
        for (auto it = mp.begin(); it != mp.end(); ++it) {
            // 将每组异位词（即哈希表中每个键对应的值）添加到结果向量中。
            // emplace_back 直接构造并插入，避免不必要的拷贝或移动操作。
            ans.emplace_back(it->second);
        }

        // 返回最终的分组结果
        return ans;
    }
};

官方还给出来计数这一解题方法：

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        // 自定义对 array<int, 26> 类型的哈希函数
        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);
        }
        vector<vector<string>> ans;
        for (auto it = mp.begin(); it != mp.end(); ++it) {
            ans.emplace_back(it->second);
        }
        return ans;
    }
};

根据其思想写的代码如下:
下面的代码原理就是构造类似于
“aab” -> a2b1
“abc” -> a1b1c1

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> map;

        for (string& str : strs) {
            int counts[26] = {0};
            for (char c : str) {
                counts[c - 'a']++;
            }

            // 构造 key：包含字符和其数量
            string key;
            for (int i = 0; i < 26; ++i) {
                if (counts[i] > 0) {
                    key += ('a' + i);
                    key += to_string(counts[i]);
                }
            }

            map[key].push_back(str);
        }

        vector<vector<string>> ans;
        for (auto& p : map) {
            ans.push_back(p.second);
        }

        return ans;
    }
};

因为要是只是简单的编写如下这样的代码：

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> map;
        for (string str : strs)
        {
            int counts[26] = {0};
            for (char c : str)
            {
                counts[c - 'a']++;
            }
            string key = "";
            for (int i = 0; i < 26; i++)
            {
                if (counts[i] != 0)
                {
                key.push_back(i + 'a');
                }
            }
        
        map[key].push_back(str);
        }
        vector < vector<string>> ans;
        for (auto &p : map)
        {
            ans.push_back(p.second);
        }
        return ans;
    }
};  

错误发生的位置：构造 key 的方式不对，如下

int counts[26] = {0};
for (char c : str) {
    counts[c - 'a']++;
}
string key = "";
for (int i = 0; i < 26; i++) {
    if (counts[i] != 0) {
        key.push_back(i + 'a');
    }
}

//"aba" 和 "baa" 都会变成 "ab"
//"aab" 也会变成 "ab"
//这会导致不同的异位词被错误地归为一组！

因此，还是第一种直接使用字符排序法更加的方便与简洁。

3. 最长连续序列

题目链接：字母异位词分组
题目描述：给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

解答

这道题目好像是放在哈希里面的，但是我一开始想到的解决当时居然不是哈希，而是通过动态规划进行求解。具体的思路就是将原来的数组进行排序，然后在依次比较对应位置的值，当然，注意边界处理即可。具体代码如下：

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.size() <= 1)
            return nums.size();
        sort(nums.begin(), nums.end());
        int maxLen = 1;
        int currLen = 1;
        for (int i = 0; i < nums.size() - 1; ++i) {
            if (nums[i] == nums[i + 1] - 1) {
                currLen++;
                maxLen = max(maxLen, currLen);
            } else if (nums[i] != nums[i + 1]) { // 跳过重复数字
                currLen = 1;
            }
            // 如果是重复数字（nums[i] == nums[i+1]），不做任何操作，继续循环
        }
        return maxLen;
    }
};

但是呢，要是实在是想使用哈希的话，我试一下看看，

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        // 将输入数组中的所有元素存入一个哈希集合中
        // unordered_set 支持 O(1) 时间复杂度的查找操作
        unordered_set<int> numSet(nums.begin(), nums.end());

        // 用于记录当前找到的最长连续序列的长度
        int longest = 0;

        // 遍历集合中的每一个数字
        for (int num : numSet) {
            // 判断当前数字是否是某个连续序列的起点
            // 如果 num - 1 不在集合中，则说明 num 是一个连续序列的起点
            if (numSet.find(num - 1) == numSet.end()) {
                int currentNum = num;     // 当前连续序列的起始数字
                int length = 1;           // 当前连续序列的长度，初始为 1

                // 向后查找连续递增的整数
                // 只要 currentNum + 1 存在于集合中，就继续扩展序列
                while (numSet.find(currentNum + 1) != numSet.end()) {
                    currentNum++;         // 移动到下一个连续整数
                    length++;             // 序列长度加一
                }

                // 比较并更新全局最长连续序列长度
                longest = max(longest, length);
            }
        }

        // 返回最终找到的最长连续序列的长度
        return longest;
    }
};

说实话，差不多，还是需要动态规划。

关于哈希的好像就这三道题。