两数之和

知识点

unordered_map有find操作，传入待查询的key值
- 如果有对应key值，则返回位于该位置的迭代器；
- 如果没有对应key值，则返回unordered_map::end()迭代器

解题思路

首先初始化一个unordered_map，nums中的元素作为key，每个元素的下标作为value
遍历nums数组中的每一个元素num
- 如果unorder_map找到target - num，则返回对应的下标和num对应下标i
- 如果没有找到，则将当前元素在unordered_map中对应的value设置为i
以上的算法步骤保证了，如果遍历较小的元素没有找到符合要求的组合，那么在遍历组合中较大的元素时，就可以找到较小的元素，进而返回组合

实现代码

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 {};
    }
};

字母异位词分组

知识点

emplace_back成员函数
- 在vector或者unorderd_map尾部添加一个新的元素
- 与push_back相比，emplace_back直接在容器内部的内存空间构造对象，避免了临时空间的复制与删除。提高了性能
对于unordered_map，使用迭代器it遍历访问unordered_map中的每一个元素
- it->self表示这个元素的key
- it->second表示这个元素的value

解题思路

使用排序后的字符串的作为哈希表的key
- 异位词中的字母（样式和数量）都是相同的，所以排序后的字符串也必然是相同的
哈希表的value为vector<string>用来存储同一组异位词
最后将每组异位词存入ans

实现代码

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);
        }
        vector<vector<string>> ans;
        for(auto it = mp.begin(); it != mp.end(); it ++){
            ans.emplace_back(it->second);
        }

        return ans;
    }
};

最长连续序列

知识点

unordered_set中的元素都是唯一的，没有重复的
解题思路
题中要求我们在$\Omega(n)$的时间复杂度中完成搜索
我们考虑使用unordered_set进行存储，这样可以排除重复元素的干扰，因为重复元素不能算作连续序列
如果使用暴力搜索，对于一个元素x，我们要遍历整个数组来搜索x + 1, x + 2, x + 3, ... , x + y ，这样的算法时间复杂度为$\Omega(n^2)$，显然不符合要求
为了优化算法时间复杂度，在搜索时，对于元素x，我们首先判断x - 1 是否在unordered_set中
- 如果在，则跳过当前对当前x的遍历，因为从x - 1开始的连续序列一定要长于从x开始的连续序列，没有继续搜索的必要
- 如果不在，则执行循环，寻找下一个x + 1, x + 2, ..., x + y是否在序列中
ans = max(ans, y - x)
- 因为int y = x + 1和在循环中执行了y ++，所以直接y - x就是最长序列的长度

实现代码

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int ans = 0;
        unordered_set<int> st(nums.begin(), nums.end());
        for(int x : st){
            if(st.contains(x - 1)){
                continue;
            }

            int y = x + 1;
            while(st.contains(y))
                y ++;
            ans = max(ans, y - x);
        }

        return ans;
    }
};

hot100系列——哈希

两数之和

知识点

解题思路

实现代码

字母异位词分组

知识点

解题思路

实现代码

最长连续序列

知识点

解题思路

实现代码

Enjoy Reading This Article?