LeetCode Hot100

哈希

适用场景：

collections.defaultdict(type) 字典类型，自动添加某类型元素。思考哈希值如何计算、如何存储。
涉及到查重、判断是否存在相似元素时，可以使用。

例题

字母异位词分组

1
2
3
4
5


1. collections.defaultdict(list) 满足返回的为各个字符集;通过 mp[key].append(st) 来给字典加入值。

2. "".join(sorted(s)) 来排序、求重

3. return list(mp.values()) 直接返回值的列表

最长连续序列

1
2
3


1. 利用集合去重、提高查找速度

2. 分析连续序列所满足的条件、限制的条件：若n-1在序列中，则无需遍历n，利用包含关系来简化算法

双指针

适用场景：

多变量问题，变量间存在某种关系
首尾比较、字符移动
同向、相向遍历问题

通法：

初始化左右指针，并考虑其作用、意义
写循环，考虑边界条件、指针变化规律，注意规范

例题

移动0

1
2
3


1. 由于要将0移到末端，所以右指针需要指向非零数，左指针指向0，两数交换即可

2. 边界条件：右指针到末尾即停止，因为已经没有非零数需要向前移动

盛最多水的容器

1
2
3
4
5
6


1. 暴力思路：直接两层for循环从左向右遍历

2. 思考：有必要依次循环吗？什么情况下会出现最大值？如何趋向最大值？

3. 优化：计算面积的公式是：(right - left)*min(height[left],height[right])
那么不妨从 right - left 最大时开始遍历，这时想到双指针。那么往里收缩的条件就变成比较height的大小。如果height更大就直接保留，舍去了很多不必要的情况。

三数之和

1
2
3
4
5


1. 难点在于去重，各个值的组合不能重复

2. 思考："不能重复"这一要求能不能转化？

3. 优化：不妨将数组重新排序，从而让三个数也排序地输出，免去了去重的麻烦。更进一步，a+b+c=0是等式关系，而a确定后，b是递增的，c又是由a、b决定的，故可以将b、c用双指针遍历，一增一减，完全符合要求。

滑动窗口

适用情景：

连续子数组、子序列
在一个范围内进行条件统计
具有单调性，随窗口移动时不必全部更新
要点在于，将问题放到窗口中讨论，控制窗口来控制遍历所有可能情况

模板：

右入（直到装满窗口） - 判断 - 更新 - 左出

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


ans = vowel = 0
for i, c in enumerate(s):  # 枚举窗口右端点 i
    # 1. 右端点进入窗口
    if c in "aeiou":
        vowel += 1

    left = i - k + 1  # 窗口左端点
    if left < 0:  # 窗口大小不足 k，尚未形成第一个窗口
        continue

    # 2. 更新答案
    ans = max(ans, vowel)
    if ans == k:  # 答案已经等于理论最大值
        break  # 无需再循环

    # 3. 左端点离开窗口，为下一个循环做准备
    if s[left] in "aeiou":
        vowel -= 1
return ans

定长

无重复字符的最长字串

1
2
3
4
5
6
7


1. 先模拟，右指针移动到发现重复字符时为边界

2. 边界处理：发现移动左指针时，无需将右指针移动回来（单调性），移动左指针即可

3. 注意：边界要分清楚！！right - left 的相对关系不能错

4. Counter(str) 方法，统计各个字符出现的次数

几乎唯一子数组的最大和

如果 nums 的一个子数组有至少 m 个互不相同的元素，我们称它是 几乎唯一 子数组。

1
2
3
4
5
6
7


1. 区间求和，考虑用滑动窗口

2. 有两个变量 m,k 分别维护即可。用一个字典来标记是否有重复！

3. 注意：当 defaultdict(int) 为空时，需要将元素删去！否则统计长度时会出错。
	if cnt[out] == 0:
    	del cnt[out]

不定长 + 越长越合法

每个字符最多出现两次

给你一个字符串 s ，请找出满足每个字符最多出现两次的最长子字符串，并返回该子字符串的最大长度。

1
2
3


1. 区间判断，仍然是滑动窗口，不同之处在于变成了不定长滑窗

2. 不定长的判断逻辑修改一下即可

使数组平衡的最少移出数目

给你一个整数数组 nums 和一个整数 k。

如果一个数组的最大元素的值至多是其最小元素的 k 倍，则该数组被称为是平衡的。

你可以从 nums 中移除任意数量的元素，但不能使其变为空数组。

返回为了使剩余数组平衡，需要移除的元素的最小数量。

1

1. 能看出是滑动窗口吗？问题转化为：求一个窗口，使得其最小元素最小值*k >= 最大值！

不定长 + 越短越合法

最短美丽字串

给二进制字符串s和正整数k，找到满足以下条件的子字符串：

子字符串中1的个数恰好是k（即美丽子字符串）；

