【算法题】哈希-平芜编程栈

哈希表（哈希映射/哈希集合）是算法中解决“查找、统计、匹配”类问题的核心工具，核心优势是平均O(1)时间复杂度的增删查操作。它通过“键值对”的映射关系，将原本需要线性遍历的查找操作优化为常数级，广泛应用于两数之和、字符统计、重复元素判断、异位词分组等场景。本文通过5道经典题目，拆解哈希表在不同场景下的解题思路与代码实现。

一、两数之和

题目描述：
给定整数数组nums和目标值target，找出数组中两个数的索引，使它们的和等于target（假设每种输入只有一个答案，且不能使用同一个元素两次）。

示例：

输入：nums = [2,7,11,15], target = 9，输出：[0,1]

解题思路：
用哈希表存储“数值→索引”的映射，遍历数组时反向查找：

遍历数组，对当前元素nums[i]，计算需要匹配的数值x = target - nums[i]。
若x存在于哈希表中，说明已遍历过该数值，直接返回[hash[x], i]。
若不存在，将当前数值和索引存入哈希表，继续遍历。

完整代码：

classSolution{public:vector<int>twoSum(vector<int>&nums,inttarget){unordered_map<int,int>hash;for(inti=0;i<nums.size();i++){intx=target-nums[i];if(hash.count(x))return{hash[x],i};hash[nums[i]]=i;}return{-1,-1};}};

复杂度分析：

时间复杂度：O(n)O(n)O(n)，遍历数组一次，哈希表的查/存操作均为O(1)O(1)O(1)。
空间复杂度：O(n)O(n)O(n)，哈希表最多存储n-1个元素。

二、判定是否互为字符重排

题目描述：
给定两个字符串s1和s2，判断是否为彼此的字符重排（字符种类和数量完全相同，仅顺序不同）。

示例：

输入：s1 = "abc", s2 = "bca"，输出：true
输入：s1 = "abc", s2 = "abd"，输出：false

解题思路：
用固定长度的数组模拟哈希表（字符集仅小写字母），统计字符频次：

若两字符串长度不同，直接返回false。
遍历s1，统计每个字符的出现次数。
遍历s2，减少对应字符的频次，若出现频次为负（字符数量不匹配），返回false。

完整代码：

classSolution{public:boolCheckPermutation(string s1,string s2){if(s1.size()!=s2.size())returnfalse;inthash[26]={0};for(autoc:s1)hash[c-'a']++;for(autoc:s2)if(--hash[c-'a']<0)returnfalse;returntrue;}};

复杂度分析：

时间复杂度：O(n)O(n)O(n)，n为字符串长度，遍历两次字符串。
空间复杂度：O(1)O(1)O(1)，数组长度固定为26（仅存储小写字母频次）。

三、存在重复元素

题目描述：
给定整数数组nums，判断是否存在重复元素（任意一个元素出现至少两次）。

示例：

输入：nums = [1,2,3,1]，输出：true
输入：nums = [1,2,3,4]，输出：false

解题思路：
用哈希集合存储已遍历的元素，遍历过程中实时查重：

遍历数组，若当前元素已在哈希集合中，说明存在重复，返回true。
若不存在，将元素插入集合，继续遍历。
遍历结束后未找到重复元素，返回false。

完整代码：

classSolution{public:boolcontainsDuplicate(vector<int>&nums){unordered_set<int>hash;for(auton:nums){if(hash.count(n))returntrue;elsehash.insert(n);}returnfalse;}};

复杂度分析：

时间复杂度：O(n)O(n)O(n)，遍历数组一次，集合的查/插操作均为O(1)O(1)O(1)。
空间复杂度：O(n)O(n)O(n)，集合最多存储n个元素。

四、存在重复元素 II

题目描述：
给定整数数组nums和整数k，判断是否存在两个不同的索引i和j，使得nums[i] = nums[j]且abs(i - j) ≤ k。

示例：

输入：nums = [1,2,3,1], k = 3，输出：true
输入：nums = [1,2,3,1,2,3], k = 2，输出：false

解题思路：
用哈希表存储“数值→最新索引”的映射，遍历过程中检查索引差：

遍历数组，若当前数值已存在于哈希表中，计算索引差abs(i - hash[nums[i]])。
若索引差 ≤k，返回true；否则更新哈希表中该数值的索引为当前索引。
若数值不存在，直接存入哈希表。

完整代码：

classSolution{public:boolcontainsNearbyDuplicate(vector<int>&nums,intk){unordered_map<int,int>hash;for(inti=0;i<nums.size();i++){if(hash.count(nums[i]))if(abs(i-hash[nums[i]])<=k)returntrue;hash[nums[i]]=i;}returnfalse;}};

复杂度分析：

时间复杂度：O(n)O(n)O(n)，遍历数组一次，哈希表操作均为O(1)O(1)O(1)。
空间复杂度：O(n)O(n)O(n)，哈希表最多存储n个元素。

五、字母异位词分组

题目描述：
给定字符串数组strs，将字母异位词组合在一起（字母异位词指字母相同但排列不同的字符串）。

示例：

输入：strs = ["eat","tea","tan","ate","nat","bat"]，输出：[["eat","tea","ate"],["tan","nat"],["bat"]]

解题思路：
将“排序后的字符串”作为哈希表的键，分组存储异位词：

遍历每个字符串，将其排序后得到“基准键”（异位词排序后结果相同）。
将原字符串存入哈希表中对应键的列表里。
遍历哈希表，收集所有列表作为结果。

完整代码：

classSolution{public:vector<vector<string>>groupAnagrams(vector<string>&strs){unordered_map<string,vector<string>>hash;for(auto&s:strs){string tmp=s;sort(tmp.begin(),tmp.end());hash[tmp].push_back(s);}vector<vector<string>>ret;for(auto&[x,y]:hash){ret.push_back(y);}returnret;}};