LeetCode Hot100-Day 1

Created by: Yuanpeng QU
Created time: 2025年8月14日 11:27

15. 三数之和[mid]

给一个数组nums，求 满足nums[i]+nums[j]+nums[k]==0的所有[nums[i],nums[j],nums[k]]组合，顺序没有要求，但是不能有重复的组合出现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        
        n = len(nums)
        # left, right = 1, n-1 关键2
        res = []

        for k in range(n):
            if nums[k] > 0:
                break

            if k > 0 and nums[k] == nums[k-1]:
                continue
            
            left, right = k+1, n-1 # 关键2

            while left < right:
                if nums[left] + nums[right] + nums[k] < 0: # 关键2
                    left += 1
                elif nums[left] + nums[right] + nums[k] > 0:
                    right -= 1
                else:
                    res.append([nums[k],nums[left],nums[right]])

                    while left < right and nums[left] == nums[left+1]:# 关键1
                        left += 1
                    while left < right and nums[right] == nums[right-1]:
                        right -= 1
                    
                    left += 1 #关键2
                    right -= 1
        return res
  • 我想到的地方：先把nums排序，这样就能用双指针做，也就是先固定一个k，再求nums[i]+nums[j]判断其是否等于-nums[k]从而得到一组结果。但是错误的是我想着同时挪动两个指针往中间靠了，所以没写出来。
  • 关键1：去重，k和left和right所对应的nums的值可能和上一个或下一个重复，需要跳过，并且需要一个list保存结果
  • 关键2：left, right = k+1, n-1要在for 里面这样才能确保left能够更新，并且nums[left] + nums[right] + nums[k] < 0 的时候是left+=1而不是>0的时候，仔细想想就知道如果nums[left] + nums[right]的值要小过结果的话，只有把nums[left]往大的值挪才有可能让结果==0。对于nums[right]也同理。 只有最后等于0的结果出现了才需要left和right都往中间挪，这是因为它们现在所在位置的值都被用上了，避免重复使用。

283. 移动零[easy]

给一个数组nums，将所有0移动到最后面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        slow, fast = 0, 0
        
        while fast < len(nums):
            if nums[fast] != 0:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        while slow < len(nums):
            nums[slow] = 0
            slow += 1
        
        return nums
  • 关键思路：双指针（快慢指针版）
  • 一开始就想错了不能用朝中间靠拢版的双指针，问题的关键在于使用fast遍历整个数组，slow则用于储存非0的数后+1，并且两个指针开始都指向0，这样就能保证slow和其左边的值都是非0的，最后等fast遍历完后将slow的右边全部赋0就可以了。
  • 改进：用for循环替代while fast<len(nums): fast+=1和while slow < len(nums): slow += 1。这会更加python！

75. 颜色分类[mid]

给一个数组nums里面元素只有0，1，2，按顺序表示红白蓝，现在要求按照这个顺序把nums内所有的元素原地排序，不能用sort，进阶方法是只遍历一次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import collections
class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        dict_num = collections.defaultdict(int)
        for i in range(len(nums)):
            if nums[i] == 0:
                dict_num[0] += 1
            elif nums[i] == 1:
                dict_num[1] += 1
            else:
                dict_num[2] += 1
        
        for j in range(len(nums)):
            if j < dict_num[0]:
                nums[j] = 0
            elif j < dict_num[0]+dict_num[1]:
                nums[j] = 1
            else:
                nums[j] = 2
            
        return nums
  • 我的做法：哈希储存+遍历2次
  • 简单直观的想法就是遍历第一次找一个地方储存0，1，2出现的次数，再遍历一次将出现0，1，2出现的次数分别填上去
  • 缺点是空间复杂度高
  • 最优解是3指针，
  • p0：指向 0 区的末尾。初始时 p0 = 0。[0, p0-1] 区间内的都是0。
  • p2：指向 2 区的开头。初始时 p2 = len(nums) - 1。[p2+1, n-1] 区间内的都是2。
  • curr：当前遍历到的元素的指针。初始时 curr = 0。