该子字符串是所有美丽子字符串中最短的；

若有多个最短的，选字典序最小的；若没有美丽子字符串，返回空字符串。

1
2
3
4
5


1. 如何保证最短？ --> 最前端如果有 0，需要继续向后

2. 当达到筛选条件后，需要进一步收缩边界！

3. 字符串字典序直接比较即可

求子数组个数 + 越短越合法

元素乘积小于 k 的子数组数目

给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。

1
2
3


1. 要求连续子数组，发现缩短以后一样符合条件，所以是滑窗的变式

2. 小于当前窗口的都符合，所以要 res += right - left + 1

不间断子数组数目

给你一个下标从 0 开始的整数数组 nums 。nums 的一个子数组如果满足以下条件，那么它是 不间断 的：

i，i + 1 ，…，j 表示子数组中的下标。对于所有满足 i <= i1, i2 <= j 的下标对，都有 0 <= |nums[i1] - nums[i2]| <= 2 。

请你返回 不间断 子数组的总数目。

子数组是一个数组中一段连续非空的元素序列。

1
2
3


1. 用哈希表维护的判断条件！

2. 还是滑窗的思路，依次控制窗口枚举

求子数组个数 + 越长越合法

包含所有三种字符的子字符串数目

给你一个字符串 s ，它只包含三种字符 a, b 和 c 。

请你返回 a，b 和 c 都至少出现过一次的子字符串数目。

1
2
3
4
5


1. 先找至少出现过一次的情况，想到滑动窗口

2. “至少”意味着只能找最短，所以在更新时要将更长的字符串加上，即 res += left

3. 注意：不能写 if len(cnt) < 3: continue 的判断，边界条件要考虑清楚！

恰好型滑窗

要计算有多少个元素和恰好等于 k 的子数组，可以把问题变成：

计算有多少个元素和 ≥k 的子数组。

计算有多少个元素和 >k，也就是 ≥k+1 的子数组。

因为滑动窗口比较难解决“等于”问题，故尝试转化成不等于问题，即越…越合法

答案就是元素和 ≥k 的子数组个数，减去元素和 ≥k+1 的子数组个数。

也可以把问题变成 ≤k 减去 ≤k−1，即两个「至多」。可根据题目选择合适的变形方式。

和相同的二元子数组

给你一个二元数组 nums ，和一个整数 goal ，请你统计并返回有多少个和为 goal 的非空子数组。

子数组 是数组的一段连续部分。

1
2
3


1. 求区间和，可以用前缀和，但是这里考虑滑窗

2. 转为求 res1 - res2，需要用两个 left1，2、sum1，2 来分别求边界

前缀和

适用情景：

连续子数组求和问题，数组不单调时，考虑用前缀和
任意子数组都是一个前缀去掉前缀后的结果。所以任意子数组的和，都可以表示为两个前缀和的差。
定义 s[0] = 0 ，提高适用性

初始化模板：

1
2
3


s = [0] * (len(nums) + 1)
        for i, x in enumerate(nums):
            s[i + 1] = s[i] + x

例题

和为 K 的子数组

1
2
3
4
5
6
7


1. 连续数组求和，考虑前缀和

2. 继续分析，发现要求 s[i] + s[j] == k，暴力写法要 O(n^2)，考虑转换

3. 想到哈希表，空间换时间，遍历一遍后存储到表中，可以直接查询 s[j] - k

4. 注意：哈希表的遍历顺序和数组顺序要对应！先寻找，再加入哈希表，不能一次性往里添加

最大子数组和

1
2
3
4
5


1. 考虑前缀和

2. 发现边缘条件：需要考虑负数！前缀和求的是区间加法，所以要用当前前缀减去前面的最小前缀（需要维护）

3. 还可以用动态规划

二分

适用场景：

有序数组找指定大小的数

思路：

先确定区间（循环不变量），根据区间来初始化左右指针
明确：左右指针以外是已经确定了大小关系的，接下来要更新的是左右指针以内的数
转化
- 基本做法只能做 >= x
- 遇见 >x，转成 >= x+1，<x 转成 <= x-1 等等
易错点
- 要保证区间 - 条件判断的连贯性，判断条件只要符合区间，就合法，就需要查找
- 建议画图来理解！
- 可以定义函数来复用逻辑

示例：

 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


def binary_search(nums, target):
    left = 0
    right = len(nums) - 1  # 闭区间初始化
    while left <= right:   # 区间非空时循环
        mid = (left + right) // 2  # 避免溢出可用 left + (right - left) // 2
        if nums[mid] == target:
            return mid  # 找到目标，返回索引
        elif nums[mid] > target:
            right = mid - 1  # 目标在左半区间，收缩右边界
        else:
            left = mid + 1   # 目标在右半区间，收缩左边界
    return -1  # 区间为空，未找到

