LeetCode 热题 100

约 4425 字大约 15 分钟

LeetcodePythonC++

2025-08-30

LeetCode 热题 100

哈希

1. 两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
提示
思路：用一个哈希表来存储遍历过的元素，后续遍历如果需要的值在哈希表中有，那么就查找到了。
Python
```
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
    dic = {}
    for i, x in enumerate(nums):
        find = target - x
        if find in dic:
            return [dic[find], i]
        else:
            dic[x] = i
```
C++
```
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> mp;
        for (int j = 0; ; j++) {
            auto it = mp.find(target - nums[j]);
            if (it != mp.end()) {
                return {it->second, j};
            }
            mp[nums[j]] = j;
        }
    }
};
```
时间复杂度： $O(n)$ 。
空间复杂度： $O(n)$ 。
49. 字母异位词分组
给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。
示例 1：
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
解释：
- 在 strs 中没有字符串可以通过重新排列来形成 "bat"。
- 字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。
- 字符串 "ate" ，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此。
示例 2：
输入: strs = [""]
输出: [[""]]
示例 3：
输入: strs = ["a"]
输出: [["a"]]
提示
思路：一开始想过用Counter，可以区分出不同的字符串是否是一组字母异位词，但是仍然需要花费额外的时间去判断当前字符串是属于哪一组的字母异位词。因此改用sorted，排序后的字符串天然拥有唯一性，适合搭配哈希表来使用，key表示排序后的字符串，value使用一个列表来整合这组的字母异位词。
```
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:

    from collections import defaultdict

    dic = defaultdict(list)
    for s in strs: # O(n)
        sorted_s = ''.join(sorted(s)) # O(mlogm)
        dic[sorted_s].append(s)

    return list(dic.values())
```
时间复杂度： $O(nmlogm)$ 。其中 n 为 strs 的长度，m 为 strs[i] 的长度。每个字符串排序需要 $O(mlogm)$ 的时间，有 n 个字符串，所以总的时间复杂度为 $O(nmlogm)$ 。
空间复杂度： $O(nm)$ 。
128. 最长连续序列
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9
示例 3：
输入：nums = [1,0,1,2]
输出：3
提示
思路：set拥有去除重复元素的功能，因此将nums放入哈希集合，此时注意如果2,3,4是连续的，那么1,2,3,4必然连续，因此如果遇到当前元素-1也在集合内部，避免重复计算直接跳过即可。
```
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
    st = set(nums)
    res = 0
    for x in st:
        if x - 1 in st:
            continue
        y = x + 1
        while y in st:
            y += 1
        res = max(res, y - x)
    return res
```
时间复杂度： $O(n)$ 。
空间复杂度： $O(m)$ 。其中 m 是 nums 中的不同元素个数。

双指针

283. 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意，必须在不复制数组的情况下原地对数组进行操作。

示例 1：

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2：

输入: nums = [0]
输出: [0]

提示

思路：双指针的思路，慢指针初始指向 0 ，快指针遍历整个数组，遇到非 0 的数就用慢指针所在空间存储，同时慢指针+1，即指向下一个空位。

Python

class Solution:
def moveZeroes(self, nums: List[int]) -> None:
    """
    Do not return anything, modify nums in-place instead.
    """
    left = 0
    for i, num in enumerate(nums):
        if num:
            nums[i], nums[left] = nums[left], nums[i]
            left += 1
    return nums

C++

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int left = 0;
        for (int &x : nums) {
            if (x) {
                swap(x, nums[left]);
                left++;
            }
        }
    }
};

