力扣hot100--＞hash表/map

hash表/map

1. 1. 两数之和

简单

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

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

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

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只会存在一个有效答案

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // 创建一个哈希表（unordered_map），用于存储数组元素及其索引
        unordered_map<int, int> unmap;
        
        // 遍历数组中的每个元素
        for(int i = 0; i < nums.size(); ++i){
            // 查找是否存在一个元素，使得当前元素与之的和等于目标值
            auto ite = unmap.find(target - nums[i]);
            if(ite != unmap.end()){
                // 如果找到这样的元素，返回当前索引和找到的索引
                return {i, unmap[target - nums[i]]};
            }
            // 将当前元素及其索引插入到哈希表中
            unmap.insert(pair<int, int>(nums[i], i));
        }
        // 如果没有找到符合条件的元素，返回空数组
        return {};
    }
};
 

解释：

 unmap.find(target - nums[i]) 的返回类型是 unordered_map<int, int>::iterator。这个迭代器指向哈希表中与 target - nums[i] 相等的键值对，或者如果没有找到这样的键，则指向 unmap.end()。

使用 auto 可以让代码更简洁和易读。

2. 49. 字母异位词分组

中等

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

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

示例 1:

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

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

提示：

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

class Solution {
public:
    // 函数定义：输入字符串数组，返回分组的异位词
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ss; // 用于存储最终结果的二维向量
        unordered_map<string, vector<string>> m; // 哈希表，键为排序后的字符串，值为异位词的向量

        // 遍历输入的字符串数组
        for(string &s : strs){
            string t = s; // 复制当前字符串
            sort(t.begin(), t.end()); // 对字符串进行排序，以便找到异位词

            // 将原始字符串加入到对应排序后的键的向量中
            m[t].push_back(s);
        }

        // 遍历哈希表，将每个值向量添加到结果中
        for(auto it = m.begin(); it != m.end(); ++it){
            ss.push_back(it->second); // 将当前异位词组添加到结果向量中
        }

        return ss; // 返回分组后的异位词
    }
};

解释：

sort(s.begin(), s.end()); 这意味着所有异位词（如 "tea" 和 "ate"）在排序后都会转换为相同的字符串（"aet"）。

3. 128. 最长连续序列

中等

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

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

示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        sort(nums.begin(), nums.end(), less<>()); // 对数组进行排序
        
        int leng = 1; // 当前连续序列的长度
        int answer = nums.size() > 0 ? 1 : 0; // 如果数组不为空，初始化为 1；否则为 0

        for (int i = 1; i < nums.size(); i++) {
            // 跳过重复的元素
            while (i < nums.size() && nums[i] == nums[i - 1]) {
                i++;
            }

            // 检查当前元素是否与前一个元素连续
            if (i < nums.size() && nums[i] == nums[i - 1] + 1) {
                leng++; // 增加当前连续序列的长度
                answer = max(answer, leng); // 更新最长连续序列的长度
            } else {
                leng = 1; // 重置当前连续序列的长度
            }
        }
        return answer; // 返回最长连续序列的长度
    }
};

 解释：

跳过重复元素的主要目的是确保在计算连续序列的长度时，每个数字只被计数一次。否则，重复的元素会导致错误的序列长度计算。

比如：数组[1,0,1,2],正确输出为3。当经过排序后数组为[0,1,1,2],如果去掉跳过重复元素步骤，则会从最后一个重复元素重新开始计数就会得到错误的答案。

1. while 循环中的条件限制

代码示例：

while (i < nums.size() && nums[i] == nums[i - 1]) { i++; }

原因：

• 当数组中有多个重复元素时，i 会增加，可能会最终达到 nums.size()。如果不进行边界检查，访问 nums[i] 时会导致越界错误。

2. if 语句中的条件限制

代码示例：

if (i < nums.size() && nums[i] == nums[i - 1] + 1) { ... }

原因：

• 如果 while 循环已经将 i 增加到 nums.size()，那么访问 nums[i] 会导致越界。这个条件确保在进行连续性检查时，i 仍在有效范围内。