LeetCode 146 https://leetcode.cn/problems/lru-cache/description/ 难度：Mid 本题是双向链表和哈希表的经典题目。每个节点有 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/ 难度：Mid 本题为经典的哈希表加滑动窗口的题目，哈希表统计窗口内字符出现次数，如果窗口右端点字符出现次数大于 1，右移左端点，直到无重复字符，最后更新答案。窗口的长度为 right - left + 1。 时间复杂度：O(n)，其中 n 为 s 的长度。注意 left 至多增加 n 次，所以整个二重循环至多循环 O(n) 次。 空间复杂度：O(∣Σ∣)，其中 ∣Σ∣ 为字符集合的大小，本题中字符均为 ASCII 字符，所以 ∣Σ∣≤128。 ...