LeetCode Go · 二分查找（2）

返回题库与筛选 · 收录范围与使用说明

来源与许可

题目版权归 LeetCode；题解来自 Doocs/leetcode，按 CC BY-SA 4.0 共享。补充 Go 代码来自灵茶山艾府、halfrost，保留 MIT 许可及逐题署名。本站提取 Go、调整分类及折叠排版；标注“本站整理”的 Go 解法依据题意与参考思路补写，按 CC BY-SA 4.0 共享。收录日期：2026-10-31；主题源版本：91ef8c241a5e。

本卷 30 题 · 点击题目展开，先独立思考，再查看解法。

497. 非重叠矩形中的随机点

中等1 种解法

标签：水塘抽样、数组、数学、二分查找、有序集合、前缀和、随机化

题目、示例与约束

给定一个由非重叠的轴对齐矩形的数组 rects ，其中 rects[i] = [ai, bi, xi, yi] 表示 (ai, bi) 是第 i 个矩形的左下角点，(xi, yi) 是第 i 个矩形的右上角点。设计一个算法来随机挑选一个被某一矩形覆盖的整数点。矩形周长上的点也算做是被矩形覆盖。所有满足要求的点必须等概率被返回。

在给定的矩形覆盖的空间内的任何整数点都有可能被返回。

请注意 ，整数点是具有整数坐标的点。

实现 Solution 类:

• Solution(int[][] rects) 用给定的矩形数组 rects 初始化对象。
• int[] pick() 返回一个随机的整数点 [u, v] 在给定的矩形所覆盖的空间内。

 

示例 1：

输入: 
["Solution", "pick", "pick", "pick", "pick", "pick"]
[[[[-2, -2, 1, 1], [2, 2, 4, 6]]], [], [], [], [], []]
输出: 
[null, [1, -2], [1, -1], [-1, -2], [-2, -2], [0, 0]]

解释：
Solution solution = new Solution([[-2, -2, 1, 1], [2, 2, 4, 6]]);
solution.pick(); // 返回 [1, -2]
solution.pick(); // 返回 [1, -1]
solution.pick(); // 返回 [-1, -2]
solution.pick(); // 返回 [-2, -2]
solution.pick(); // 返回 [0, 0]

 

提示：

• 1 <= rects.length <= 100
• rects[i].length == 4
• -109 <= ai < xi <= 109
• -109 <= bi < yi <= 109
• xi - ai <= 2000
• yi - bi <= 2000
• 所有的矩形不重叠。
• pick 最多被调用 104 次。

方法一：前缀和 + 二分查找 · Go 实现

思考

在若干不重叠矩形的整数点上均匀采样。若先等概率选矩形再选点，小矩形被抽中的机会过大。

按格子数做前缀和，在 $[1,\mathit{\text{total}}]$ 上均匀取 $v$，二分定位矩形，再在该矩形内均匀取整点。

前缀和把「按面积加权」变成一次二分。矩形不重叠保证每个整点只属于一个矩形。

将矩形面积求前缀和 $s$，然后随机获取到一个面积 $v$，利用二分查找定位到是哪个矩形，然后继续随机获取该矩形的其中一个整数点坐标即可。

type Solution struct {
	s     []int
	rects [][]int
}

func Constructor(rects [][]int) Solution {
	n := len(rects)
	s := make([]int, n+1)
	for i, v := range rects {
		s[i+1] = s[i] + (v[2]-v[0]+1)*(v[3]-v[1]+1)
	}
	return Solution{s, rects}
}

func (this *Solution) Pick() []int {
	n := len(this.rects)
	v := 1 + rand.Intn(this.s[len(this.s)-1])
	left, right := 0, n
	for left < right {
		mid := (left + right) >> 1
		if this.s[mid] >= v {
			right = mid
		} else {
			left = mid + 1
		}
	}
	rect := this.rects[left-1]
	x, y := rect[0]+rand.Intn(rect[2]-rect[0]+1), rect[1]+rand.Intn(rect[3]-rect[1]+1)
	return []int{x, y}
}

力扣原题 · Doocs 题解来源

528. 按权重随机选择

中等1 种解法

标签：数组、数学、二分查找、前缀和、随机化

题目、示例与约束

给你一个 下标从 0 开始 的正整数数组 w ，其中 w[i] 代表第 i 个下标的权重。

请你实现一个函数 pickIndex ，它可以 随机地 从范围 [0, w.length - 1] 内（含 0 和 w.length - 1）选出并返回一个下标。选取下标 i 的 概率 为 w[i] / sum(w) 。

• 例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3) = 0.25 （即，25%），而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。

 

示例 1：

输入：
["Solution","pickIndex"]
[[[1]],[]]
输出：
[null,0]
解释：
Solution solution = new Solution([1]);
solution.pickIndex(); // 返回 0，因为数组中只有一个元素，所以唯一的选择是返回下标 0。

示例 2：

输入：
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
输出：
[null,1,1,1,1,0]
解释：
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // 返回 1，返回下标 1，返回该下标概率为 3/4 。
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 0，返回下标 0，返回该下标概率为 1/4 。

由于这是一个随机问题，允许多个答案，因此下列输出都可以被认为是正确的:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
诸若此类。

 

提示：

• 1 <= w.length <= 104
• 1 <= w[i] <= 105
• pickIndex 将被调用不超过 104 次

方法一 · Go 实现

思考

按权重 $w[i]$ 做离散抽样，调用次数很多，不能每次线性扫描累加。

前缀和把权重变成数轴上的区间，均匀随机一个 $[1,S]$ 中的整数后再二分定位所属区间。构造 $O(n)$，单次抽取 $O(\log n)$。下标要减一，因为前缀和数组在开头垫了 $0$。

type Solution struct {
	s []int
}

func Constructor(w []int) Solution {
	n := len(w)
	s := make([]int, n+1)
	for i := 0; i < n; i++ {
		s[i+1] = s[i] + w[i]
	}
	return Solution{s}
}

