1.两数之和

题目链接：两数之和

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

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

解题思路：

我们创建一个哈希表，以数组的值做key，索引做value。对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

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

• 时间复杂度：O(n)
• 空间复杂度：O(n)

49.字母异位词分组

题目链接：字母异位词分组

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

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

解题思路：

由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。

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

128.最长连续序列

题目链接：最长连续序列

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

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

解题思路：

我们可以将数组放在数轴上看，我们在遍历数组时，首先找到连续段的起点，再向后记录连续段的长度，这里我们要快速判断nums[i]-1 或者nums[i]+1 是否在数组中。

“当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。”

我们这里首先将nums数组放进set集合中，再遍历nums，如果nums[i]-1在set中，则nums[i]一定不是连续段的起点，否则判断nums[i]+1 在不在set中，记录连续段的长度。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> set;
        for (auto num : nums) {
            set.insert(num);
        }
        int result = 0;
        for (auto num : nums) {
            if (set.count(num - 1) == 0) {
                int len = 1;
                while (set.count(num + 1)) {
                    num++;
                    len++;
                }
                result = max(len, result);
            }
        }
        return result;
    }
};