早上好，我的leetcode 【hash】（第二期）

写在前面：坚持才是最难的事情

C++代码还是不方便写，改用python了，TAT

---

1.两数之和

你好，梦开始的地方~

https://leetcode.cn/problems/two-sum/description/?envType=study-plan-v2&envId=top-100-liked

直接两个for循环

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {

        int size = nums.size();
        for (int i = 0; i < size; i++ ){
            for (int j = i + 1; j < size; j++){
                if (nums[i] + nums[j] == target){
                    return {i ,j};
                }
            }
        }
        return {};
    }
};

时间复杂度：O（$N^2$），其中N是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次
空间复杂度：O (1)。

最容易想到的方法是枚举数组中的每一个数 x，寻找数组中是否存在 target - x。方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。

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

    }
};

49. 字母异位词分组

https://leetcode.cn/problems/group-anagrams/description/?envType=study-plan-v2&envId=top-100-liked

思路：将字符串排序，字符串排序后相同的放在一起

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

class Solution {
private:
    unordered_map<string, vector<string>> hash;
    vector<vector<string>> ans;
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        for (const auto& str : strs){
            string tmp = str;
            sort(tmp.begin(), tmp.end());
            hash[tmp].emplace_back(str);
        }
        for (const auto& one: hash){
            ans.emplace_back(one.second);
        }
        return ans;
    }
};

时间复杂度$:O(nk\log k)$,其中 $n$ 是 $strs$ 中的字符串的数量，$k$ 是 $strs$ 中的字符串的的最大长度。需要遍历 $n$ 个字符串，对于每个字符串，需要 $O(k\log k)$ 的时间进行排序以及 $O(1)$ 的时间更新哈希表，因此总时间复杂度是 $O(nk\log k)$ 。

空间复杂度： $O(nk)$,其中 $n$ 是 $strs$ 中的字符串的数量，$k$ 是 $strs$ 中的字符串的的最大长
度。需要用哈希表存储全部字符串。

---

方法二：计数
由于互为字母异位词的两个字符串包含的字母相同，因此两个字符串中的相同字母出现的次数一定是相同的，故可以将每个字母出现的次数使用字符串表示，作为哈希表的键。

由于字符串只包含小写字母，因此对于每个字符串，可以使用长度为 26 的数组记录每个字母出现的次数。、

还是python写比较方便，C++太不熟悉了TAT

class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        mp = collections.defaultdict(list);

        for st in strs:
        	# 记录字母出现的次数
            counts = [0] * 26
            for ch in st:
            	# 字母出现记录+1
            	# ord() 函数返回一个字符的Unicode码点，因此 ord(ch) 返回字符 ch 的Unicode码点
                counts[ord(ch) - ord("a")] += 1
            
            # 两个字符串中的相同字母出现的次数一定是相同的，放在一起
            mp[tuple(counts)].append(st)
        
        return list(mp.values())

时间复杂度$:O(n(k+|\Sigma |))$,其中 $n$ 是 $strs$ 中的字符串的数量，$k$ 是 $strs$ 中的字符串的的最大长度，Σ 是字符集，在本题中字符集为所有小写字母，$|\Sigma |=26$。需要遍历 $n$ 个字符串，对于每个字符串，需要 $O(k)$ 的时间计算每个字母出现的次数，$O(|\Sigma |)$ 的时间生成哈希表的键， 以及 $O(1)$ 的时间更新哈希表，
因此总时间复杂度是 $O(n(k+|\Sigma |))$ 。

空间复杂度： $O(n(k+|\Sigma |))$,其中 $n$ 是 $strs$ 中的字符串的数量，$k$ 是 $strs$ 中的字符串的最大
长度，Σ 是字符集，在本题中字符集为所有小写字母，$|\Sigma |=26$。需要用哈希表存储全部字符串，而记录每个字符串中每个字母出现次数的数组需要的空间为 $O(|\Sigma |)$, 在渐进意义下小于$O(n(k+|\Sigma |))$,忽略不计。

128.最长连续序列

https://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-100-liked

我们考虑枚举数组中的每个数$x$,考虑以其为起点，不断尝试匹配$x+1,x+2,?$是否存在，假设最长匹配到了 $x+y$,那么以 $x$ 为起点的最长连续序列即为 $x,x+1,x+2,?,x+y$, 其长度为
$y+1$, 我们不断枚举并更新答案即可。

对于匹配的过程，暴力的方法是 $O(n)$ 遍历数组去看是否存在这个数，但其实更高效的方法是用一
个哈希表存储数组中的数，这样查看一个数是否存在即能优化至 $O(1)$ 的时间复杂度。

仅仅是这样我们的算法时间复杂度最坏情况下还是会达到 $O(n^2)$ 。
即外层需要枚举 $O(n)$ 个数，内层需要暴力匹配 $O(n)$ 次), 无法满足题目的要求。

但仔细分析这个过程，我们会发现其中执行了很多不必要的枚举，如果已知有一个 $x,x+1,x+2,?,x+y$ 的连续序列，而我们却重新从 $x+1$ ,$x+2$ 或者是 $x+y$ 处开始尝试匹配，那么得到的结果肯定不会优于枚举 $x$ 为起点的答案，因此我们在外层循环的时候碰到这种情况跳过即可。

那么怎么判断是否跳过呢？ 由于我们要枚举的数 $x$一定是在数组中不存在前驱数$x?1$的，不然按
照上面的分析我们会从 $x?1$ 开始尝试匹配，因此我们每次在哈希表中检查是否存在 $x?1$ 即能判断是否需要跳过了。

class Solution(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        longest_streak = 0
        num_set = set(nums)

        for num in num_set:
            if num - 1 not in num_set:
                current_num = num
                current_streak = 1

                while current_num + 1 in num_set:
                    current_num += 1
                    current_streak += 1

                longest_streak = max(longest_streak, current_streak)

        return longest_streak    

时间复杂度： $O(n)$,其中 $n$ 为数组的长度。具体分析已在上面正文中给出。
空间复杂度： $O(n)$。哈希表存储数组中所有的数需要 $O(n)$ 的空间。

在 Python 中，使用 in 操作符来判断元素是否存在于 set 中，其平均时间复杂度是 O(1)。这是因为 set 是基于哈希表实现的，在大多数情况下，通过哈希函数将元素映射到哈希表的特定位置，可以在常数时间内进行查找操作。当然，如果出现哈希冲突，时间复杂度可以增高到 O(n)。但是在平均情况下，查询元素是否在 set 中仍然是效率很高的操作。