Leetcode-Hot100-Hash

Leetcode Hot100: 哈希算法部分解题记录。

代码：Python

后续会慢慢补充C++和Java版本

1. 两数之和

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

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

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

解题思路：

• 哈希存储 target-n : idx
• 每次迭代的值为n
• 若n的pair不在哈希表中，则将n和id存储到哈希表，一遍后续n的pair出现时可以找到n与其id

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hash_s = {}
        for idx, n in enumerate(nums):
            if target - n in hash_s.keys():
                return [idx, hash_s[target-n]]
            else:
                hash_s[n] = idx
        return []

49.字母异位词分组

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

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

解题思路
把单词字母排序，作为哈希表的key，这个单词本身作为哈希表的value。value是list类型，每次append到list最后

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        mp = collections.defaultdict(list)
        for s in strs:
            key = "".join(sorted(s))
            mp[key].append(s)
        return list(mp.values())

• collections.defaultdict(list): 什么都没有的时候默认有一个空list
• sorted(s)：对s排序，s可以是任何可迭代对象注意：sorted() 会返回一个列表，而不是字符串。
• “”.join(sorted(s))：转为字符串

class Solution {

public:

    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> mp;
        for(string& s: strs)
        {
            string k = s;
            sort(k.begin(), k.end());
            mp[k].emplace_back(s);
        }
        vector<vector<string>> result;
        for(auto it = mp.begin(); it != mp.end(); it++)
        {
            result.emplace_back(it->second);
        }
        return result;
    }
};

• unordered_map<string, vector<string>>:哈希表，存储key-value键值对，key 为字符串，value 为字符串向量（vector<string>）。
• mp.begin() 遍历 unordered_map，it->first 是键（排序后的字符串），it->second 是对应的 vector<string>（异位词列表）。

emplace_back() 和 push_back() 主要区别在于对象的构造方式。
主要区别

方法	作用	主要区别
push_back(const T& value)	拷贝（或移动）对象到 vector 末尾	需要先构造对象，再拷贝或移动到 vector
emplace_back(args...)	直接在 vector 末尾构造对象	避免额外的拷贝或移动，效率更高

128. 最长连续序列

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

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

解题思路

• 时间复杂度 O(n) ，说明不能用排序算法。
• nums中数字可能重复出现，所以需要用set方法去重
• 每次迭代判断当前n-1是否存在于set中
  • 若存在，则以n为头，寻找该序列的长度。

下面是官方的C++代码

class Solution {

public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> nums_set;
        for(const int& n: nums){
            nums_set.insert(n);
        }

        int result = 0;

        for(const int& n: nums_set){
            if(!nums_set.count(n-1)){
            // 对每个元素检查他的-1是否存在于set中
            // 若不存在，则这是一个新的序列起点
                int currNum = n;
                int currLen = 1;
                while(nums_set.count(currNum + 1)){
                //是起点，就找以他为头的序列
                    currNum ++;
                    currLen ++;
                }
                result = max(result,currLen);
            }
        }
        return result;

    }
};