11. 盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明：你不能倾斜容器。
示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。（原图请跳转链接查看）
示例 2：
输入：height = [1,1]
输出：1
提示
思路：关键是理解短板效应。如示例一的图，我们在首尾各使用一个指针，计算初始容积，移动指针，如果容积变大，则更新。问题是怎么移动，移动哪条边？假如我们移动长的边，例如左边红色的线，首先让它变短（右移一位），容积必然变小，因为矩形的长宽都短了，然后如果变长呢？长变短宽不变（因为短板效应，容积和短的边有关），因此我们只能移动短的边。
重要
思考：为什么相等时移动左右两边都可以？首先，如果遇到左右相等的情况，那么里面都是比当前宽短的和只有一根比宽长的这两种情况，是可以直接 break 的，因为不可能比当前容积大，更不用说比从初始就记录的 res 大了，因此自然移动左右都可以。而只有当内部有两根以上长的情况，才会可能比当前容积大，既然有两根以上，那么先移动左还是右自然最终都会移到这两根内部最长的上面。
```
class Solution:
def maxArea(self, height: List[int]) -> int:
    left = 0
    right = len(height) - 1
    res = (right - left) * min(height[right], height[left])
    while left < right:
        if height[left] == height[right]:
            break
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
        res = max(res, (right - left) * min(height[right], height[left]))
    return res
```
时间复杂度： $O(n)$ 。
空间复杂度： $O(1)$ 。

15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示

思路：要充分利用已经排好序的信息，面多加水水多加面。用一个指针i遍历数组（优化：避免重复，遇到和上一个元素相同则跳过），j和k以首尾的方式来遍历i后面的部分，如果ijk大于0，那么k变小，如果ijk小于0，那么k变大，当ijk等于0时，就找到了，存储结果，jk同时中间移动一位，查找其他可能（优化：避免重复，遇到j和j-1、k和k+1相同则跳过）。

class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
    nums.sort() # O(nlogn)
    res = []
    n = len(nums)
    for i in range(n - 2): # O(n)
        if i > 0 and nums[i] == nums[i - 1]: # 优化：避免重复
            continue
        if nums[i] + nums[i + 1] + nums[i + 2] > 0: # 优化：最小的三数大于0，则后续不可能等于0
            break
        if nums[i] + nums[-2] + nums[-1] < 0: # 优化：当前和最大的两数小于0，则后续不可能等于0
            continue
        j = i + 1
        k = n - 1
        while j < k: # O(n)
            if nums[i] + nums[j] + nums[k] > 0:
                k -= 1
            elif nums[i] + nums[j] + nums[k] < 0:
                j += 1
            else:
                res.append([nums[i], nums[j], nums[k]])
                j += 1
                while nums[j] == nums[j - 1] and j < k: # 优化：避免重复
                    j += 1
                k -= 1
                while nums[k] == nums[k + 1] and j < k: # 优化：避免重复
                    k -= 1
    return res

时间复杂度： $O(n^2)$ 。

空间复杂度： $O(1)$ 。

42. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
提示
思路：考虑某一个位置能接多少水，取决于这个位置左边最大值和右边最大值，换种说法，可以把这个位置看成有一个木桶，木桶的左长度就是左边最大值，右长度就是右边的最大值，当前接水量为左长度和右长度的最小值减去柱子高度（短板效应）。因此很自然想到分别计算出前缀最大值和后缀最大值。
```
class Solution:
def trap(self, height: List[int]) -> int:
    n = len(height)
    res = 0
    pre_max = [0] * n
    pre_max[0] = height[0]
    suf_max = [0] * n
    suf_max[-1] = height[-1]
    for i in range(1, n): # O(n)
        pre_max[i] = max(pre_max[i-1], height[i])
    for i in range(n - 2, -1, -1): # O(n)
        suf_max[i] = max(suf_max[i+1], height[i])

    for i in range(n): # O(n)
        res += min(pre_max[i], suf_max[i]) - height[i]
    return res
```
时间复杂度： $O(n)$ 。
空间复杂度： $O(n)$ 。
重要
优化空间复杂度：考虑现在只知道前几项的最大值和后几项的最大值，中间的状态不知道，但如果后几项中的最大值比前几项大，根据短板效应，即使中间状态还有更大的板子，装水的量也取决于短板，因此前几项的水量可以直接计算，反之亦然。
```
class Solution:
def trap(self, height: List[int]) -> int:
    n = len(height)
    res = 0
    left = 0
    right = n - 1
    pre_max = 0
    suf_max = 0

    while left < right: # O(n)
        pre_max = max(pre_max, height[left])
        suf_max = max(suf_max, height[right])
        if pre_max < suf_max:
            res += pre_max - height[left]
            left += 1
        else:
            res += suf_max - height[right]
            right -= 1
    return res
```
时间复杂度： $O(n)$ 。
空间复杂度： $O(1)$ 。