func (this *Solution) PickIndex() int {
	n := len(this.s)
	x := 1 + rand.Intn(this.s[n-1])
	left, right := 1, n-1
	for left < right {
		mid := (left + right) >> 1
		if this.s[mid] >= x {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return left - 1
}

/**
 * Your Solution object will be instantiated and called as such:
 * obj := Constructor(w);
 * param_1 := obj.PickIndex();
 */

力扣原题 · Doocs 题解来源

532. 数组中的 k-diff 数对

中等1 种解法

标签：数组、哈希表、双指针、二分查找、排序

题目、示例与约束

给你一个整数数组 nums 和一个整数 k，请你在数组中找出 不同的 k-diff 数对，并返回不同的 k-diff 数对 的数目。

k-diff 数对定义为一个整数对 (nums[i], nums[j]) ，并满足下述全部条件：

• 0 <= i, j < nums.length
• i != j
• |nums[i] - nums[j]| == k

注意，|val| 表示 val 的绝对值。

 

示例 1：

输入：nums = [3, 1, 4, 1, 5], k = 2
输出：2
解释：数组中有两个 2-diff 数对, (1, 3) 和 (3, 5)。
尽管数组中有两个 1 ，但我们只应返回不同的数对的数量。

示例 2：

输入：nums = [1, 2, 3, 4, 5], k = 1
输出：4
解释：数组中有四个 1-diff 数对, (1, 2), (2, 3), (3, 4) 和 (4, 5) 。

示例 3：

输入：nums = [1, 3, 1, 5, 4], k = 0
输出：1
解释：数组中只有一个 0-diff 数对，(1, 1) 。

 

提示：

• 1 <= nums.length <= 104
• -107 <= nums[i] <= 107
• 0 <= k <= 107

方法一：哈希表 · Go 实现

思考

统计满足 $|a-b|=k$ 的不同数对（值不同，与下标无关）。枚举所有下标对是 $O(n^2)$。

一边遍历一边把已见过的值放入集合：若 $x-k$ 或 $x+k$ 已出现，则把较小元加入答案集合，避免同一数对重复计数。 $k$ 固定，查找是期望常数。

由于 $k$ 是一个定值，我们可以用一个哈希表 $\mathit{\text{ans}}$ 记录数对的较小值，就能够确定较大的值。最后返回 $\mathit{\text{ans}}$ 的大小作为答案。

遍历数组 $\mathit{\text{nums}}$，当前遍历到的数 $x$，我们用哈希表 $\mathit{\text{vis}}$ 记录此前遍历到的所有数字。若 $x-k$ 在 $\mathit{\text{vis}}$ 中，则将 $x-k$ 添加至 $\mathit{\text{ans}}$；若 $x+k$ 在 $\mathit{\text{vis}}$ 中，则将 $x$ 添加至 $\mathit{\text{ans}}$。然后我们将 $x$ 添加至 $\mathit{\text{vis}}$。继续遍历数组 $\mathit{\text{nums}}$ 直至遍历结束。

最后返回 $\mathit{\text{ans}}$ 的大小作为答案。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $\mathit{\text{nums}}$ 的长度。

func findPairs(nums []int, k int) int {
	ans := make(map[int]struct{})
	vis := make(map[int]struct{})

	for _, x := range nums {
		if _, ok := vis[x-k]; ok {
			ans[x-k] = struct{}{}
		}
		if _, ok := vis[x+k]; ok {
			ans[x] = struct{}{}
		}
		vis[x] = struct{}{}
	}
	return len(ans)
}

力扣原题 · Doocs 题解来源

540. 有序数组中的单一元素

中等1 种解法

标签：数组、二分查找

题目、示例与约束

给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。

请你找出并返回只出现一次的那个数。

你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

 

示例 1:

输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2

示例 2:

输入: nums =  [3,3,7,7,10,11,11]
输出: 10

 

提示:

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 105

方法一：二分查找 · Go 实现

思考

有序数组中只有一个元素出现一次，其余成对相邻。要求 $O(\log n)$，不能整表扫描。

成对元素占据偶数-奇数下标。若 $mid$ 与 $mid\oplus 1$ 仍是一对，则单独元素在右半，否则在左半（含 $mid$）。二分缩小到单独元素。按位异或避免讨论 $mid$ 奇偶分支。

题目给定的数组 $\mathit{\text{nums}}$ 是有序的，且要求在 $\mathit{\text{O}}(\log n)$ 时间找到只出现一次的元素，因此我们考虑使用二分查找解决。

我们定义二分查找的左边界 $\mathit{\text{l}}=0$，右边界 $\mathit{\text{r}}=n-1$，其中 $n$ 是数组的长度。

在每一步中，我们取中间位置 $\mathit{\text{mid}}=(l+r)/2$，如果下标 $\mathit{\text{mid}}$ 为偶数，那么我们应该将 $\mathit{\text{nums}}[\mathit{\text{mid}}]$ 与 $\mathit{\text{nums}}[\mathit{\text{mid}}+1]$ 进行比较；如果下标 $\mathit{\text{mid}}$ 为奇数，那么我们应该将 $\mathit{\text{nums}}[\mathit{\text{mid}}]$ 与 $\mathit{\text{nums}}[\mathit{\text{mid}}-1]$ 进行比较。因此，我们可以统一将 $\mathit{\text{nums}}[\mathit{\text{mid}}]$ 与 $\mathit{\text{nums}}[\mathit{\text{mid}}\oplus 1]$ 进行比较，其中 $\oplus$ 表示异或运算。

如果 $\mathit{\text{nums}}[\mathit{\text{mid}}]\ne \mathit{\text{nums}}[\mathit{\text{mid}}\oplus 1]$，那么答案在 $[\mathit{\text{l}},\mathit{\text{mid}}]$ 中，我们令 $\mathit{\text{r}}=\mathit{\text{mid}}$；如果 $\mathit{\text{nums}}[\mathit{\text{mid}}]=\mathit{\text{nums}}[\mathit{\text{mid}}\oplus 1]$，那么答案在 $[\mathit{\text{mid}}+1,\mathit{\text{r}}]$ 中，我们令 $\mathit{\text{l}}=\mathit{\text{mid}}+1$。继续二分查找，直到 $\mathit{\text{l}}=\mathit{\text{r}}$，此时 $\mathit{\text{nums}}[\mathit{\text{l}}]$ 即为只出现一次的元素。

时间复杂度 $\mathit{\text{O}}(\log n)$，其中 $n$ 是数组 $\mathit{\text{nums}}$ 的长度。空间复杂度 $\mathit{\text{O}}(1)$。

func singleNonDuplicate(nums []int) int {
	l, r := 0, len(nums)-1
	for l < r {
		mid := (l + r) >> 1
		if nums[mid] != nums[mid^1] {
			r = mid
		} else {
			l = mid + 1
		}
	}
	return nums[l]
}

力扣原题 · Doocs 题解来源

633. 平方数之和

中等2 种解法

标签：数学、双指针、二分查找

题目、示例与约束

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。

 

示例 1：

输入：c = 5
输出：true
解释：1 * 1 + 2 * 2 = 5

示例 2：

输入：c = 3
输出：false

 

提示：

• 0 <= c <= 231 - 1

方法一：数学 + 双指针 · Go 实现

思考

判断是否存在 $a^2+b^2=c$。对每个 $a$ 再开方检查 $c-a^2$ 需要多次开方。 $c$ 可达 $2^{31}-1$，从 $0$ 与 $\sqrt{c}$ 两端相向移动即可。

和偏小则增大 $a$，偏大则减小 $b$。平方关于指针单调，不会漏解。

我们可以使用双指针的方法来解决这个问题，定义两个指针 $a$ 和 $b$，分别指向 $0$ 和 $\sqrt{c}$。在每一步中，我们会计算 $s=a^2+b^2$ 的值，然后比较 $s$ 与 $c$ 的大小。如果 $s=c$，我们就找到了两个整数 $a$ 和 $b$，使得 $a^2+b^2=c$。如果 $s<c$，我们将 $a$ 的值增加 $1$，如果 $s>c$，我们将 $b$ 的值减小 $1$。我们不断进行这个过程直到找到答案，或者 $a$ 的值大于 $b$ 的值，返回 false。

时间复杂度 $O(\sqrt{c})$，其中 $c$ 是给定的非负整数。空间复杂度 $O(1)$。

func judgeSquareSum(c int) bool {
	a, b := 0, int(math.Sqrt(float64(c)))
	for a <= b {
		s := a*a + b*b
		if s == c {
			return true
		}
		if s < c {
			a++
		} else {
			b--
		}
	}
	return false
}

方法二：数学 · Go 实现

思考

双指针是 $O(\sqrt{c})$ 的搜索。数论上， $c$ 能写成两平方和当且仅当所有形如 $4k+3$ 的素因子幂次为偶数。质因数分解后按此判定，复杂度同阶但不再枚举 $(a,b)$。

这个问题实际上是关于一个数能否表示为两个平方数之和的条件。这个定理可以追溯到费马（Fermat）和欧拉（Euler），它在数论中是一个经典结果。

具体来说，这个定理可以表述为：

一个正整数 ( n ) 能表示为两个平方数之和的充要条件是：( n ) 的所有形如 ( 4k + 3 ) 的素数因子的幂次均为偶数。

这意味着，如果我们将 $n$ 分解成素数因子乘积的形式，即 $n=p_1^{e_1}{p}_2^{e_2}\cdots p_k^{e_k}$，其中 $p_i$ 是素数且 $e_i$ 是它们对应的幂次，那么 $n$ 可以表示为两个平方数之和，当且仅当所有 $4k+3$ 形式的素数因子 $p_i$ 的幂次 $e_i$ 都是偶数。

更正式地，假设 $p_i$ 是形如 $4k+3$ 的素数，则对于每一个这样的 $p_i$，要求 $e_i$ 是偶数。

例如：

• 数字 $13$ 是素数，且 $13\equiv 1(\mathrm{mod}4)$，因此它可以表示为两个平方数之和，即 $13=2^2+3^2$。
• 数字 $21$ 分解为 $3\times 7$，其中 $3$ 和 $7$ 都是形如 $4k+3$ 的素数因子，并且它们的幂次都是 $1$（奇数），因此 $21$ 不能表示为两个平方数之和。

总结起来，这个定理在数论中非常重要，用于判断一个数是否可以表示为两个平方数之和。

时间复杂度 $O(\sqrt{c})$，其中 $c$ 是给定的非负整数。空间复杂度 $O(1)$。

func judgeSquareSum(c int) bool {
	n := int(math.Sqrt(float64(c)))
	for i := 2; i <= n; i++ {
		if c%i == 0 {
			exp := 0
			for c%i == 0 {
				c /= i
				exp++
			}
			if i%4 == 3 && exp%2 != 0 {
				return false
			}
		}
	}
	return c%4 != 3
}

力扣原题 · Doocs 题解来源

644. 子数组最大平均数 II 🔒

困难1 种解法

标签：数组、二分查找、前缀和

题目、示例与约束

给你一个包含 n 个整数的数组 nums ，和一个整数 k 。

请你找出 长度大于等于 k 且含最大平均值的连续子数组。并输出这个最大平均值。任何计算误差小于 10-5 的结果都将被视为正确答案。

 

示例 1：

输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75000
解释：
- 当长度为 4 的时候，连续子数组平均值分别为 [0.5, 12.75, 10.5] ，其中最大平均值是 12.75 。
- 当长度为 5 的时候，连续子数组平均值分别为 [10.4, 10.8] ，其中最大平均值是 10.8 。
- 当长度为 6 的时候，连续子数组平均值分别为 [9.16667] ，其中最大平均值是 9.16667 。
当取长度为 4 的子数组（即，子数组 [12, -5, -6, 50]）的时候，可以得到最大的连续子数组平均值 12.75 ，所以返回 12.75 。
根据题目要求，无需考虑长度小于 4 的子数组。

示例 2：

输入：nums = [5], k = 1
输出：5.00000

 

提示：

• n == nums.length
• 1 <= k <= n <= 104
• -104 <= nums[i] <= 104

方法一：二分查找 · Go 实现

思考

长度至少为 $k$ 的子数组最大平均值，枚举区间是平方级， $n$ 可达 ${10}^4$。平均值对阈值单调：存在均值 $\ge v$ 则答案不小于 $v$。

对 $v$ 二分，把每个元素减 $v$ 后问是否存在长度 $\ge k$ 的非负和子数组。用前缀和减去此前最短合法前缀的最小值即可判定。

我们注意到，如果一个长度大于等于 $k$ 的子数组的平均值为 $v$，那么最大平均数一定大于等于 $v$，否则最大平均数一定小于 $v$。因此，我们可以使用二分查找的方法找出最大平均数。

我们考虑二分查找的左右边界分别是什么？左边界 $l$ 一定是数组中的最小值，而右边界 $r$ 则是数组中的最大值。接下来，我们二分查找中点 $mid$，判断是否存在长度大于等于 $k$ 的子数组的平均值大于等于 $mid$。如果存在，那么我们就将左边界 $l$ 更新为 $mid$，否则我们就将右边界 $r$ 更新为 $mid$。当左边界和右边界的差小于一个极小的非负数，即 $r-l<ϵ$ 时，我们就可以得到最大平均数，其中 $ϵ$ 表示一个极小的正数，可以取 ${10}^{-5}$。

问题的关键在于如何判断一个长度大于等于 $k$ 的子数组的平均值是否大于等于 $v$。

我们假设在数组 $nums$ 中，存在一个长度为 $j$ 的子数组，元素分别为 $a_1,a_2,\cdots ,a_j$，满足其平均值大于等于 $v$，即：

$$\frac{a_1+a_2+\cdots +a_j}{j}\ge v$$

那么：

$$a_1+a_2+\cdots +a_j\ge v\times j$$

即：

$$(a_1-v)+(a_2-v)+\cdots +(a_j-v)\ge 0$$

可以发现，如果我们将数组 $nums$ 中的每个元素都减去 $v$，那么原问题就转换成了一个求长度大于等于 $k$ 的子数组的元素和是否大于等于 $0$ 的问题。我们可以使用滑动窗口来解决这个问题。

我们先计算得到数组前 $k$ 个元素与 $v$ 的差值之和 $s$，如果 $s\ge 0$，那么就说明存在长度大于等于 $k$ 的子数组的元素和大于等于 $0$。

否则，我们继续往后遍历元素 $nums[j]$，假设当前前 $j$ 项元素与 $v$ 的差值之和为 $s_j$，那么我们可以维护在 $[0,..j-k]$ 范围内元素的前缀和与 $v$ 的差值之和的最小值 $mi$，如果存在 $s_j\ge mi$，那么就说明存在长度大于等于 $k$ 的子数组的元素和大于等于 $0$，返回 $true$。

否则，我们继续往后遍历元素 $nums[j]$，直到遍历完整个数组。

时间复杂度 $O(n\times \log M)$，其中 $n$ 和 $M$ 分别是数组 $nums$ 的长度以及数组中的最大值和最小值的差值。空间复杂度 $O(1)$。

func findMaxAverage(nums []int, k int) float64 {
	eps := 1e-5
	l := float64(slices.Min(nums))
	r := float64(slices.Max(nums))
	check := func(v float64) bool {
		s := 0.0
		for _, x := range nums[:k] {
			s += float64(x) - v
		}
		if s >= 0 {
			return true
		}
		t := 0.0
		mi := 0.0
		for i := k; i < len(nums); i++ {
			s += float64(nums[i]) - v
			t += float64(nums[i-k]) - v
			mi = math.Min(mi, t)
			if s >= mi {
				return true
			}
		}
		return false
	}
	for r-l >= eps {
		mid := (l + r) / 2
		if check(mid) {
			l = mid
		} else {
			r = mid
		}
	}
	return l
}

力扣原题 · Doocs 题解来源

658. 找到 K 个最接近的元素

中等3 种解法

标签：数组、双指针、二分查找、排序、滑动窗口、堆（优先队列）

题目、示例与约束

给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。

整数 a 比整数 b 更接近 x 需要满足：

• |a - x| < |b - x| 或者
• |a - x| == |b - x| 且 a < b

 

示例 1：

输入：arr = [1,2,3,4,5], k = 4, x = 3
输出：[1,2,3,4]

示例 2：

输入：arr = [1,1,2,3,4,5], k = 4, x = -1
输出：[1,1,2,3]

 

提示：

• 1 <= k <= arr.length
• 1 <= arr.length <= 104
• arr 按 升序 排列
• -104 <= arr[i], x <= 104

方法一：排序 · Go 实现

思考

有序数组中找与 $x$ 最接近的 $k$ 个数，结果仍要有序。按距离排序再取前 $k$ 个即可，代价是 $O(n\log n)$。

以 $|v-x|$ 为键排序，截取前 $k$ 个后再按值排序。

将 $arr$ 中的所有元素按照与 $x$ 的距离从小到大进行排列。取前 $k$ 个元素排序后返回。

时间复杂度 $O(nlogn)$。

func findClosestElements(arr []int, k int, x int) []int {
	sort.Slice(arr, func(i, j int) bool {
		v := abs(arr[i]-x) - abs(arr[j]-x)
		if v == 0 {
			return arr[i] < arr[j]
		}
		return v < 0
	})
	ans := arr[:k]
	sort.Ints(ans)
	return ans
}

func abs(x int) int {
	if x >= 0 {
		return x
	}
	return -x
}

方法二：双指针 · Go 实现

思考

答案必是一段连续子数组。两端指针按距离把更远的一侧收进来，直到长度恰为 $k$，线性即可，且结果已有序。

直觉上，有序数组 $arr$ 最靠近 $x$ 的 $k$ 个数必然是一段连续的子数组。

我们可以声明头尾指针，记为 $l$ 和 $r$，然后根据 $x-arr[l]$ 与 $arr[r-1]-x$ 的大小比较结果缩小范围，直到 $r-l=k$。

时间复杂度 $O(n)$。

func findClosestElements(arr []int, k int, x int) []int {
	l, r := 0, len(arr)
	for r-l > k {
		if x-arr[l] <= arr[r-1]-x {
			r--
		} else {
			l++
		}
	}
	return arr[l:r]
}

方法三：二分查找 · Go 实现

思考

双指针是线性。窗口左端在 $[0,n-k]$ 上单调：比较 $x-arr[mid]$ 与 $arr[mid+k]-x$ 即可二分左端，降到 $O(\log n)$。

在方法二的基础上，我们更进一步，查找大小为 $k$ 的窗口的左边界。

时间复杂度 $O(logn)$。

func findClosestElements(arr []int, k int, x int) []int {
	left, right := 0, len(arr)-k
	for left < right {
		mid := (left + right) >> 1
		if x-arr[mid] <= arr[mid+k]-x {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return arr[left : left+k]
}

力扣原题 · Doocs 题解来源

668. 乘法表中第k小的数

困难1 种解法

标签：数学、二分查找

题目、示例与约束

几乎每一个人都用 乘法表。但是你能在乘法表中快速找到第 k 小的数字吗？

乘法表是大小为 m x n 的一个整数矩阵，其中 mat[i][j] == i * j（下标从 1 开始）。

给你三个整数 m、n 和 k，请你在大小为 m x n 的乘法表中，找出并返回第 k 小的数字。

 

示例 1：

输入：m = 3, n = 3, k = 5
输出：3
解释：第 5 小的数字是 3 。

示例 2：

输入：m = 2, n = 3, k = 6
输出：6
解释：第 6 小的数字是 6 。

 

提示：

• 1 <= m, n <= 3 * 104
• 1 <= k <= m * n

方法一：二分查找 · Go 实现

思考

$m\times n$ 乘法表中第 $k$ 小。表最大 $3\cdot {10}^4$ 边，物化排序不可行。

对值 $x$ 二分：第 $i$ 行不超过 $x$ 的个数为 $min(\lfloor x/i\rfloor ,n)$。累加后与 $k$ 比较，找最小满足 $\mathit{\text{cnt}}\ge k$ 的 $x$。

题目可以转换为，求有多少个数不超过 x。对于每一行 i，所有数都是 i 的倍数，不超过 x 的个数有 x / i 个。

二分枚举 x，累加每一行不超过 x 的个数，得到 cnt。找到 cnt >= k 的最小 x。

func findKthNumber(m int, n int, k int) int {
	left, right := 1, m*n
	for left < right {
		mid := (left + right) >> 1
		cnt := 0
		for i := 1; i <= m; i++ {
			cnt += min(mid/i, n)
		}
		if cnt >= k {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return left
}

力扣原题 · Doocs 题解来源

702. 搜索长度未知的有序数组 🔒

中等1 种解法

标签：数组、二分查找、交互

题目、示例与约束

这是一个交互问题。

您有一个升序整数数组，其长度未知。您没有访问数组的权限，但是可以使用 ArrayReader 接口访问它。你可以调用 ArrayReader.get(i):

• 返回数组第ith个索引(0-indexed)处的值(即 secret[i])，或者

• 如果 i  超出了数组的边界，则返回 231 - 1

你也会得到一个整数 target。

如果存在secret[k] == target，请返回索引 k 的值；否则返回 -1

你必须写一个时间复杂度为 O(log n) 的算法。

 

示例 1：

输入: secret = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 存在在 nums 中，下标为 4

示例 2：

输入: secret = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不在数组中所以返回 -1

 

提示：

• 1 <= secret.length <= 104
• -104 <= secret[i], target <= 104
• secret 严格递增

方法一：二分查找 · Go 实现

思考

数组有序但长度未知，只能通过接口按下落标取值，越界返回哨兵。线性从下标 $0$ 扫到目标，调用次数与目标位置成正比，在长度为 ${10}^4$ 时偏慢，也未利用有序性。

长度未知时无法直接对全区间二分。若先把右端点按倍增扩大，直到取值不小于目标，则目标必落在刚刚跨过的那一段，长度与目标位置同阶。

为此先令 $r=1$ 并不断左移一位，再在 $[r/2,r]$ 上做二分。查找区间长度为 $O(M)$，总调用次数 $O(\log M)$，其中 $M$ 为目标下标。

我们先定义一个指针 $r=1$，每一次判断 $r$ 处的值是否小于目标值，如果小于目标值，我们将 $r$ 乘以 $2$，即左移一位，直到 $r$ 处的值大于等于目标值。此时，我们可以确定目标值在 $[r/2,r]$ 的区间内。

接下来，我们定义一个指针 $l=r/2$，然后我们可以使用二分查找的方法在 $[l,r]$ 的区间内查找目标值的位置。

时间复杂度 $O(\log M)$，其中 $M$ 为目标值的位置。空间复杂度 $O(1)$。

/**
 * // This is the ArrayReader's API interface.
 * // You should not implement it, or speculate about its implementation
 * type ArrayReader struct {
 * }
 *
 * func (this *ArrayReader) get(index int) int {}
 */

func search(reader ArrayReader, target int) int {
	r := 1
	for reader.get(r) < target {
		r <<= 1
	}
	l := r >> 1
	for l < r {
		mid := (l + r) >> 1
		if reader.get(mid) >= target {
			r = mid
		} else {
			l = mid + 1
		}
	}
	if reader.get(l) == target {
		return l
	}
	return -1
}

力扣原题 · Doocs 题解来源

704. 二分查找

简单1 种解法

标签：数组、二分查找

题目、示例与约束

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果 target 存在返回下标，否则返回 -1。

你必须编写一个具有 O(log n) 时间复杂度的算法。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

 

提示：

1. 你可以假设 nums 中的所有元素是不重复的。
2. n 将在 [1, 10000]之间。
3. nums 的每个元素都将在 [-9999, 9999]之间。

方法一：二分查找 · Go 实现

思考

在升序且无重复的数组中查找 $\mathit{\text{target}}$。 $n\le {10}^4$，线性扫描可以通过，但有序数组上每次比较都能丢掉一半候选。

取中点后，若 $\mathit{\text{nums}}[\mathit{\text{mid}}]\ge \mathit{\text{target}}$，答案不会在右侧，将右端收拢到 $\mathit{\text{mid}}$；否则答案只可能在 $\mathit{\text{mid}}$ 右侧，左端移到 $\mathit{\text{mid}}+1$。

循环至 $l=r$ 时落在第一个不小于目标的位置，再与目标比较即可区分命中与缺失。时间 $O(\log n)$，额外空间 $O(1)$。

我们定义二分查找的左边界 $l=0$，右边界 $r=n-1$。

每一次循环，我们计算中间位置 $\mathit{\text{mid}}=(l+r)/2$，然后比较 $\mathit{\text{nums}}[\mathit{\text{mid}}]$ 和 $\mathit{\text{target}}$ 的大小。

• 如果 $\mathit{\text{nums}}[\mathit{\text{mid}}]\ge \mathit{\text{target}}$，说明 $\mathit{\text{target}}$ 在左半部分，我们将右边界 $r$ 移动到 $\mathit{\text{mid}}$；
• 否则，说明 $\mathit{\text{target}}$ 在右半部分，我们将左边界 $l$ 移动到 $\mathit{\text{mid}}+1$。

循环结束的条件是 $l<r$，此时 $\mathit{\text{nums}}[l]$ 就是我们要找的目标值，如果 $\mathit{\text{nums}}[l]=\mathit{\text{target}}$，返回 $l$，否则返回 $-1$。

时间复杂度 $O(\log n)$，其中 $n$ 是数组 $\mathit{\text{nums}}$ 的长度。空间复杂度 $O(1)$。

func search(nums []int, target int) int {
	l, r := 0, len(nums)-1
	for l < r {
		mid := (l + r) >> 1
		if nums[mid] >= target {
			r = mid
		} else {
			l = mid + 1
		}
	}
	if nums[l] == target {
		return l
	}
	return -1
}

力扣原题 · Doocs 题解来源

710. 黑名单中的随机数

困难1 种解法

标签：数组、哈希表、数学、二分查找、排序、随机化

题目、示例与约束

给定一个整数 n 和一个 无重复 黑名单整数数组 blacklist 。设计一种算法，从 [0, n - 1] 范围内的任意整数中选取一个 未加入 黑名单 blacklist 的整数。任何在上述范围内且不在黑名单 blacklist 中的整数都应该有 同等的可能性 被返回。

优化你的算法，使它最小化调用语言 内置 随机函数的次数。

实现 Solution 类:

• Solution(int n, int[] blacklist) 初始化整数 n 和被加入黑名单 blacklist 的整数
• int pick() 返回一个范围为 [0, n - 1] 且不在黑名单 blacklist 中的随机整数

 

示例 1：

输入
["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"]
[[7, [2, 3, 5]], [], [], [], [], [], [], []]
输出
[null, 0, 4, 1, 6, 1, 0, 4]

解释
Solution solution = new Solution(7, [2, 3, 5]);
solution.pick(); // 返回0，任何[0,1,4,6]的整数都可以。注意，对于每一个pick的调用，
                 // 0、1、4和6的返回概率必须相等(即概率为1/4)。
solution.pick(); // 返回 4
solution.pick(); // 返回 1
solution.pick(); // 返回 6
solution.pick(); // 返回 1
solution.pick(); // 返回 0
solution.pick(); // 返回 4

 

提示:

• 1 <= n <= 109
• 0 <= blacklist.length <= min(105, n - 1)
• 0 <= blacklist[i] < n
• blacklist 中所有值都 不同
•  pick 最多被调用 2 * 104 次

方法一：哈希表 · Go 实现

思考

要从 $[0,n)$ 中等概率抽取不在黑名单中的整数， $n$ 很大而黑名单相对较短，每次现场扫描或拒绝采样都可能反复撞上黑名单。

合法整数恰好有 $k=n-|B|$ 个。若能把 $[0,k)$ 中「被拉黑」的位置一一映射到 $[k,n)$ 中的白名单，则只需在 $[0,k)$ 上均匀取数，再按映射替换即可。

预处理时把黑名单放入集合，从 $i=k$ 起跳过黑名单，将每个小于 $k$ 的黑名单值映到下一个可用的大号。 $\mathit{\text{pick}}$ 时取 $x\in [0,k)$，查表得 $d.get(x,x)$。

type Solution struct {
	d map[int]int
	k int
}

func Constructor(n int, blacklist []int) Solution {
	k := n - len(blacklist)
	i := k
	black := map[int]bool{}
	for _, b := range blacklist {
		black[b] = true
	}
	d := map[int]int{}
	for _, b := range blacklist {
		if b < k {
			for black[i] {
				i++
			}
			d[b] = i
			i++
		}
	}
	return Solution{d, k}
}

func (this *Solution) Pick() int {
	x := rand.Intn(this.k)
	if v, ok := this.d[x]; ok {
		return v
	}
	return x
}

/**
 * Your Solution object will be instantiated and called as such:
 * obj := Constructor(n, blacklist);
 * param_1 := obj.Pick();
 */

力扣原题 · Doocs 题解来源

713. 乘积小于 K 的子数组

中等1 种解法

标签：数组、二分查找、前缀和、滑动窗口

题目、示例与约束

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

请你返回 子数组 内所有元素的 乘积严格小于 k 的连续子数组的数目。

 

示例 1：

输入：nums = [10,5,2,6], k = 100
输出：8
解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2]、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。

示例 2：

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

 

提示: 

• 1 <= nums.length <= 3 * 104
• 1 <= nums[i] <= 1000
• 0 <= k <= 106

方法一：双指针 · Go 实现

思考

统计乘积严格小于 $k$ 的连续子数组个数。数组长度可达 $3\times {10}^4$，枚举左右端点再求积为 $O(n^2)$，偏紧。

元素均为正整数，窗口乘积随右端扩张而单调不减。一旦乘积达到 $k$，必须右移左端才能恢复合法，因此每个端点至多移动一次。

维护乘积 $p$ 与左端 $l$：右端纳入 $x$ 后，若 $p\ge k$ 则不断除掉 $\mathit{\text{nums}}[l]$。此时以 $r$ 结尾的合法子数组个数为 $r-l+1$。一遍扫描即可。

我们可以用双指针维护一个滑动窗口，窗口内所有元素的乘积小于 $k$。

定义两个指针 $l$ 和 $r$ 分别指向滑动窗口的左右边界，初始时 $l=r=0$。我们用一个变量 $p$ 记录窗口内所有元素的乘积，初始时 $p=1$。

每次，我们将 $r$ 右移一位，将 $r$ 指向的元素 $x$ 加入窗口，更新 $p=p\times x$。然后，如果 $p\ge k$，我们循环地将 $l$ 右移一位，并更新 $p=p÷\text{nums}[l]$，直到 $p<k$ 或者 $l>r$ 为止。这样，以 $r$ 结尾的、乘积小于 $k$ 的连续子数组的个数即为 $r-l+1$。然后我们将答案加上这个数量，并继续移动 $r$，直到 $r$ 到达数组的末尾。

时间复杂度 $O(n)$，其中 $n$ 为数组的长度。空间复杂度 $O(1)$。

func numSubarrayProductLessThanK(nums []int, k int) (ans int) {
    l, p := 0, 1
    for r, x := range nums {
        p *= x
        for l <= r && p >= k {
            p /= nums[l]
            l++
        }
        ans += r - l + 1
    }
    return
}

力扣原题 · Doocs 题解来源

719. 找出第 K 小的数对距离

困难1 种解法

标签：数组、双指针、二分查找、排序

题目、示例与约束

数对 (a,b) 由整数 a 和 b 组成，其数对距离定义为 a 和 b 的绝对差值。

给你一个整数数组 nums 和一个整数 k ，数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length 。返回 所有数对距离中 第 k 小的数对距离。

 

示例 1：

输入：nums = [1,3,1], k = 1
输出：0
解释：数对和对应的距离如下：
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
距离第 1 小的数对是 (1,1) ，距离为 0 。

示例 2：

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

示例 3：

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

 

提示：

• n == nums.length
• 2 <= n <= 104
• 0 <= nums[i] <= 106
• 1 <= k <= n * (n - 1) / 2

方法一：排序 + 二分查找 · Go 实现

思考

数对距离的第 $k$ 小。 $n\le {10}^4$，枚举全部 $O(n^2)$ 对再排序超出限制。距离取值在 $[0,max-min]$，具有单调性：不大于 $d$ 的对数随 $d$ 增大而不减。

因此可以对距离二分，判定「有多少对数对距离 $\le d$」。数组排序后，对每个右端点 $b$，左端最小合法值是 $b-d$，用二分找到下界即可在 $O(n\log n)$ 内数完。

在 $[0,nums[-1]-nums[0]]$ 上二分最小的 $d$ 使得计数 $\ge k$，即为第 $k$ 小距离。

先对 $nums$ 数组进行排序，然后在 $[0,nums[n-1]-nums[0]]$ 范围内二分枚举数对距离 $dist$，若 $nums$ 中数对距离小于等于 $dist$ 的数量 $cnt$ 大于等于 $k$，则尝试缩小 $dist$，否则尝试扩大 $dist$。

时间复杂度 $O(nlogn\times logm)$，其中 $n$ 表示 $nums$ 的长度， $m$ 表示 $nums$ 中两个数的最大差值。

func smallestDistancePair(nums []int, k int) int {
	sort.Ints(nums)
	n := len(nums)
	left, right := 0, nums[n-1]-nums[0]
	count := func(dist int) int {
		cnt := 0
		for i, v := range nums {
			target := v - dist
			left, right := 0, i
			for left < right {
				mid := (left + right) >> 1
				if nums[mid] >= target {
					right = mid
				} else {
					left = mid + 1
				}
			}
			cnt += i - left
		}
		return cnt
	}
	for left < right {
		mid := (left + right) >> 1
		if count(mid) >= k {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return left
}

力扣原题 · Doocs 题解来源

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

简单1 种解法

标签：数组、二分查找

题目、示例与约束

给你一个字符数组 letters，该数组按 非递减顺序 排序，以及一个字符 target。letters 里至少有两个不同的字符。

返回 letters 中大于 target 的最小的字符。如果不存在这样的字符，则返回 letters 的第一个字符。

 

示例 1：

输入: letters = ['c', 'f', 'j'], target = 'a'
输出: 'c'
解释：letters 中字典上比 'a' 大的最小字符是 'c'。

示例 2:

输入: letters = ['c','f','j'], target = 'c'
输出: 'f'
解释：letters 中字典顺序上大于 'c' 的最小字符是 'f'。

示例 3:

输入: letters = ['x','x','y','y'], target = 'z'
输出: 'x'
解释：letters 中没有一个字符在字典上大于 'z'，所以我们返回 letters[0]。

 

提示：

• 2 <= letters.length <= 104
• letters[i] 是一个小写字母
• letters 按非递减顺序排序
• letters 最少包含两个不同的字母
• target 是一个小写字母

方法一：二分查找 · Go 实现

思考

在非递减的字母数组中找严格大于 $\mathit{\text{target}}$ 的最小字符，并环形回到开头。 $n\le {10}^4$，有序故可二分。

这是上界查找：第一个大于目标的位置。若该位置等于 $n$，则应取 $letters[0]$，对下标取模即可。

对码值做 $\mathit{\text{bisect\_right}}$，返回 $letters[imodn]$。时间 $O(\log n)$。

由于 $\mathit{\text{letters}}$ 是按照非递减顺序排序的，所以我们可以使用二分查找来找到大于 $\mathit{\text{target}}$ 的最小字符。

我们定义二分查找的左边界 $l=0$，右边界 $r=n$。对于每一次二分查找，我们计算中间位置 $mid=(l+r)/2$，如果 $letters[mid]>\mathit{\text{target}}$，则说明我们需要在左半部分继续查找，即 $r=mid$；否则我们需要在右半部分继续查找，即 $l=mid+1$。

最后我们返回 $letters[lmodn]$ 即可。

时间复杂度 $O(\log n)$，其中 $n$ 是 $\mathit{\text{letters}}$ 的长度。空间复杂度 $O(1)$。

func nextGreatestLetter(letters []byte, target byte) byte {
	i := sort.Search(len(letters), func(i int) bool { return letters[i] > target })
	return letters[i%len(letters)]
}

力扣原题 · Doocs 题解来源

754. 到达终点数字

中等1 种解法

标签：数学、二分查找

题目、示例与约束

在一根无限长的数轴上，你站在0的位置。终点在target的位置。

你可以做一些数量的移动 numMoves :

• 每次你可以选择向左或向右移动。
• 第 i 次移动（从  i == 1 开始，到 i == numMoves ），在选择的方向上走 i 步。

给定整数 target ，返回 到达目标所需的 最小 移动次数(即最小 numMoves ) 。

 

示例 1:

输入: target = 2
输出: 3
解释:
第一次移动，从 0 到 1 。
第二次移动，从 1 到 -1 。
第三次移动，从 -1 到 2 。

示例 2:

输入: target = 3
输出: 2
解释:
第一次移动，从 0 到 1 。
第二次移动，从 1 到 3 。

 

提示:

• -109 <= target <= 109
• target != 0

方法一：数学分析 · Go 实现

思考

第 $i$ 步必须走 $i$，方向自选，求到达 $\mathit{\text{target}}$ 的最少步数。目标可达 ${10}^9$，搜索步数序列不可行。

方向关于原点对称，可先取绝对值。连续向右走 $k$ 步到达三角数 $s$；若 $s-\mathit{\text{target}}$ 为偶数，把其中 $\frac{s-\mathit{\text{target}}}{2}$ 这一步反向即可，步数不变。

增大 $k$ 直到 $s\ge \mathit{\text{target}}$ 且差为偶数。 $k$ 为 $O(\sqrt{|\mathit{\text{target}}|})$。

由于对称性，每次可以选择向左或向右移动，因此，我们可以将 $\mathit{\text{target}}$ 统一取绝对值。

定义 $s$ 表示当前所处的位置，用变量 $k$ 记录移动的次数。初始时 $s$ 和 $k$ 均为 $0$。

我们将 $s$ 一直循环累加，直到满足 $s\ge \mathit{\text{target}}$ 并且 $(s-\mathit{\text{target}})mod2=0$，此时的移动次数 $k$ 就是答案，直接返回。

为什么？因为如果 $s\ge \mathit{\text{target}}$ 且 $(s-\mathit{\text{target}})\mathrm{mod}2=0$，我们只需要把前面 $\frac{s-\mathit{\text{target}}}{2}$ 这个正整数变为负数，就能使得 $s$ 与 $\mathit{\text{target}}$ 相等。正整数变负数的过程，实际上是将移动的方向改变，但实际移动次数仍然不变。

时间复杂度 $O(\sqrt{\left|\mathit{\text{target}}\right|})$，空间复杂度 $O(1)$。

func reachNumber(target int) int {
	if target < 0 {
		target = -target
	}
	var s, k int
	for {
		if s >= target && (s-target)%2 == 0 {
			return k
		}
		k++
		s += k
	}
}

力扣原题 · Doocs 题解来源

774. 最小化去加油站的最大距离 🔒

困难1 种解法

标签：数组、二分查找

题目、示例与约束

整数数组 stations 表示 水平数轴 上各个加油站的位置。给你一个整数 k 。

请你在数轴上增设 k 个加油站，新增加油站可以位于 水平数轴 上的任意位置，而不必放在整数位置上。

设 penalty() 是：增设 k 个新加油站后，相邻 两个加油站间的最大距离。

请你返回 penalty() 可能的最小值。与实际答案误差在 10-6 范围内的答案将被视作正确答案。

 

示例 1：

输入：stations = [1,2,3,4,5,6,7,8,9,10], k = 9
输出：0.50000

示例 2：

输入：stations = [23,24,36,39,46,56,57,65,84,98], k = 1
输出：14.00000

 

提示：

• 10 <= stations.length <= 2000
• 0 <= stations[i] <= 108
• stations 按 严格递增 顺序排列
• 1 <= k <= 106

方法一：二分查找（浮点数二分） · Go 实现

思考

在已有站之间插入至多 $k$ 个新站，最小化相邻站的最大间距。 $k$ 可达 ${10}^6$，不能枚举每段插几个。

答案关于「最大间距 $x$」单调：间距越小需要的插入越多。一段长 $d$ 需要 $\lfloor d/x\rfloor$ 个新站才能把间距压到 $x$ 以下。

对 $x$ 做浮点二分，判定插入总数是否 $\le k$。精度 ${10}^{-6}$。

我们二分枚举相邻两个加油站间的距离，找到最小的距离，使得加油站的数量不超过 $k$。

时间复杂度 $O(n\log M)$。其中 $n$ 为加油站的数量；而 $M$ 为答案的范围，即 ${10}^8$ 除以答案的精度 ${10}^{-6}$。

func minmaxGasDist(stations []int, k int) float64 {
	check := func(x float64) bool {
		s := 0
		for i, v := range stations[:len(stations)-1] {
			s += int(float64(stations[i+1]-v) / x)
		}
		return s <= k
	}
	var left, right float64 = 0, 1e8
	for right-left > 1e-6 {
		mid := (left + right) / 2.0
		if check(mid) {
			right = mid
		} else {
			left = mid
		}
	}
	return left
}

力扣原题 · Doocs 题解来源

786. 第 K 个最小的质数分数

中等1 种解法

标签：数组、双指针、二分查找、排序、堆（优先队列）

题目、示例与约束

给你一个按递增顺序排序的数组 arr 和一个整数 k 。数组 arr 由 1 和若干 质数 组成，且其中所有整数互不相同。

对于每对满足 0 <= i < j < arr.length 的 i 和 j ，可以得到分数 arr[i] / arr[j] 。

那么第 k 个最小的分数是多少呢?  以长度为 2 的整数数组返回你的答案, 这里 answer[0] == arr[i] 且 answer[1] == arr[j] 。

 

示例 1：

输入：arr = [1,2,3,5], k = 3
输出：[2,5]
解释：已构造好的分数,排序后如下所示: 
1/5, 1/3, 2/5, 1/2, 3/5, 2/3
很明显第三个最小的分数是 2/5

示例 2：

输入：arr = [1,7], k = 1
输出：[1,7]

 

提示：

• 2 <= arr.length <= 1000
• 1 <= arr[i] <= 3 * 104
• arr[0] == 1
• arr[i] 是一个 质数 ，i > 0
• arr 中的所有数字 互不相同 ，且按 严格递增 排序
• 1 <= k <= arr.length * (arr.length - 1) / 2

 

进阶：你可以设计并实现时间复杂度小于 O(n2) 的算法解决此问题吗？

方法一 · Go 实现

思考

有序质数数组中第 $k$ 小的真分数 $arr[i]/arr[j]$（ $i<j$）。 $n\le 1000$，枚举全部 $O(n^2)$ 对再排序偏慢。

固定分母 $arr[j]$ 时分子增大分数增大，全体分数构成 $n-1$ 条有序链。多路归并用小根堆每次弹出当前最小，把同一 $j$ 的下一个分子推入。

初态放入每条链的最小元 $arr[0]/arr[j]$，弹出 $k-1$ 次后堆顶即答案。

type frac struct{ x, y, i, j int }
type hp []frac

func (a hp) Len() int           { return len(a) }
func (a hp) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a hp) Less(i, j int) bool { return a[i].x*a[j].y < a[j].x*a[i].y }
func (a *hp) Push(x any)        { *a = append(*a, x.(frac)) }
func (a *hp) Pop() any          { l := len(*a); tmp := (*a)[l-1]; *a = (*a)[:l-1]; return tmp }

func kthSmallestPrimeFraction(arr []int, k int) []int {
	n := len(arr)
	h := make(hp, 0, n-1)
	for i := 1; i < n; i++ {
		h = append(h, frac{1, arr[i], 0, i})
	}
	heap.Init(&h)
	for i := 1; i < k; i++ {
		f := heap.Pop(&h).(frac)
		if f.i+1 < f.j {
			heap.Push(&h, frac{arr[f.i+1], arr[f.j], f.i + 1, f.j})
		}
	}
	return []int{h[0].x, h[0].y}
}

力扣原题 · Doocs 题解来源

793. 阶乘函数后 K 个零

困难1 种解法

标签：数学、二分查找

题目、示例与约束

 f(x) 是 x! 末尾是 0 的数量。回想一下 x! = 1 * 2 * 3 * ... * x，且 0! = 1 。

• 例如， f(3) = 0 ，因为 3! = 6 的末尾没有 0 ；而 f(11) = 2 ，因为 11!= 39916800 末端有 2 个 0 。

给定 k，找出返回能满足 f(x) = k 的非负整数 x 的数量。

 

示例 1：

输入：k = 0
输出：5
解释：0!, 1!, 2!, 3!, 和 4! 均符合 k = 0 的条件。

示例 2：

输入：k = 5
输出：0
解释：没有匹配到这样的 x!，符合 k = 5 的条件。

示例 3:

输入: k = 3
输出: 5

 

提示:

• 0 <= k <= 109

方法一：二分查找 · Go 实现

思考

$f(x)$ 为 $x!$ 尾零个数，问有多少 $x$ 使 $f(x)=k$。 $f$ 单调不降且会跳过某些值，跳过则答案为 $0$，否则一段连续 $x$ 同值，长度多为 $5$。

最小的满足 $f(x)\ge k$ 的 $x$ 记为 $g(k)$，所求即 $g(k+1)-g(k)$。 $f(x)\ge x/5$，故在 $[0,5k]$ 上二分 $g$。

定义 $f(x)$ 为 $x!$ 末尾零的个数，那么

$$f(x)=\{\begin{array}{l}0,x=0\\ x/5+f(x/5),x>0\end{array}$$

定义 $g(k)$ 表示 $x!$ 末尾为零的个数为 $k$ 的最小的 $x$ 值，那么题目等价于求解 $g(k+1)-g(k)$。

由于 $g(k)$ 是单调递增的，因此可以使用二分查找求解 $g(k)$。

同时，由于 $f(x)=x/5+f(x/5)\ge x/5$，因此 $f(5k)\ge k$。所以，求解 $g(k)$ 时，二分的右边界可以取 $5k$。

时间复杂度 $O(lo{g}^{2}k)$，其中 $k$ 为题目给定的整数。二分查找 $g(k)$ 的时间复杂度为 $O(logk)$，计算 $f(x)$ 的时间复杂度为 $O(logx)$，因此总时间复杂度为 $O(lo{g}^{2}k)$。

func preimageSizeFZF(k int) int {
	f := func(x int) int {
		res := 0
		for x != 0 {
			x /= 5
			res += x
		}
		return res
	}

	g := func(k int) int {
		left, right := 0, k*5
		for left < right {
			mid := (left + right) >> 1
			if f(mid) >= k {
				right = mid
			} else {
				left = mid + 1
			}
		}
		return left
	}

	return g(k+1) - g(k)
}

力扣原题 · Doocs 题解来源

825. 适龄的朋友

中等1 种解法

标签：数组、双指针、二分查找、排序

题目、示例与约束

在社交媒体网站上有 n 个用户。给你一个整数数组 ages ，其中 ages[i] 是第 i 个用户的年龄。

如果下述任意一个条件为真，那么用户 x 将不会向用户 y（x != y）发送好友请求：

• ages[y] <= 0.5 * ages[x] + 7
• ages[y] > ages[x]
• ages[y] > 100 && ages[x] < 100

否则，x 将会向 y 发送一条好友请求。

注意，如果 x 向 y 发送一条好友请求，y 不必也向 x 发送一条好友请求。另外，用户不会向自己发送好友请求。

返回在该社交媒体网站上产生的好友请求总数。

 

示例 1：

输入：ages = [16,16]
输出：2
解释：2 人互发好友请求。

示例 2：

输入：ages = [16,17,18]
输出：2
解释：产生的好友请求为 17 -> 16 ，18 -> 17 。

示例 3：

输入：ages = [20,30,100,110,120]
输出：3
解释：产生的好友请求为 110 -> 100 ，120 -> 110 ，120 -> 100 。

 

提示：

• n == ages.length
• 1 <= n <= 2 * 104
• 1 <= ages[i] <= 120

方法一：计数 + 枚举 · Go 实现

思考

好友请求的条件只依赖两个年龄，且年龄范围仅 $1\dots 120$，而 $n$ 可达 $2\cdot {10}^4$。两两枚举人会重复计算相同年龄对。

先计数每个年龄的人数，再枚举年龄对 $(x,y)$ 判断是否满足三个不等式。同一年龄内部要去掉自己给自己发请求，贡献为 $x\cdot (y-[x=y])$。

我们可以用一个长度为 $121$ 的数组 $\mathit{\text{cnt}}$ 记录每个年龄的人数。

接下来，枚举所有可能的年龄对 $(\mathit{\text{ax}},\mathit{\text{ay}})$，如果 $\mathit{\text{ax}}$ 和 $\mathit{\text{ay}}$ 不满足题目中的任意一个条件，这些年龄对 $(\mathit{\text{ax}},\mathit{\text{ay}})$ 就可以互发好友请求。

此时，如果 $\mathit{\text{ax}}=\mathit{\text{ay}}$，年龄相同，那么 $\mathit{\text{ax}}$ 和 $\mathit{\text{ay}}$ 之间的好友请求数为 $\mathit{\text{cnt}}[\mathit{\text{ax}}]\times (\mathit{\text{cnt}}[\mathit{\text{ax}}]-1)$；否则，年龄不同，那么 $\mathit{\text{ax}}$ 和 $\mathit{\text{ay}}$ 之间的好友请求数为 $\mathit{\text{cnt}}[\mathit{\text{ax}}]\times \mathit{\text{cnt}}[\mathit{\text{ay}}]$。我们将这些好友请求数累加到答案中即可。

时间复杂度 $O(n+m^2)$，其中 $n$ 是数组 $\mathit{\text{ages}}$ 的长度，而 $m$ 是年龄的最大值，本题中 $m=121$。

func numFriendRequests(ages []int) (ans int) {
	cnt := [121]int{}
	for _, x := range ages {
		cnt[x]++
	}
	for ax, x := range cnt {
		for ay, y := range cnt {
			if ay <= ax/2+7 || ay > ax || (ay > 100 && ax < 100) {
				continue
			}
			if ax == ay {
				ans += x * (x - 1)
			} else {
				ans += x * y
			}
		}
	}

	return
}

力扣原题 · Doocs 题解来源

852. 山脉数组的峰顶索引

中等1 种解法

标签：数组、二分查找、三分查找

题目、示例与约束

给定一个长度为 n 的整数 山脉 数组 arr ，其中的值递增到一个 峰值元素 然后递减。

返回峰值元素的下标。

你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。

 

示例 1：

输入：arr = [0,1,0]
输出：1

示例 2：

输入：arr = [0,2,1,0]
输出：1

示例 3：

输入：arr = [0,10,5,2]
输出：1

 

提示：

• 3 <= arr.length <= 105
• 0 <= arr[i] <= 106
• 题目数据 保证 arr 是一个山脉数组

方法一 · Go 实现

思考

数组保证先严格上升再严格下降，求峰下标。线性扫描可行，但 $n\le {10}^5$ 且题目暗示对数时间。峰左侧 $arr[i]<arr[i+1]$，右侧相反。

在 $[1,n-2]$ 上二分：若 $arr[mid]>arr[mid+1]$ 则峰在左半（含 $mid$），否则在右半。收缩后左端点即峰。

func peakIndexInMountainArray(arr []int) int {
	left, right := 1, len(arr)-2
	for left < right {
		mid := (left + right) >> 1
		if arr[mid] > arr[mid+1] {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return left
}

力扣原题 · Doocs 题解来源

862. 和至少为 K 的最短子数组

困难1 种解法

标签：队列、数组、二分查找、前缀和、滑动窗口、单调队列、堆（优先队列）

题目、示例与约束

给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。

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

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

• 1 <= nums.length <= 105
• -105 <= nums[i] <= 105
• 1 <= k <= 109

方法一：前缀和 + 单调队列 · Go 实现

思考

最短子数组和至少为 $k$。含负数时滑动窗口的单调性被破坏， $n\le {10}^5$ 不能平方枚举。前缀和 $s$ 上即求最小的 $j-i$ 满足 $s[j]-s[i]\ge k$。

维护 $s$ 下标的单调递增队列：队头已能组成 $\ge k$ 则弹出并更新长度；队尾不小于当前前缀和则丢掉，因为更短且前缀和更大的起点更优。

题目要求找到一个最短的子数组，使得子数组的和大于等于 $k$。不难想到，可以使用前缀和快速计算子数组的和。

我们用一个长度为 $n+1$ 的数组 $s[i]$ 表示数组 $nums$ 前 $i$ 个元素的和。另外，我们需要维护一个严格单调递增的队列 $q$，队列中存储的是前缀和数组 $s[i]$ 的下标。注意，这里的单调递增是指下标对应的前缀和的大小，而不是下标的大小。

为什么存的是下标呢？这是为了方便计算子数组的长度。那为什么队列严格单调递增？我们可以用反证法来说明。

假设队列元素非严格单调递增，也即是说，存在下标 $i$ 和 $j$，满足 $i<j$，且 $s[i]\ge s[j]$。

当遍历到下标 $k$，其中 $i<j<k\le n$，此时 $s[k]-s[j]\ge s[k]-s[i]$，且 $nums[j..k-1]$ 的长度小于 $nums[i..k-1]$ 的长度。由于下标 $j$ 的存在，子数组 $nums[i..k-1]$ 一定不是最优解，队列中的下标 $i$ 是不必要的，需要将其移除。因此，队列中的元素一定严格单调递增。

回到这道题目上，我们遍历前缀和数组 $s$，对于遍历到的下标 $i$，如果 $s[i]-s[q.front]\ge k$，说明当前遇到了一个可行解，我们可以更新答案。此时，我们需要将队首元素出队，直到队列为空或者 $s[i]-s[q.front]<k$ 为止。

如果此时队列不为空，为了维持队列的严格单调递增，我们还需要判断队尾元素是否需要出队，如果 $s[q.back]\ge s[i]$，则需要循环将队尾元素出队，直到队列为空或者 $s[q.back]<s[i]$ 为止。然后，我们将下标 $i$ 入队。

遍历结束，如果我们没有找到可行解，那么返回 $-1$。否则，返回答案。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是数组 $nums$ 的长度。

func shortestSubarray(nums []int, k int) int {
	n := len(nums)
	s := make([]int, n+1)
	for i, x := range nums {
		s[i+1] = s[i] + x
	}
	q := []int{}
	ans := n + 1
	for i, v := range s {
		for len(q) > 0 && v-s[q[0]] >= k {
			ans = min(ans, i-q[0])
			q = q[1:]
		}
		for len(q) > 0 && s[q[len(q)-1]] >= v {
			q = q[:len(q)-1]
		}
		q = append(q, i)
	}
	if ans > n {
		return -1
	}
	return ans
}

力扣原题 · Doocs 题解来源

875. 爱吃香蕉的珂珂

中等1 种解法

标签：数组、二分查找

题目、示例与约束

珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。

珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。  

珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。

 

示例 1：

输入：piles = [3,6,7,11], h = 8
输出：4

示例 2：

输入：piles = [30,11,23,4,20], h = 5
输出：30

示例 3：

输入：piles = [30,11,23,4,20], h = 6
输出：23

 

提示：

• 1 <= piles.length <= 104
• piles.length <= h <= 109
• 1 <= piles[i] <= 109

方法一：二分查找 · Go 实现

思考

速度 $k$ 越大，耗时越少，要在 $h$ 小时内吃完的最小 $k$。 $h$ 与堆大小达 ${10}^9$，枚举 $k$ 不可行，但「能否在 $h$ 小时吃完」对 $k$ 单调。

在 $[1,maxpiles]$ 上二分，判定函数把每堆按 $k$ 向上取整后求和。第一个使判定为真的速度即答案。

我们注意到，如果珂珂能够以 $k$ 的速度在 $h$ 小时内吃完所有香蕉，那么她也可以以 $k^{\prime }>k$ 的速度在 $h$ 小时内吃完所有香蕉。这存在着单调性，因此我们可以使用二分查找，找到最小的满足条件的 $k$。

我们定义二分查找的左边界 $l=1$，右边界 $r=max(\mathit{\text{piles}})$。每一次二分，我们取中间值 $mid=\frac{l+r}{2}$，然后计算以 $mid$ 的速度吃香蕉需要的时间 $s$。如果 $s\le h$，说明 $mid$ 的速度可以满足条件，我们将右边界 $r$ 更新为 $mid$；否则，我们将左边界 $l$ 更新为 $mid+1$。最终，当 $l=r$ 时，我们找到了最小的满足条件的 $k$。

时间复杂度 $O(n\times \log M)$，其中 $n$ 和 $M$ 分别是数组 $\mathit{\text{piles}}$ 的长度和最大值。空间复杂度 $O(1)$。

func minEatingSpeed(piles []int, h int) int {
	return 1 + sort.Search(slices.Max(piles), func(k int) bool {
		k++
		s := 0
		for _, x := range piles {
			s += (x + k - 1) / k
		}
		return s <= h
	})
}

力扣原题 · Doocs 题解来源

878. 第 N 个神奇数字

困难1 种解法

标签：数学、二分查找、容斥原理、最小公倍数

题目、示例与约束

一个正整数如果能被 a 或 b 整除，那么它是神奇的。

给定三个整数 n , a , b ，返回第 n 个神奇的数字。因为答案可能很大，所以返回答案 对 109 + 7 取模 后的值。

 

示例 1：

输入：n = 1, a = 2, b = 3
输出：2

示例 2：

输入：n = 4, a = 2, b = 3
输出：6

 

提示：

• 1 <= n <= 109
• 2 <= a, b <= 4 * 104

 

方法一：数学 + 二分查找 · Go 实现

思考

第 $n$ 个能被 $a$ 或 $b$ 整除的正整数， $n$ 达 ${10}^9$。直接按倍数枚举过慢。不超过 $x$ 的神奇数个数为 $x/a+x/b-x/\mathrm{lcm}(a,b)$，该函数对 $x$ 单调。

在足够大的上界上二分最小的 $x$ 使计数达到 $n$，再取模。上界取 $(a+b)\cdot n$ 已覆盖。

根据题目描述，神奇数字是能被 $a$ 或 $b$ 整除的正整数。

而我们知道，对于任意正整数 $x$，在 $[1,..x]$ 范围内，能被 $a$ 整除的数有 $\lfloor \frac{x}{a}\rfloor$ 个，能被 $b$ 整除的数有 $\lfloor \frac{x}{b}\rfloor$ 个，能被 $a$ 和 $b$ 同时整除的数有 $\lfloor \frac{x}{c}\rfloor$ 个，其中 $c$ 是 $a$ 和 $b$ 的最小公倍数。最小公倍数的计算公式为 $c=lcm(a,b)=\frac{a\times b}{gcd(a,b)}$。

因此，对于任意正整数 $x$，在 $[1,..x]$ 范围内，神奇数字的个数为：

$$\lfloor \frac{x}{a}\rfloor +\lfloor \frac{x}{b}\rfloor -\lfloor \frac{x}{c}\rfloor$$

为什么要减去 $\lfloor \frac{x}{c}\rfloor$ 呢？可以这样理解，在 $[1,..x]$ 范围内，能被 $a$ 和 $b$ 同时整除的数，它们既能被 $a$ 整除，也能被 $b$ 整除，因此它们被计算了两次，需要减去一次。

题目要我们找到第 $n$ 个神奇数字，也即是说，要找到一个最小的正整数 $x$，使得以下式子成立：

$$\lfloor \frac{x}{a}\rfloor +\lfloor \frac{x}{b}\rfloor -\lfloor \frac{x}{c}\rfloor \ge n$$

随着 $x$ 的增大，神奇数字的个数也会增大，因此我们可以使用二分查找的方法，找到最小的正整数 $x$，使得上述式子成立。

注意答案的取模操作。

时间复杂度 $O(\log M)$，空间复杂度 $O(1)$。其中 $M$ 是二分查找的上界，本题可以取 $M=(a+b)\times n$。

func nthMagicalNumber(n int, a int, b int) int {
	c := a * b / gcd(a, b)
	const mod int = 1e9 + 7
	r := (a + b) * n
	return sort.Search(r, func(x int) bool { return x/a+x/b-x/c >= n }) % mod
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

力扣原题 · Doocs 题解来源

888. 公平的糖果交换

简单1 种解法

标签：数组、哈希表、二分查找、排序

题目、示例与约束

爱丽丝和鲍勃拥有不同总数量的糖果。给你两个数组 aliceSizes 和 bobSizes ，aliceSizes[i] 是爱丽丝拥有的第 i 盒糖果中的糖果数量，bobSizes[j] 是鲍勃拥有的第 j 盒糖果中的糖果数量。

两人想要互相交换一盒糖果，这样在交换之后，他们就可以拥有相同总数量的糖果。一个人拥有的糖果总数量是他们每盒糖果数量的总和。

返回一个整数数组 answer，其中 answer[0] 是爱丽丝必须交换的糖果盒中的糖果的数目，answer[1] 是鲍勃必须交换的糖果盒中的糖果的数目。如果存在多个答案，你可以返回其中 任何一个 。题目测试用例保证存在与输入对应的答案。

 

示例 1：

输入：aliceSizes = [1,1], bobSizes = [2,2]
输出：[1,2]

示例 2：

输入：aliceSizes = [1,2], bobSizes = [2,3]
输出：[1,2]

示例 3：

输入：aliceSizes = [2], bobSizes = [1,3]
输出：[2,3]

示例 4：

输入：aliceSizes = [1,2,5], bobSizes = [2,4]
输出：[5,4]

 

提示：

• 1 <= aliceSizes.length, bobSizes.length <= 104
• 1 <= aliceSizes[i], bobSizes[j] <= 105
• 爱丽丝和鲍勃的糖果总数量不同。
• 题目数据保证对于给定的输入至少存在一个有效答案。

方法一：哈希表 · Go 实现

思考

各换一盒使两人糖数相等。设爱丽丝拿出 $a$、鲍勃拿出 $b$，则 $a-b$ 等于总差的一半。 $n\le {10}^4$，对每个 $a$ 扫描鲍勃会平方。

把鲍勃的盒重放入集合，枚举 $a$ 查 $a-\mathit{\text{diff}}$ 是否存在。题目保证有解。

我们可以先计算出爱丽丝和鲍勃的糖果总数之差，除以二得到需要交换的糖果数之差 $\mathit{\text{diff}}$，用一个哈希表 $\mathit{\text{s}}$ 存储鲍勃的糖果盒中的糖果数，然后遍历爱丽丝的糖果盒，对于每个糖果数 $\mathit{\text{a}}$，我们判断 $\mathit{\text{a}}-\mathit{\text{diff}}$ 是否在哈希表 $\mathit{\text{s}}$ 中，如果存在，说明找到了一组答案，返回即可。

时间复杂度 $O(m+n)$，空间复杂度 $O(n)$。其中 $m$ 和 $n$ 分别是爱丽丝和鲍勃的糖果盒的数量。

func fairCandySwap(aliceSizes []int, bobSizes []int) []int {
	s1, s2 := 0, 0
	s := map[int]bool{}
	for _, a := range aliceSizes {
		s1 += a
	}
	for _, b := range bobSizes {
		s2 += b
		s[b] = true
	}
	diff := (s1 - s2) / 2
	for _, a := range aliceSizes {
		if b := a - diff; s[b] {
			return []int{a, b}
		}
	}
	return nil
}

力扣原题 · Doocs 题解来源

1004. 最大连续1的个数 III

中等1 种解法

标签：数组、二分查找、前缀和、滑动窗口

题目、示例与约束

给定一个二进制数组 nums 和一个整数 k，假设最多可以翻转 k 个 0 ，则返回执行操作后 数组中连续 1 的最大个数 。

 

示例 1：

输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。

示例 2：

输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。

 

提示：

• 1 <= nums.length <= 105
• nums[i] 不是 0 就是 1
• 0 <= k <= nums.length

方法一：滑动窗口 · Go 实现

思考

枚举所有子数组并统计其中 $0$ 的个数需要 $O(n^2)$，而 $n\le {10}^5$，不可行。所求是「至多翻转 $k$ 个 $0$」后最长的连续 $1$，等价于最长且含 $0$ 不超过 $k$ 个的窗口。

窗口右端每前进一步，若零的个数超过 $k$，则左端也必须前进以恢复可行性。题目只要最长长度，窗口只需单调变长，左端每次至多移动一格，不必缩到合法后再继续。

用 $l$ 与 $\mathit{\text{cnt}}$ 维护当前窗口：右端扫过每个位置，超限则丢掉左端的一个位置。结束时 $n-l$ 即为最大可行窗口长度。

我们可以遍历数组，用一个变量 $\mathit{\text{cnt}}$ 记录当前窗口中 0 的个数，当 $\mathit{\text{cnt}}>k$ 时，我们将窗口的左边界右移一位。

遍历结束后，窗口的长度即为最大连续 1 的个数。

注意，在上述过程中，我们不需要循环将窗口的左边界右移，而是直接将左边界右移一位，这是因为，题目求的是最大连续 1 的个数，因此，窗口的长度只会增加，不会减少，所以我们不需要循环右移左边界。

时间复杂度 $O(n)$，其中 $n$ 为数组的长度。空间复杂度 $O(1)$。

相似题目：

• 487. 最大连续 1 的个数 II
• 2024. 考试的最大困扰度

func longestOnes(nums []int, k int) int {
	l, cnt := 0, 0
	for _, x := range nums {
		cnt += x ^ 1
		if cnt > k {
			cnt -= nums[l] ^ 1
			l++
		}
	}
	return len(nums) - l
}

力扣原题 · Doocs 题解来源

1011. 在 D 天内送达包裹的能力

中等1 种解法

标签：数组、二分查找

题目、示例与约束

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

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

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

 

示例 1：

输入：weights = [1,2,3,4,5,6,7,8,9,10], days = 5
输出：15
解释：
船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：
第 1 天：1, 2, 3, 4, 5
第 2 天：6, 7
第 3 天：8
第 4 天：9
第 5 天：10

请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。 

示例 2：

输入：weights = [3,2,2,4,1,4], days = 3
输出：6
解释：
船舶最低载重 6 就能够在 3 天内送达所有包裹，如下所示：
第 1 天：3, 2
第 2 天：2, 4
第 3 天：1, 4

示例 3：

输入：weights = [1,2,3,1,1], days = 4
输出：3
解释：
第 1 天：1
第 2 天：2
第 3 天：3
第 4 天：1, 1

 

提示：

• 1 <= days <= weights.length <= 5 * 104
• 1 <= weights[i] <= 500

方法一：二分查找 · Go 实现

思考

运载能力的下界是最重包裹，上界是全部重量之和，在该范围内逐一验证所需天数， $n\le 5\times {10}^4$ 且总和可达千万级，线性枚举不可行。

能力增大时所需天数不会增加，因此「能否在 $\mathit{\text{days}}$ 天内运完」对能力值单调，最小可行能力可以用二分定位。

对给定上限 $x$，按顺序把包裹装入当前船，超重则换一天。在 $[max{w}_i,\sum w_i]$ 上二分第一次使 $\mathit{\text{check}}$ 为真的位置。

我们注意到，如果运载能力 $x$ 能够在 $days$ 天内运送完所有包裹，那么运载能力 $x+1$ 也能在 $days$ 天内运送完所有包裹。也即是说，随着运载能力的增加，运送天数只会减少，不会增加。这存在一个单调性，因此我们可以使用二分查找的方法来寻找最小的运载能力。

我们定义二分查找的左边界 $left=\underset{i=0}{\overset{n-1}{max}}weights[i]$，右边界 $right=\sum _{i=0}^{n-1}weights[i]$。然后二分枚举运载能力 $x$，判断是否能在 $days$ 天内运送完所有包裹。如果能，那么我们将右边界调整为 $x$，否则将左边界调整为 $x+1$。

判断是否能在 $days$ 天内运送完所有包裹的方法是，我们从左到右遍历包裹，将当前包裹加入当前运载能力的船上，如果当前船的运载能力超过了 $x$，那么我们将当前包裹放到下一天的船上，同时天数加一。如果天数超过了 $days$，那么我们返回 $false$，否则返回 $true$。

时间复杂度 $O(n\times \log \sum _{i=0}^{n-1}weights[i])$，空间复杂度 $O(1)$。其中 $n$ 为包裹数量。

func shipWithinDays(weights []int, days int) int {
	var left, right int
	for _, w := range weights {
		if left < w {
			left = w
		}
		right += w
	}
	return left + sort.Search(right, func(mx int) bool {
		mx += left
		ws, cnt := 0, 1
		for _, w := range weights {
			ws += w
			if ws > mx {
				ws = w
				cnt++
			}
		}
		return cnt <= days
	})
}

力扣原题 · Doocs 题解来源

1044. 最长重复子串

困难1 种解法

标签：字符串、二分查找、后缀数组、滑动窗口、哈希函数、滚动哈希、Boyer–Moore 算法、扩展 KMP

题目、示例与约束

给你一个字符串 s ，考虑其所有 重复子串 ：即 s 的（连续）子串，在 s 中出现 2 次或更多次。这些出现之间可能存在重叠。

返回 任意一个 可能具有最长长度的重复子串。如果 s 不含重复子串，那么答案为 "" 。

 

示例 1：

输入：s = "banana"
输出："ana"

示例 2：

输入：s = "abcd"
输出：""

 

提示：

• 2 <= s.length <= 3 * 104
• s 由小写英文字母组成

方法一：字符串哈希 + 二分查找 · Go 实现

思考

枚举所有子串再放入集合判断重复， $n\le 3\times {10}^4$ 时平方级不可行。若存在长为 $L$ 的重复子串，则更短的也存在，长度具有单调性。

对长度二分：检查函数把所有长为 $\mathit{\text{mid}}$ 的切片放入集合，一旦碰撞就返回该串。能找到则尝试更长，否则缩短。

实现直接用 Python 切片与哈希集合；二分过程中记下最后一次命中的串作为答案。

字符串哈希是把一个任意长度的字符串映射成一个非负整数，并且其冲突的概率几乎为 0。字符串哈希用于计算字符串哈希值，快速判断两个字符串是否相等。

取一固定值 BASE，把字符串看作是 BASE 进制数，并分配一个大于 0 的数值，代表每种字符。一般来说，我们分配的数值都远小于 BASE。例如，对于小写字母构成的字符串，可以令 a=1, b=2, ..., z=26。取一固定值 MOD，求出该 BASE 进制对 M 的余数，作为该字符串的 hash 值。

一般来说，取 BASE=131 或者 BASE=13331，此时 hash 值产生的冲突概率极低。只要两个字符串 hash 值相同，我们就认为两个字符串是相等的。通常 MOD 取 2^64，C++ 里，可以直接使用 unsigned long long 类型存储这个 hash 值，在计算时不处理算术溢出问题，产生溢出时相当于自动对 2^64 取模，这样可以避免低效取模运算。

除了在极特殊构造的数据上，上述 hash 算法很难产生冲突，一般情况下上述 hash 算法完全可以出现在题目的标准答案中。我们还可以多取一些恰当的 BASE 和 MOD 的值（例如大质数），多进行几组 hash 运算，当结果都相同时才认为原字符串相等，就更加难以构造出使这个 hash 产生错误的数据。

对于本题，二分枚举长度，找到满足条件的最大长度即可。

时间复杂度 $O(n\log n)$。其中 $n$ 为字符串长度。

相似题目：

• 1062. 最长重复子串

func longestDupSubstring(s string) string {
	base, n := 131, len(s)
	p := make([]int64, n+10)
	h := make([]int64, n+10)
	p[0] = 1
	for i := 0; i < n; i++ {
		p[i+1] = p[i] * int64(base)
		h[i+1] = h[i]*int64(base) + int64(s[i])
	}
	check := func(l int) string {
		vis := make(map[int64]bool)
		for i := 1; i+l-1 <= n; i++ {
			j := i + l - 1
			t := h[j] - h[i-1]*p[j-i+1]
			if vis[t] {
				return s[i-1 : j]
			}
			vis[t] = true
		}
		return ""
	}
	left, right := 0, n
	ans := ""
	for left < right {
		mid := (left + right + 1) >> 1
		t := check(mid)
		if len(t) > 0 {
			left = mid
			ans = t
		} else {
			right = mid - 1
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1060. 有序数组中的缺失元素 🔒

中等1 种解法

标签：数组、二分查找

题目、示例与约束

现有一个按 升序 排列的整数数组 nums ，其中每个数字都 互不相同 。

给你一个整数 k ，请你找出并返回从数组最左边开始的第 k 个缺失数字。

 

示例 1：

输入：nums = [4,7,9,10], k = 1
输出：5
解释：第一个缺失数字为 5 。

示例 2：

输入：nums = [4,7,9,10], k = 3
输出：8
解释：缺失数字有 [5,6,8,...]，因此第三个缺失数字为 8 。

示例 3：

输入：nums = [1,2,4], k = 3
输出：6
解释：缺失数字有 [3,5,6,7,...]，因此第三个缺失数字为 6 。

 

提示：

• 1 <= nums.length <= 5 * 104
• 1 <= nums[i] <= 107
• nums 按 升序 排列，其中所有元素 互不相同 。
• 1 <= k <= 108

 

进阶：你可以设计一个对数时间复杂度（即，O(log(n))）的解决方案吗？

方法一：二分查找 · Go 实现

思考

有序且互异，下标 $i$ 之前缺失的个数是 $nums[i]-nums[0]-i$。线性扫到第 $k$ 个缺失即可，但进阶要求对数时间。

$\mathit{\text{missing}}(i)$ 随 $i$ 递增。若 $k$ 大于末尾缺失数，答案在数组右侧；否则二分最小的满足 $\mathit{\text{missing}}(i)\ge k$ 的 $i$，再从 $nums[i-1]$ 补上剩余缺口。

二分边界为 $[0,n-1]$。

我们设计一个函数 $missing(i)$，表示 $nums[i]$ 与 $nums[0]$ 之间缺失的元素个数。那么 $missing(i)$ 就等于 $nums[i]-nums[0]-i$。我们可以通过二分查找找到最小的 $i$，使得 $missing(i)\ge k$，那么 $nums[i-1]+k-missing(i-1)$ 就是第 $k$ 个缺失的元素。

时间复杂度 $O(\log n)$，空间复杂度 $O(1)$。其中 $n$ 为数组 $nums$ 的长度。

func missingElement(nums []int, k int) int {
	missing := func(i int) int {
		return nums[i] - nums[0] - i
	}
	n := len(nums)
	if k > missing(n-1) {
		return nums[n-1] + k - missing(n-1)
	}
	l, r := 0, n-1
	for l < r {
		mid := (l + r) >> 1
		if missing(mid) >= k {
			r = mid
		} else {
			l = mid + 1
		}
	}
	return nums[l-1] + k - missing(l-1)
}

力扣原题 · Doocs 题解来源

1064. 不动点 🔒

简单1 种解法

标签：数组、二分查找

题目、示例与约束

给定已经按 升序 排列、由不同整数组成的数组 arr，返回满足 arr[i] == i 的最小索引 i。如果不存在这样的 i，返回 -1。

 

示例 1：

输入：arr = [-10,-5,0,3,7]
输出：3
解释：对于给定的数组，arr[0] = -10，arr[1] = -5，arr[2] = 0，arr[3] = 3，因此输出为 3 。

示例 2：

输入：arr = [0,2,5,8,17]
输出：0
解释：arr[0] = 0，因此输出为 0 。

示例 3：

输入：arr = [-10,-5,3,4,7,9]
输出：-1
解释：不存在这样的 i 满足 arr[i] = i，因此输出为 -1 。

 

提示：

• 1 <= arr.length < 104
• -109 <= arr[i] <= 109

 

进阶：时间复杂度为 O(n) 的解决方案很直观也很简单。你可以设计更优的解决方案吗？

方法一：二分查找 · Go 实现

思考

线性扫描找 $arr[i]=i$ 的最小下标即可，进阶希望 $O(\log n)$。数组严格递增，故 $arr[i]-i$ 单调不降，第一个非负处即最小不动点候选。

若 $arr[mid]\ge mid$，答案不会在右侧；否则只可能在 $mid$ 之后。

二分到左端后检查是否真的相等，否则返回 $-1$。

题目给定的数组是按升序排列的，因此我们可以使用二分查找的方法找出最小的满足 $arr[i]$ 等于 $i$ 的下标 $i$。

我们定义二分查找的左边界 $left=0$，右边界 $right=n-1$。每一次，我们找到当前的中间位置 $mid$，如果中间位置满足 $arr[mid]\ge mid$，那么我们就确定了最小的不动点 🔒 的位置一定不会出现在下标大于 $mid$ 的位置，因此我们令 $right=mid$；如果中间位置满足 $arr[mid]<mid$，那么最小的不动点 🔒 一定出现在下标大于 $mid$ 的位置，因此我们令 $left=mid+1$。

最后，如果我们没有找到最小的不动点 🔒，那么我们返回 $-1$。

时间复杂度 $O(\log n)$，其中 $n$ 是数组的长度。空间复杂度 $O(1)$。

func fixedPoint(arr []int) int {
	left, right := 0, len(arr)-1
	for left < right {
		mid := (left + right) >> 1
		if arr[mid] >= mid {
			right = mid
		} else {
			left = mid + 1
		}
	}
	if arr[left] == left {
		return left
	}
	return -1
}

力扣原题 · Doocs 题解来源

1095. 山脉数组中查找目标值

困难1 种解法

标签：数组、二分查找、交互、三分查找

题目、示例与约束

（这是一个 交互式问题 ）

你可以将一个数组 arr 称为 山脉数组 当且仅当：

• arr.length >= 3
• 存在一些 0 < i < arr.length - 1 的 i 使得：
  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

给定一个山脉数组 mountainArr ，返回 最小 的 index 使得 mountainArr.get(index) == target。如果不存在这样的 index，返回 -1 。

你无法直接访问山脉数组。你只能使用 MountainArray 接口来访问数组：

• MountainArray.get(k) 返回数组中下标为 k 的元素（从 0 开始）。
• MountainArray.length() 返回数组的长度。

调用 MountainArray.get 超过 100 次的提交会被判定为错误答案。此外，任何试图绕过在线评测的解决方案都将导致取消资格。

 

示例 1：

输入：mountainArr = [1,2,3,4,5,3,1], target = 3
输出：2
解释：3 在数组中出现了两次，下标分别为 2 和 5，我们返回最小的下标 2。

示例 2：

输入：mountainArr = [0,1,2,4,2,1], target = 3
输出：-1
解释：3 在数组中没有出现，返回 -1。

 

提示：

• 3 <= mountainArr.length() <= 104
• 0 <= target <= 109
• 0 <= mountainArr.get(index) <= 109

方法一：二分查找 · Go 实现

思考

山脉数组只能通过 get 访问，长度 ${10}^4$，必须把查询次数压到对数。先定位峰顶，再在左侧升序、右侧降序各做一次二分。

比较 $get(mid)$ 与 $get(mid+1)$ 可判断峰在哪一侧。search 用系数 $k=\pm 1$ 统一升序与降序上的下界查找。

先查左半，没有再查右半，保证返回最小下标。

我们先通过二分查找，找到数组中的最大值所在的下标 $l$，那么数组就可以被分成两段，前半段是递增的，后半段是递减的。

然后我们在前半段中使用二分查找，查找目标值所在的下标，如果找不到，再在后半段中使用二分查找，查找目标值所在的下标。

时间复杂度 $O(\log n)$，其中 $n$ 是数组的长度。空间复杂度 $O(1)$。

/**
 * // This is the MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 * type MountainArray struct {
 * }
 *
 * func (this *MountainArray) get(index int) int {}
 * func (this *MountainArray) length() int {}
 */

func findInMountainArray(target int, mountainArr *MountainArray) int {
	n := mountainArr.length()
	l, r := 0, n-1
	for l < r {
		mid := (l + r) >> 1
		if mountainArr.get(mid) > mountainArr.get(mid+1) {
			r = mid
		} else {
			l = mid + 1
		}
	}
	search := func(l, r, k int) int {
		for l < r {
			mid := (l + r) >> 1
			if k*mountainArr.get(mid) >= k*target {
				r = mid
			} else {
				l = mid + 1
			}
		}
		if mountainArr.get(l) == target {
			return l
		}
		return -1
	}
	ans := search(0, l, 1)
	if ans == -1 {
		return search(l+1, n-1, -1)
	}
	return ans
}

力扣原题 · Doocs 题解来源