LeetCode 560 https://leetcode.cn/problems/subarray-sum-equals-k/description/ 难度：中等 本题是前缀和题目。需要注意只有满足单调性的时候才能使用滑动窗口。 s 为前缀和，如果 i 到 j 的和为 k，那么 s[j] - s[i] == k。 枚举右，维护左，通过哈希表统计有多少 s[i] == s[j] - k。 时间复杂度：O(n)，其中 n 为 nums 的长度。 空间复杂度：O(n)。 ...
LeetCode 128 https://leetcode.cn/problems/longest-consecutive-sequence/description/ 难度：中等 对于 nums 中的元素 x，以 x 为起点，不断查找下一个数 x+1,x+2,⋯ 是否在 nums 中，并统计序列的长度。 为了做到 O(n) 的时间复杂度，需要两个关键优化： 把 nums 中的数都放入一个哈希集合中，这样可以 O(1) 判断数字是否在 nums 中。 如果 x−1 在哈希集合中，则不以 x 为起点。为什么？因为以 x−1 为起点计算出的序列长度，一定比以 x 为起点计算出的序列长度要长！这样可以避免大量重复计算。比如 nums=[3,2,4,5]，从 3 开始，我们可以找到 3,4,5 这个连续序列；而从 2 开始，我们可以找到 2,3,4,5 这个连续序列，一定比从 3 开始的序列更长。 ⚠ 注意：遍历元素的时候，要遍历哈希集合，而不是 nums！如果 nums=[1,1,1,…,1,2,3,4,5,…]（前一半都是 1），遍历 nums 的做法会导致每个 1 都跑一个 O(n) 的循环，总的循环次数是 \(O(n^2)\)，会超时。 时间复杂度：O(n)，其中 n 是 nums 的长度。在二重循环中，每个元素至多遍历两次：在外层循环中遍历一次，在内层循环中遍历一次。所以二重循环的时间复杂度是 O(n) 的。比如 nums=[1,2,3,4]，其中 2,3,4 不会进入内层循环，只有 1 会进入内层循环。 空间复杂度：O(n)。 ...
LeetCode 76 https://leetcode.cn/problems/minimum-window-substring/description/ 难度：困难 这是滑动窗口的题目。s 覆盖 t 的意思就是对 t 中的每个字母，s 里的出现次数都不小于 t 里的出现次数。出现次数使用哈希表来计数，在本题可以使用数组来进行优化。 时间复杂度：O(∣Σ∣m+n)，其中 m 为 s 的长度，n 为 t 的长度，∣Σ∣ 为字符集合的大小，本题字符均为英文字母，所以 ∣Σ∣=52。注意 left 只会增加不会减少，left 每增加一次，我们就花费 O(∣Σ∣) 的时间。因为 left 至多增加 m 次，所以二重循环的时间复杂度为 O(∣Σ∣m)，再算上统计 t 字母出现次数的时间 O(n)，总的时间复杂度为 O(∣Σ∣m+n)。 空间复杂度：O(∣Σ∣)。如果创建了大小为 128 的数组，则 ∣Σ∣=128。 ...
LeetCode 1 https://leetcode.cn/problems/two-sum/description/ 难度：简单 LeetCode 第一题，哈希表的应用。 时间复杂度：O(n)，其中 n 为 nums 的长度。 空间复杂度：O(n)。哈希表需要 O(n) 的空间。 ...
LeetCode 146 https://leetcode.cn/problems/lru-cache/description/ 难度：中等 本题是双向链表和哈希表的经典题目。每个节点有 key，value，还有两个指针 prev 和 next 分别指向前一个和下一个节点。 此外，链表中还包含一个 dummy 节点，让每个节点的 prev 和 next 都不为空。 时间复杂度：所有操作均为 O(1)。 空间复杂度：O(min(p,capacity))，其中 p 为 put 的调用次数。 ...
LeetCode 0003 https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/ 难度：中等 本题为经典的哈希表加滑动窗口的题目，哈希表统计窗口内字符出现次数，如果窗口右端点字符出现次数大于 1，右移左端点，直到无重复字符，最后更新答案。窗口的长度为 right - left + 1。 时间复杂度：O(n)，其中 n 为 s 的长度。注意 left 至多增加 n 次，所以整个二重循环至多循环 O(n) 次。 空间复杂度：O(∣Σ∣)，其中 ∣Σ∣ 为字符集合的大小，本题中字符均为 ASCII 字符，所以 ∣Σ∣≤128。 ...