def find_first_ge(nums, target):
    left = 0
    right = len(nums) - 1
    res = len(nums)  # 默认值（若所有元素都小于target，返回数组长度）
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] >= target:
            res = mid  # 可能是候选答案，继续向左找更小的符合条件的位置
            right = mid - 1
        else:
            left = mid + 1  # 不符合，向右找
    return res

二分查找

查找元素首尾位置

1
2
3
4
5


1. 边界的判断注意，函数 find 的是什么？结果要什么？

2. 找到坐标后，如何排除不可能的答案？--> 直接用左右边界判断即可。

3. 还写错了 while 的更新条件，nums[mid] 而非 mid

搜索插入位置

1

1. 先想清楚要找什么！找第一个大于等于指定数的位置即可！

寻找比目标字母大的最小字母

1
2
3


1. 写习惯了大于等于，怎么变成大于？ --> 改变循环不变量就可以！控制 left 左边为 <= 的就行

2. py 里求 askii 码：ord(char)

两个数组的距离值

给你两个整数数组 arr1 ， arr2 和一个整数 d ，请你返回两个数组之间的 距离值 。

「距离值」定义为符合此距离要求的元素数目：对于元素 arr1[i] ，不存在任何元素 arr2[j] 满足 |arr1[i]-arr2[j]| <= d 。

1
2
3
4
5


1. 怎么找满足距离值的数？ --> 距离先变小后变大 --> 二分

2. 找什么数？ --> 大于等于 target 的第一个数和第一个数的前一个数，这两个数才有可能

3. 优化：二分查找 ≥x−d 的最小的数 y。如果 y 不存在，或者 y>x+d，那么说明 arr 没有在 [x−d,x+d] 中的数，答案加一。

区间内查询数字的频率

请你实现 RangeFreqQuery 类：

RangeFreqQuery(int[] arr) 用下标从 0 开始的整数数组 arr 构造一个类的实例。

int query(int left, int right, int value) 返回子数组 arr[left...right] 中 value 的频率。

1
2
3


1. 暴力会超时……考虑优化

2. 找数字在区间内出现的频率，把问题化约到每个数字，先记录每个数字出现的下标表，然后二分查找在所求区间内，数字的数量。

二分答案

定义：一种通过 “二分枚举可能的答案范围” 来求解优化问题（如最大值最小化、最小值最大化）的算法。

核心目标：在所有可能的答案中，找到满足题目约束条件的最优解（如最大、最小、符合条件的解）。

本质：“构造答案并验证”，将优化问题转化为 “判断某个值是否为可行解” 的判定问题，再通过二分缩小范围。

简而言之，就是不确定上下界，需要自己放缩出边界，然后进行二分查找。可能需要自己编写 check 函数来判断

模板：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution:
    # 计算满足 check(x) == True 的最小整数 x
    def binarySearchMin(self, nums: List[int]) -> int:
        # 二分猜答案：判断 mid 是否满足题目要求
        def check(mid: int) -> bool:
            # TODO

        left =   # 循环不变量：check(left) 恒为 False
        right =   # 循环不变量：check(right) 恒为 True
        while left + 1 < right:  # 开区间不为空
            mid = (left + right) // 2
            if check(mid):  # 说明 check(>= mid 的数) 均为 True
                right = mid  # 接下来在 (left, mid) 中二分答案
            else:  # 说明 check(<= mid 的数) 均为 False
                left = mid  # 接下来在 (mid, right) 中二分答案
        # 循环结束后 left+1 = right
        # 此时 check(left) == False 而 check(left+1) == check(right) == True
        # 所以 right 就是最小的满足 check 的值
        return right

使结果不超过阈值的最小除数

给你一个整数数组 nums 和一个正整数 threshold ，你需要选择一个正整数作为除数，然后将数组里每个数都除以它，并对除法结果求和。

请你找出能够使上述结果小于等于阈值 threshold 的除数中最小的那个。

每个数除以除数后都向上取整，比方说 7/3 = 3 ， 10/2 = 5 。

题目保证一定有解。

1
2
3
4
5


1. 找值，考虑二分

2. 先确定上下边界，可以取 1,max(nums),然后自定义 check 函数判断。

3. python 的向上取整函数 math.ceil()

在 D 天内送达包裹的能力

传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。

传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量（weights）的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。

返回能在 days 天内将传送带上的所有包裹送达的船的最低运载能力。

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


1. 难点在 check 函数的编写！怎么判断是否可以？

2. 其实很简单，注意初始 cnt = 1，每天的货物运输需要模拟过程才不会错！

def helper(load):
    days = 1  # 最少也得花一天
    s = 0
    for x in weights:
        s += x
        if s > load:
            days += 1
            s = x  # 当前包开始新一天
    return days