LCHot100-01：哈希

两数之和

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

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

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

暴力肯定是不行的，太慢了，双重循环每经过一个数需要将后面的数全部遍历一遍，复杂度为 $O(N^2)$ 。哈希表查找是 $O(1)$ ，尝试利用：对每一个数组中的数，先算达成 target 所需要的补数，用哈希看它在不在集合中，在的话用补数当键找出它的 index，不在的话以自己为键在哈希表中存进自己的 index。最终的时间复杂度是 $O(1)$ 。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashmap;
        int vec_size = num.size();
        for (int i = 0; i < vec_size; ++i) {
            int complement = target - nums[i];
            if (hashmap.find(complement) != hashmap.end()) {
                return {hashmap[complement], i};
            }
            hashmap[nums[i]] = i;
        }
        return {};
    }
};

字母异位词分组

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

评论区：人话都不会说。“把字母数量相同的字符串分到一组”很难吗？示例：[“nat”,“tan”]都是一个 a，一个 n，一个 t，所以分到一组。[“ate”,“eat”,“tea”]都是一个 a，一个 e，一个 t，所以分到一组。

很适合用 unorderd_map：字幕异位词在哈希表中共享一个键，这个键使用字符串按字典序排序产生的字符串即可。函数返回值是 vector<vector<string>> ，哈希表中是 string-vector<string> 的键值对，全部装进哈希表后按键值 pair 将 vector<string> 逐组推进 vector 即可。

对每一个字符串排序的时间复杂度是 $O(klogk)$ ， $k$ 即单词最大长度，全部排序即 $O(nklogk)$ 。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> hashmap;
        for (string& s : strs) {
            string key = s;
            sort(key.begin(), key.end());
            hashmap[key].push_back(s);
        }
        vector<vector<string>> result;
        for (auto& pair : hashmap) {
            result.push_back(pair.second);
        }
        return result;
    }
};

最长连续序列

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

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

对每一个数字，向后搜索只需要判断下一个数在不在数组里，在的话就对长度累加。在一个连续的区间内，应当尽可能减少重复访问的次数。unordered_set 判断元素是否在集合内的时间复杂度为 $O(1)$ ，将数组装进无序集合，那么对集合中的每一个数字 num，当且仅当这个数字是连续序列的开头（即 num-1 不在集合中时），从这个数字开始递增序列长度；当一个元素有前缀的连续序列，则跳过。这样就可以避免一个连续序列里多次访问同一个元素。

集合由若干个连续子序列组成，对每一个子序列中的元素都没有重复访问，最终对集合中的每一个数只访问一次，时间复杂度为 $O(1)$ 。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> numSet(nums.begin(), nums.end());
        int maxLen = 0;
        for (int num : numSet) {
            if (!numSet.count(num - 1)) {
                int currentNum = num;
                int currentLen = 1;
                while (numSet.count(currentNum + 1)) {
                    currentNum++;
                    currentLen++;
                }
                maxLen = max(maxLen, currentLen);
            }
        }
        return maxLen;
    }
};