滑动窗口

3. 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。
示例 1：
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2：
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3：
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。
提示
思路：典型的滑动窗口思想。
```
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:

    from collections import Counter
    cnt = Counter()
    left = 0
    res = 0
    for right, c in enumerate(s):
        cnt[c] += 1
        while cnt[c] > 1:
            cnt[s[left]] -= 1
            left += 1
        res = max(res, right - left + 1)
    return res
```
时间复杂度： $O(n)$ 。
空间复杂度： $O(n)$ 。
438. 找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
示例 1：
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
示例 2：
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
提示
思路：典型的滑动窗口思想。
```
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
    from collections import Counter
    cnt = Counter()
    target = Counter(p)
    res = []
    left = 0
    for i, c in enumerate(s):
        cnt[c] += 1
        left = i - len(p) + 1
        if left < 0:
            continue
        if cnt == target:
            res.append(left)
        cnt[s[left]] -= 1
        if cnt[s[left]] == 0:
            del cnt[s[left]]
    return res
```
时间复杂度： $O(∣Σ∣m+n)$ ，其中 m 是 s 的长度，n 是 p 的长度，∣Σ∣=26 是字符集合的大小。
空间复杂度： $O(∣Σ∣)$ 。返回值不计入。

子串

560. 和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2

示例 2：

输入：nums = [1,2,3], k = 3
输出：2

提示

思路：先转化为前缀和的思路，再转化为两数之和，灵神的思路太妙了，建议多看几遍灵神的题解。

Python

class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
    s = [0] * (len(nums) + 1)
    for i, x in enumerate(nums):
        s[i + 1] = s[i] + x
    res = 0
    cnt = defaultdict(int)
    for sj in s:
        res += cnt[sj - k]
        cnt[sj] += 1
    return res

C++

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        vector<int> v;
        v.resize(nums.size() + 1);
        for (int i = 0; i < nums.size(); i++) {
            v[i + 1] = v[i] + nums[i];
        }
        int res = 0;
        unordered_map<int, int> cnt;
        for (auto sj : v) {
            res += cnt.contains(sj - k) ? cnt[sj - k] : 0;
            cnt[sj]++;
        }
        return res;
    }
};

时间复杂度： $O(n)$ ，其中 n 为 nums 的长度。

空间复杂度： $O(n)$ 。

239. 滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1
出：[1]
提示
思路：用一个双端队列构造一个从大到小的单调栈，无非是入和出的逻辑，如果当前元素比队尾元素大，那么不符合单调栈，队尾元素出列（右端），直到符合才入栈；如果队头元素超过了k大小的窗口，需要及时出列（左端）；每一轮循环栈内最大元素（左端）就是当前窗口的最大值。
Python
```
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
    from collections import deque
    q = deque()
    res = []
    for i, num in enumerate(nums):
        while q and num > nums[q[-1]]:
            q.pop()
        q.append(i)
        left = i - k + 1
        if left > q[0]:
            q.popleft()
        if left >= 0:
            res.append(nums[q[0]])
    return res
```
C++
```
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        deque<int> q;
        vector<int> res(n - k + 1);
        for (int i = 0; i < n; i++) {
            while (!q.empty() && nums[i] > nums[q.back()]) {
                q.pop_back();
            }
            q.push_back(i);
            int left = i - k + 1;
            if (left > q.front()) {
                q.pop_front();
            }
            if (left >= 0) {
                res[left] = nums[q.front()];
            }
        }
        return res;
    }
};
```
时间复杂度： $O(n)$ ，其中 n 为 nums 的长度。由于每个下标至多入队出队各一次，所以二重循环的循环次数是 O(n) 的。
空间复杂度： $O(min(k,U))$ ，其中 U 是 nums 中的不同元素个数（本题至多为 20001）。双端队列至多有 k 个元素，同时又没有重复元素，所以也至多有 U 个元素，所以空间复杂度为 $O(min(k,U))$ 。返回值的空间不计入。