我们让 curr 指针从头到尾遍历数组，在 curr <= p2 的条件下循环，根据 nums[curr] 的值来执行不同的操作：

  • 如果 nums[curr] == 0:
    • 说明这个 0 应该被放到 0 区。
    • 我们将 nums[curr] 和 nums[p0] 进行交换。
    • 交换后，p0 指向的元素已经处理完毕，所以 p0 向右移动一位 (p0 += 1)。
    • curr 指针也向右移动一位 (curr += 1)，继续检查下一个元素。
  • 如果 nums[curr] == 2:
    • 说明这个 2 应该被放到 2 区。
    • 我们将 nums[curr] 和 nums[p2] 进行交换。
    • 交换后，p2 指向的元素已经处理完毕，所以 p2 向左移动一位 (p2 -= 1)。
    • 注意： 此时 curr 指针不能移动！因为从 p2 交换过来的那个新 nums[curr] 还没有被检查过，它可能是 0、1 或 2，需要下一轮循环来处理它。
  • 如果 nums[curr] == 1:
    • 说明这个 1 就在它应该在的位置（在 0 区和 2 区之间）。
    • 我们不需要做任何交换，只需要移动 curr 指针，继续检查下一个元素 (curr += 1)。

循环在 curr 指针“追上”或超过 p2 指针时结束。此时，整个数组的排序就完成了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from typing import List

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        荷兰国旗问题解法 (三指针)
        """
        n = len(nums)
        # p0 指向 0 区的末尾边界
        # p2 指向 2 区的开头边界
        p0, p2 = 0, n - 1
        # curr 用于遍历数组
        curr = 0
        
        # 当 curr 还没有“追上” p2 时
        while curr <= p2:
            if nums[curr] == 0:
                # 发现 0，与 p0 指向的元素交换
                nums[curr], nums[p0] = nums[p0], nums[curr]
                # 交换后，p0 和 curr 都向前进一步
                p0 += 1
                curr += 1
            elif nums[curr] == 2:
                # 发现 2，与 p2 指向的元素交换
                nums[curr], nums[p2] = nums[p2], nums[curr]
                # 交换后，p2 向前一步
                # curr 不动，因为换过来的新 nums[curr] 需要被重新判断
                p2 -= 1
            else: # nums[curr] == 1
                # 发现 1，位置正确，curr 直接向前一步
                curr += 1

42.接雨水[hard]

典中典

image.png

给一个数组height表示各个位置上的方块个数（高度），求整个数组表示的图形能接多少个水方块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        left, right = 0, len(height)-1
        left_max, right_max = 0, 0
        total = 0

        if len(height) <= 2:
            return 0

        while left < right:
            if height[left] < height[right]:
                if height[left] >= left_max:
                    left_max = height[left]
                else:
                    total += left_max - height[left]
                left += 1
            else:
                if height[right] >= right_max:
                    right_max = height[right]
                else:
                    total += right_max - height[right]
                right -= 1
        
        return total
  • 核心就是双指针（往中间靠拢版）
  • 关键1：这题和11. 盛最多水的容器类似，都是双指针，不同的地方在于11可以通过算left和right围起来的面积来求最大值，而这题可能有多个水坑可以接水，所以需要设置左边和右边都要有个最大高度来确保装水的量。而最大高度则通过每次遍历指针的时候与其对比不断更新。
  • 关键2：确保有最大高度后，只需要计算在遍历的时候当前的位置头顶上能够顶几个水方块即可，注意不需要知道当前水坑能够装多少，只需要计算每一个位置的水方块最后加起来就可以。而这个方块数则可以通过最大高度-当前高度来得到。
  • 关键3：总数小于等于2的时候没法围成水坑，所以直接返回0

3. 无重复字符的最长子串[mid]

给一个字符串s，求它里面最长的无重复字符的子串长度，其中子串和子序列的区别要搞清楚。

1
2
3
4
5
6
7
8
9
10
11
12
13

left = 0
max_len = 0
char_set = set() 

for right in range(len(s)):
	while s[right] in char_set:
		char_set.remove(s[left])
		left += 1
	char_set.add(s[right])
	
max_len = max(max_len, right-left+1)
return max_len
  • 模式：滑动窗口+哈希储存
  • 想象一个窗口，从左开始，一直把不重复的元素放入set中，直到right遍历到set里重复的元素，这个时候就需要按顺序从左开始删除元素，直到删除到set里没有重复元素为止，所以要用while而不是if，最后right走到终点后right-left+1就是最大长度
  • 关键：使用set储存窗口元素，为什么不用defaultdict（int）？是因为我们只需要判断x字符在不在哈希表里，而不需要判断有多少个x字符在不在。set集合可以用add和remove来添加和删除
  • 需要不断更新max_len是因为right到最后，但是最长子串可能在中间，时刻更新max_len确保一直是最大的

239. 滑动窗口最大值[hard]

给定一个数组nums，再给定一个滑动窗口大小k，输出滑动窗口从头到尾中每个窗口的最大值组成的list

1
2
3
4
5
6
7
8
9
10
11
输入：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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        left = 0
        right = left + k - 1 
        res = []
        max_i = float('-inf')
        while right < len(nums):
            for i in range(left, right+1):
                max_i = max(max_i, nums[i])
            res.append(max_i)
            right += 1
            left += 1
            max_i = float('-inf')

        return res
  • 我直接暴力解决，但是超时了，因为时间复杂度为O(N*k), N和k都很大时运算量爆炸
  • 最佳解法是用双向队列deque解决，时间复杂度为O(N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
   deque = collections.deque() # 创建小队
   res = []

   for i in range(len(nums)):
       
       # 规则3， 队头离开了滑动窗口需要请走
       if deque and deque[0] <= i - k:
           deque.popleft()
       # 规则2， 每个入队的元素需要和队里所有成员“比武”，比不过的老队员全部踢出去，这样就能保证每一个循环的队头都是最大的
       while deque and nums[deque[-1]] < nums[i]:
           deque.pop()
       # 规则1， 新人入队， 队里只存nums的index，而不存值
       deque.append(i)

       # 窗口形成后，将每次队里的最大值（队头）取出
       if i >= k - 1:
           res.append(nums[deque[0]])
return res

  • 为什么要用双向队列？

    • 用暴力法 O(N*k) 之所以慢，是因为每当窗口向右滑动一格时，我们都重新在 k 个元素里找了一遍最大值。这里面有大量的重复劳动。
    • 比如窗口从 [1, 3, -1] 滑动到 [3, -1, -3]。在 [1, 3, -1] 中，3 是最大值。当 1 离开，-3 加入时，我们其实不需要重新比较 3 和 -1。我们只需要让新来的 -3 和之前的最大值 3 比较一下就行。
    • 但问题是，如果离开的元素恰好是最大值怎么办？比如从 [3, -1, -3] 滑动到 [-1, -3, 5]，此时最大值 3 离开了，我们就需要知道剩下元素里的“第二大值”是谁。
    • 所以，核心难点在于：我们需要一个数据结构，它能帮我们快速知道“当旧的最大值离开窗口后，新的最大值是谁？”

  • 用一个“精英小队”来解决问题 (双端队列 Deque 的比喻)

    想象一下，我们不让窗口里的所有 k 个成员都参与“比武招亲”，而是组织一个“精英小队”（这就是我们的双端队列 Deque）。

    这个小队有几条非常严格的规矩：

    1. 队员身份：小队里只记录队员的编号（即数组索引 index）。
    2. 入队规矩（从队尾进）：新人 A 想要入队时，要从队尾开始，跟前面的老队员 B、C、D … 挨个比武。如果老队员打不过新人 A (nums[老队员] < nums[A])，那么这个老队员就直接被踢出队伍（从队尾踢出）。A 会一直踢到遇见一个比他强的，或者队伍里没人了，他才从队尾站进去。
    3. 出队规矩（从队头出）：我们只关心队头的那个人。如果发现他的编号太老了（已经滑出窗口范围了），就把他从队头请出去。

    这个规矩带来了什么神奇效果？

    • 因为规矩2的存在，这个“精英小队”从队头到队尾，永远是按“武力值”（即 nums 的值）从大到小排列的。
    • 因此，队头的那个队员，永远是当前小队里最能打的，也就是当前窗口的最大值！

  • 这样顺序就是，先创建一个deque，用来储存index，nums里面的第一个值进来后先判断规则3和规则2（最前面有判断deque是否为空）保证第一个元素能直接进来。然后第二个元素进来后需要和第一个元素所对应的nums值进行比较，如果赢了那就把第一个踢掉，值最大的index当队长！保证队头的index对应的值一定是这次for里最大的。

  • 以此类推，先等到遍历到窗口长度的时候（i≥k-1,也就是nums的下标到长度k的时候）取出当前窗口最大的队头记录，然后到下一轮循环的时候根据规则3判断窗口的左边界i-k是否已经比队头的index大了将小的index对应的队头移出去就完成移动了。

  • 注意最后的if i≥k-1表示是否已经形成窗口，形成窗口后窗口就不会消失了也就是说之后的for循环代表的窗口头边界往前移一位那就会产生一个新的窗口最大值。

438. 找到字符串中所有字母异位词[mid]

给两个字符串s和p，找出s中满足p的所有异位词，异位词就是不管字母顺序只管字符串长度是否相等，字母是否相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import collections
class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        s_len, p_len = len(s),len(p)
        if s_len < p_len:
            return []
        
        p_dict = collections.defaultdict(int)
        window = collections.defaultdict(int)
        res = []

        for i in range(p_len):
            p_dict[p[i]] += 1
            window[s[i]] += 1
        
        if window == p_dict:
            res.append(0)
        
        for j in range(p_len, s_len):
            s_in = s[j]
            s_out = s[j-p_len]

            window[s_in] += 1
            window[s_out] -= 1

            if window[s_out] == 0:
                del window[s_out]

            if window == p_dict:
                res.append(j - p_len + 1) # 这是子串的头字符的index
        return res
  • 这题用滑动窗口+哈希，看到固定字符串长度就想到滑动窗口
  • 问题的关键在于我们创建的两个带默认值的哈希表，和239题不一样，这次的滑动窗口需要我们先填充元素，也就是说我们创建p的哈希表和window哈希表，p_dict初始化就是将p的值全部放进去变成{’a’:1, ‘c’:2, …}。 而window哈希表也需要初始化，内容就是把它放到s里的第一组值。
  • 这样我们在初始化之后就可以开始挪动窗口了，指向窗口头部的for循环直接从p_len位置开始直到s结束位置，窗口头部指针指向的值加入window，并且将窗口尾部的指针指向的值从window里扔掉，这样就是window[s[j]]+=1, window[s[j-p_len]] -=1
  • 不出错的关键在于如果window里面被删除的元素没了的话，要使得if window == p_dict生效，一定需要把归零的元素del 掉
  • 最后通过if window == p_dict判断窗口里的子串是否是p的异位，将是的子串的开头字符的下标j-p_len+1存入res即可。

506. 和为 K 的子数组[mid]

给定一个数组nums，求能够满足和为k的所有子数组，其中的元素是连续的

这题是经典的前缀和的应用题，什么是前缀和？给定一个长度为j+1的数组nums，有

1
2
prefix_map[i] = nums[0]+…+nums[i]
prefix_map[j] = nums[0]+…+nums[i] + nums[i+1]+…+nums[j]

想要求一个连续子数组的和sum(nums[i,..,j])可以通过prefix_map[j]-prefix[i-1]得到

**最关键：**所以这题能够转化为想要求子数组和为k(nums[i~j])的数目，有：

prefix_map[j] = prefix_map[i-1]+k，也就是prefix_map[i-1] = prefix_map[j] - k

这个时候prefix_map[j]就是for循环遍历的指针指到的位置之前的和，可以记为curr_sum,而k是满足条件的子数组的和，prefix_map[i-1]则是要通过上面公式来在数组中比对的和

  • 所以这个时候就明确了：我们需要将cur_sum每走一步就记录一次，把记录存在hashmap里，记录完了后再和k相减，看看hashmap里有没有满足相减结果的值，有的话就说明现在有一个前缀和满足了，计数器+1
  • 关键1：在hashmap初始化的时候不要忘了0这个数，因为有可能会出现nums的两个值和刚好被k整减，最后为0的结果，或者是nums里面刚好有等于k的数。所以初始化一定要prefix_map[0] += 1
  • 关键2：count += prefix_map[target_sum] 而不是count += 1
  • 关键3：prefix_map[curr_sum] += 1 这个一定放在if后面，因为if里面涉及到了prefix_map的更新，也就是如果curr_num等于target_sum的情况（k=0时）如果先把 current_sum 的计数值加了1，然后又用 current_sum 本身作为 target 去查找，你就会把自己刚刚放进去的那个计数值也算进去，导致重复计算。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import collections
class Solution(object):
    def subarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        prefix_map = collections.defaultdict(int)
        prefix_map[0] = 1
        curr_sum, count = 0, 0

        for j in range(len(nums)):
            curr_sum += nums[j]

            target_sum = curr_sum - k
            if target_sum in prefix_map:
                # count += 1 不对，要存的是target_sum的个数，也就是找到多少组
                # 并且count += 1 会导致某个prefix_map[x] = 2的情况时漏掉一次，如nums = [1, -1, 1, -1, 1], k = 1
                count += prefix_map[target_sum]

            prefix_map[curr_sum] += 1 #这个一定放在if后面

        return count