LeetCode Go · 二分查找（3）

来源与许可

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

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

1099. 小于 K 的两数之和 🔒

简单2 种解法

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

题目、示例与约束

给你一个整数数组 nums 和整数 k ，返回最大和 sum ，满足存在 i < j 使得 nums[i] + nums[j] = sum 且 sum < k 。如果没有满足此等式的 i,j 存在，则返回 -1 。

示例 1：

输入：nums = [34,23,1,24,75,33,54,8], k = 60
输出：58
解释：
34 和 24 相加得到 58，58 小于 60，满足题意。

示例 2：

输入：nums = [10,20,30], k = 15
输出：-1
解释：
我们无法找到和小于 15 的两个元素。

提示：

1 <= nums.length <= 100
1 <= nums[i] <= 1000
1 <= k <= 2000

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

思考

小于 $k$ 的最大两数之和，枚举一对是平方级。排序后对每个 $x$ 找小于 $k - x$ 的最大右端，可用二分。

对下标 $i$ ，在 $(i, n)$ 上 bisect_left 定位 $k - x$ ，前一个位置若仍大于 $i$ 则更新答案。

无合法对时保持 $- 1$ 。

我们可以先对数组 $n u m s$ 进行排序，初始化答案为 $- 1$ 。

接下来，我们枚举数组中的每个元素 $n u m s [i]$ ，并在数组中寻找满足 $n u m s [j] + n u m s [i] < k$ 的最大的 $n u m s [j]$ 。这里我们可以使用二分查找来加速寻找过程。如果找到了这样的 $n u m s [j]$ ，那么我们就可以更新答案，即 $a n s = max (a n s, n u m s [i] + n u m s [j])$ 。

枚举结束后，返回答案即可。

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

func twoSumLessThanK(nums []int, k int) int {
	sort.Ints(nums)
	ans := -1
	for i, x := range nums {
		j := sort.SearchInts(nums[i+1:], k-x) + i
		if v := nums[i] + nums[j]; i < j && ans < v {
			ans = v
		}
	}
	return ans
}

方法二：排序 + 双指针 · Go 实现

思考

每个 $x$ 一次二分共 $O (n \log n)$ 。两端相向是同一单调性：和偏小则左端右移以增大，和达到 $k$ 则右端左移。

双指针一次扫完所有互异下标对的帕累托前沿，常数更小。

与方法一类似，我们可以先对数组 $n u m s$ 进行排序，初始化答案为 $- 1$ 。

接下来，我们使用双指针 $i$ 和 $j$ 分别指向数组的左右两端，每次判断 $s = n u m s [i] + n u m s [j]$ 是否小于 $k$ ，如果小于 $k$ ，那么我们就可以更新答案，即 $a n s = max (a n s, s)$ ，并将 $i$ 右移一位，否则将 $j$ 左移一位。

枚举结束后，返回答案即可。

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

func twoSumLessThanK(nums []int, k int) int {
	sort.Ints(nums)
	ans := -1
	for i, j := 0, len(nums)-1; i < j; {
		if s := nums[i] + nums[j]; s < k {
			ans = max(ans, s)
			i++
		} else {
			j--
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1150. 检查一个数是否在数组中占绝大多数 🔒

简单2 种解法

标签：数组、二分查找

题目、示例与约束

给出一个按 非递减 顺序排列的数组 nums，和一个目标数值 target。假如数组 nums 中绝大多数元素的数值都等于 target，则返回 True，否则请返回 False。

所谓占绝大多数，是指在长度为 N 的数组中出现必须 超过 N/2 次。

示例 1：

输入：nums = [2,4,5,5,5,5,5,6,6], target = 5
输出：true
解释：
数字 5 出现了 5 次，而数组的长度为 9。
所以，5 在数组中占绝大多数，因为 5 次 > 9/2。

示例 2：

输入：nums = [10,100,101,101], target = 101
输出：false
解释：
数字 101 出现了 2 次，而数组的长度是 4。
所以，101 不是 数组占绝大多数的元素，因为 2 次 = 4/2。

提示：

1 <= nums.length <= 1000
1 <= nums[i] <= 10^9
1 <= target <= 10^9

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

思考

有序数组中 $t a r g e t$ 的出现次数等于其左右边界之差。两次二分分别得第一个 $\geq t a r g e t$ 与第一个 $> t a r g e t$ 的下标，差大于 $n / 2$ 则为多数元素。线性计数在 $n$ 较大时没有必要。

我们注意到，数组 $n u m s$ 中的元素是非递减的，也就是说，数组 $n u m s$ 中的元素单调递增。因此，我们可以使用二分查找的方法，找到数组 $n u m s$ 中第一个大于等于 $t a r g e t$ 的元素的下标 $l e f t$ ，以及第一个大于 $t a r g e t$ 的元素的下标 $r i g h t$ 。如果 $r i g h t - l e f t > \frac{n}{2}$ ，则说明数组 $n u m s$ 中的元素 $t a r g e t$ 出现的次数超过了数组长度的一半，因此返回 $t r u e$ ，否则返回 $f a l s e$ 。

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

func isMajorityElement(nums []int, target int) bool {
	left := sort.SearchInts(nums, target)
	right := sort.SearchInts(nums, target+1)
	return right-left > len(nums)/2
}

方法二：二分查找（优化） · Go 实现

思考

方法一用两次二分定位区间。若 $t a r g e t$ 出现超过一半，则 $l e f t + ⌊ n / 2 ⌋$ 处仍应等于 $t a r g e t$ 。一次 bisect_left 后再做一次下标检查即可，少一次二分。

方法一中，我们使用了两次二分查找，分别找到数组 $n u m s$ 中第一个大于等于 $t a r g e t$ 的元素的下标 $l e f t$ ，以及第一个大于 $t a r g e t$ 的元素的下标 $r i g h t$ 。但是，我们可以使用一次二分查找，找到数组 $n u m s$ 中第一个大于等于 $t a r g e t$ 的元素的下标 $l e f t$ ，然后判断 $n u m s [l e f t + \frac{n}{2}]$ 是否等于 $t a r g e t$ ，如果相等，说明数组 $n u m s$ 中的元素 $t a r g e t$ 出现的次数超过了数组长度的一半，因此返回 $t r u e$ ，否则返回 $f a l s e$ 。

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

func isMajorityElement(nums []int, target int) bool {
	n := len(nums)
	left := sort.SearchInts(nums, target)
	right := left + n/2
	return right < n && nums[right] == target
}

力扣原题 · Doocs 题解来源

1170. 比较字符串最小字母出现频次

中等1 种解法

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

题目、示例与约束

定义一个函数 f(s)，统计 s 中（按字典序比较）最小字母的出现频次 ，其中 s 是一个非空字符串。

例如，若 s = "dcce"，那么 f(s) = 2，因为字典序最小字母是 "c"，它出现了 2 次。

现在，给你两个字符串数组待查表 queries 和词汇表 words 。对于每次查询 queries[i] ，需统计 words 中满足 f(queries[i]) < f(W) 的 词的数目 ，W 表示词汇表 words 中的每个词。

请你返回一个整数数组 answer 作为答案，其中每个 answer[i] 是第 i 次查询的结果。

示例 1：

输入：queries = ["cbd"], words = ["zaaaz"]
输出：[1]
解释：查询 f("cbd") = 1，而 f("zaaaz") = 3 所以 f("cbd") < f("zaaaz")。

示例 2：

输入：queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]
输出：[1,2]
解释：第一个查询 f("bbb") < f("aaaa")，第二个查询 f("aaa") 和 f("aaaa") 都 > f("cc")。

提示：

1 <= queries.length <= 2000
1 <= words.length <= 2000
1 <= queries[i].length, words[i].length <= 10
queries[i][j]、words[i][j] 都由小写英文字母组成

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

思考

每个查询要数 $w o r d s$ 中 $f$ 值严格更大的个数。对每个查询扫描全部 $w o r d s$ 为 $O (q n)$ 。先把每个 $f (w)$ 算出并排序，查询时二分第一个大于 $f (q)$ 的位置，右侧长度即为答案。 $f$ 只依赖最小字母的次数，对短串线性可求。

我们先按照题目描述，实现函数 $f (s)$ ，函数返回字符串 $s$ 中按字典序比较最小字母的出现频次。

接下来，我们将 $w o r d s$ 中的每个字符串 $w$ 都计算出 $f (w)$ ，并将其排序，存放在数组 $n u m s$ 中。

然后，我们遍历 $q u e r i e s$ 中的每个字符串 $q$ ，在 $n u m s$ 中二分查找第一个大于 $f (q)$ 的位置 $i$ ，则 $n u m s$ 中下标 $i$ 及其后面的元素都满足 $f (q) < f (W)$ ，那么当前查询的答案就是 $n - i$ 。

时间复杂度 $O ((n + q) \times M)$ ，空间复杂度 $O (n)$ 。其中 $n$ 和 $q$ 分别是数组 $w o r d s$ 和 $q u e r i e s$ 的长度，而 $M$ 是字符串的最大长度。

func numSmallerByFrequency(queries []string, words []string) (ans []int) {
	f := func(s string) int {
		cnt := [26]int{}
		for _, c := range s {
			cnt[c-'a']++
		}
		for _, x := range cnt {
			if x > 0 {
				return x
			}
		}
		return 0
	}
	n := len(words)
	nums := make([]int, n)
	for i, w := range words {
		nums[i] = f(w)
	}
	sort.Ints(nums)
	for _, q := range queries {
		x := f(q)
		ans = append(ans, n-sort.SearchInts(nums, x+1))
	}
	return
}

力扣原题 · Doocs 题解来源

1198. 找出所有行中最小公共元素 🔒

中等1 种解法

标签：数组、哈希表、二分查找、计数、矩阵

题目、示例与约束

给你一个 m x n 的矩阵 mat，其中每一行的元素均符合 严格递增 。请返回所有行中的 最小公共元素 。

如果矩阵中没有这样的公共元素，就请返回 -1。

示例 1：

输入：mat = [[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]]
输出：5

示例 2:

输入：mat = [[1,2,3],[2,3,4],[2,3,5]]
输出： 2

提示：

m == mat.length
n == mat[i].length
1 <= m, n <= 500
1 <= mat[i][j] <= 10⁴
mat[i] 已按严格递增顺序排列。

方法一：计数 · Go 实现

思考

每行严格递增，故同一数字在一行至多一次。按行扫描并计数，某值次数到达行数即出现在每一行。行内从左到右保证较小值先被加满，因此第一次凑齐行数的值就是最小公共元素；若无则返回 $- 1$ 。

我们用一个长度为 $10001$ 的数组 $c n t$ 统计每个数出现的次数。顺序遍历矩阵中的每个数，将其出现次数加一。当某个数的出现次数等于矩阵的行数时，说明该数在每一行都出现过，即为最小公共元素，返回该数即可。

若遍历结束后没有找到最小公共元素，则返回 $- 1$ 。

时间复杂度 $O (m \times n)$ ，空间复杂度 $O (10^{4})$ 。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

func smallestCommonElement(mat [][]int) int {
	cnt := [10001]int{}
	for _, row := range mat {
		for _, x := range row {
			cnt[x]++
			if cnt[x] == len(mat) {
				return x
			}
		}
	}
	return -1
}

力扣原题 · Doocs 题解来源

1201. 丑数 III

中等1 种解法

标签：数学、二分查找、组合数学、最大公约数、数论、容斥原理、欧几里得算法、最小公倍数

题目、示例与约束

丑数是可以被 a 或 b 或 c 整除的 正整数 。

给你四个整数：n 、a 、b 、c ，请你设计一个算法来找出第 n 个丑数。

示例 1：

输入：n = 3, a = 2, b = 3, c = 5
输出：4
解释：丑数序列为 2, 3, 4, 5, 6, 8, 9, 10... 其中第 3 个是 4。

示例 2：

输入：n = 4, a = 2, b = 3, c = 4
输出：6
解释：丑数序列为 2, 3, 4, 6, 8, 9, 10, 12... 其中第 4 个是 6。

示例 3：

输入：n = 5, a = 2, b = 11, c = 13
输出：10
解释：丑数序列为 2, 4, 6, 8, 10, 11, 12, 13... 其中第 5 个是 10。

提示：

1 <= n, a, b, c <= 10⁹
1 <= a * b * c <= 10¹⁸
本题结果在 [1, 2 * 10⁹] 的范围内

方法一：二分查找 + 容斥原理 · Go 实现

思考

按从小到大枚举丑数需要生成约 $n$ 个候选， $n$ 可达 $10^{9}$ ，无法在时限内完成。

小于等于 $x$ 的丑数个数随 $x$ 单调不减，因此第 $n$ 个丑数是使该计数至少为 $n$ 的最小 $x$ 。计数本身可用容斥在 $O (1)$ 内求出：并上 $a, b, c$ 的倍数，再减去两两最小公倍数的倍数，加上三者最小公倍数的倍数。

为此在 $[1, 2 \times 10^{9}]$ 上二分 $x$ ，中点用容斥判断是否已覆盖至少 $n$ 个丑数。答案范围由题目保证，无需枚举具体丑数。

我们可以将题目转换为：找到最小的正整数 $x$ ，使得小于等于 $x$ 的丑数个数恰好为 $n$ 个。

对于一个正整数 $x$ ，能被 $a$ 整除的数有 $⌊ \frac{x}{a} ⌋$ 个，能被 $b$ 整除的数有 $⌊ \frac{x}{b} ⌋$ 个，能被 $c$ 整除的数有 $⌊ \frac{x}{c} ⌋$ 个，能被 $a$ 和 $b$ 同时整除的数有 $⌊ \frac{x}{l c m (a, b)} ⌋$ 个，能被 $a$ 和 $c$ 同时整除的数有 $⌊ \frac{x}{l c m (a, c)} ⌋$ 个，能被 $b$ 和 $c$ 同时整除的数有 $⌊ \frac{x}{l c m (b, c)} ⌋$ 个，能被 $a$ , $b$ 和 $c$ 同时整除的数有 $⌊ \frac{x}{l c m (a, b, c)} ⌋$ 个。根据容斥原理，小于等于 $x$ 的丑数个数为：

⌊ \frac{x}{a} ⌋ + ⌊ \frac{x}{b} ⌋ + ⌊ \frac{x}{c} ⌋ - ⌊ \frac{x}{l c m (a, b)} ⌋ - ⌊ \frac{x}{l c m (a, c)} ⌋ - ⌊ \frac{x}{l c m (b, c)} ⌋ + ⌊ \frac{x}{l c m (a, b, c)} ⌋

我们可以使用二分查找的方法找到最小的正整数 $x$ ，使得小于等于 $x$ 的丑数个数恰好为 $n$ 个。

定义二分查找的左边界为 $l = 1$ ，右边界为 $r = 2 \times 10^{9}$ ，其中 $2 \times 10^{9}$ 是题目给定的最大值。在二分查找的每一步中，我们找出中间数 $m i d$ ，如果小于等于 $m i d$ 的丑数个数大于等于 $n$ ，那么说明最小的正整数 $x$ 落在 $[l, m i d]$ 区间内，否则落在 $[m i d + 1, r]$ 区间内。在二分查找的过程中，我们需要不断更新小于等于 $m i d$ 的丑数个数，直到找到最小的正整数 $x$ 。

时间复杂度 $O (\log m)$ ，其中 $m = 2 \times 10^{9}$ 。空间复杂度 $O (1)$ 。

func nthUglyNumber(n int, a int, b int, c int) int {
	ab, bc, ac := lcm(a, b), lcm(b, c), lcm(a, c)
	abc := lcm(ab, c)
	var l, r int = 1, 2e9
	for l < r {
		mid := (l + r) >> 1
		if mid/a+mid/b+mid/c-mid/ab-mid/bc-mid/ac+mid/abc >= n {
			r = mid
		} else {
			l = mid + 1
		}
	}
	return l
}

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

func lcm(a, b int) int {
	return a * b / gcd(a, b)
}

力扣原题 · Doocs 题解来源

1208. 尽可能使字符串相等

中等3 种解法

标签：字符串、二分查找、前缀和、滑动窗口

题目、示例与约束

给你两个长度相同的字符串，s 和 t。

将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。

用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。

如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。

如果 s 中没有子字符串可以转化成 t 中对应的子字符串，则返回 0。

示例 1：

输入：s = "abcd", t = "bcdf", maxCost = 3
输出：3
解释：s 中的 "abc" 可以变为 "bcd"。开销为 3，所以最大长度为 3。

示例 2：

输入：s = "abcd", t = "cdef", maxCost = 3
输出：1
解释：s 中的任一字符要想变成 t 中对应的字符，其开销都是 2。因此，最大长度为 1。

示例 3：

输入：s = "abcd", t = "acde", maxCost = 0
输出：1
解释：a -> a, cost = 0，字符串未发生变化，所以最大长度为 1。

提示：

1 <= s.length <= 10⁵
t.length == s.length
0 <= maxCost <= 10⁶
s 和 t 都只含小写英文字母。

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

思考

子串费用是对应位置 ASCII 差的绝对值和。 $n \leq 10^{5}$ ，枚举全部 $O (n^{2})$ 子串不可行。

固定长度时，存在费用不超过 $m a x C o s t$ 的子串具有单调性：长度 $x$ 可行则 $x - 1$ 也可行。任意区间费用可由前缀和 $O (1)$ 求出。

为此先建差分数组的前缀和，再对长度二分，并用滑动窗口式枚举验证。二分利用单调性，前缀和去掉内层求和。

我们可以创建一个长度为 $n + 1$ 的数组 $f$ ，其中 $f [i]$ 表示字符串 $s$ 的前 $i$ 个字符与字符串 $t$ 的前 $i$ 个字符的 ASCII 码值的差的绝对值之和。这样，我们就可以通过 $f [j + 1] - f [i]$ 来计算字符串 $s$ 的第 $i$ 个字符到第 $j$ 个字符的 ASCII 码值的差的绝对值之和，其中 $0 \leq i \leq j < n$ 。

注意到长度具有单调性，即如果存在长度为 $x$ 的子串满足条件，那么长度为 $x - 1$ 的子串也一定满足条件。因此，我们可以使用二分查找的方法来求解最大长度。

我们定义函数 $c h e c k (x)$ ，表示是否存在长度为 $x$ 的子串满足条件。在该函数中，我们只需要枚举所有长度为 $x$ 的子串，判断其是否满足条件即可。如果存在满足条件的子串，那么函数返回 true，否则返回 false。

接下来，我们定义二分查找的左边界 $l$ 为 $0$ ，右边界 $r$ 为 $n$ 。在每一步中，我们令 $m i d = ⌊ \frac{l + r + 1}{2} ⌋$ ，如果函数 $c h e c k (m i d)$ 的返回值为 true，那么我们将左边界更新为 $m i d$ ，否则我们将右边界更新为 $m i d - 1$ 。在二分查找结束后，我们得到的左边界即为答案。

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

func equalSubstring(s string, t string, maxCost int) int {
	n := len(s)
	f := make([]int, n+1)
	for i, a := range s {
		f[i+1] = f[i] + abs(int(a)-int(t[i]))
	}
	check := func(x int) bool {
		for i := 0; i+x-1 < n; i++ {
			if f[i+x]-f[i] <= maxCost {
				return true
			}
		}
		return false
	}
	l, r := 0, n
	for l < r {
		mid := (l + r + 1) >> 1
		if check(mid) {
			l = mid
		} else {
			r = mid - 1
		}
	}
	return l
}

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

方法二：双指针 · Go 实现

思考

方法一额外需要 $O (n)$ 前缀数组，总时间为 $O (n \log n)$ 。费用非负，窗口右端右移时费用只增，左端右移时费用只减，因此可用双指针在一次扫描中维护最大可行窗口，线性时间且常数空间。

我们可以维护两个指针 $l$ 和 $r$ ，初始时 $l = r = 0$ ；维护一个变量 $cost$ ，表示下标区间 $[l, . . r]$ 之间的 ASCII 码值的差的绝对值之和。在每一步中，我们将 $r$ 向右移动一位，然后更新 $cost = cost + | s [r] - t [r] |$ 。如果 $cost > maxCost$ ，那么我们就循环将 $l$ 向右移动一位，并且减少 $cost$ 的值，直到 $cost \leq maxCost$ 。然后我们更新答案，即 $ans = max (ans, r - l + 1)$ 。

最后返回答案即可。

时间复杂度 $O (n)$ ，其中 $n$ 为字符串 $s$ 的长度。空间复杂度 $O (1)$ 。

func equalSubstring(s string, t string, maxCost int) (ans int) {
	var cost, l int
	for r := range s {
		cost += abs(int(s[r]) - int(t[r]))
		for ; cost > maxCost; l++ {
			cost -= abs(int(s[l]) - int(t[l]))
		}
		ans = max(ans, r-l+1)
	}
	return
}

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

方法三：双指针的另一种写法 · Go 实现

思考

方法二在费用超标时可能把窗口缩短后再拉长，并显式维护答案。题目只要最大长度，可让左指针至多前进、窗口单调变长，最终 $n - l$ 即为该最大长度，省去对 $a n s$ 的更新。

在方法二中，双指针维护的区间可能变短，也可能变长，由于题目只需要求出最大长度，我们可以维护一个单调变长的区间。

具体地，我们用两个指针 $l$ 和 $r$ 指向区间的左右端点，初始时 $l = r = 0$ 。在每一步中，我们将 $r$ 向右移动一位，然后更新 $cost = cost + | s [r] - t [r] |$ 。如果 $cost > maxCost$ ，那么我们就将 $l$ 向右移动一位，并且减少 $cost$ 的值。

最后返回 $n - l$ 即可。

时间复杂度 $O (n)$ ，其中 $n$ 为字符串 $s$ 的长度。空间复杂度 $O (1)$ 。

func equalSubstring(s string, t string, maxCost int) int {
	n := len(s)
	var cost, l int
	for r := range s {
		cost += abs(int(s[r]) - int(t[r]))
		if cost > maxCost {
			cost -= abs(int(s[l]) - int(t[l]))
			l++
		}
	}
	return n - l
}

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

力扣原题 · Doocs 题解来源

1213. 三个有序数组的交集 🔒

简单2 种解法

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

题目、示例与约束

给出三个均为 严格递增排列 的整数数组 arr1，arr2 和 arr3。返回一个由仅在这三个数组中 同时出现 的整数所构成的有序数组。

示例 1：

输入: arr1 = [1,2,3,4,5], arr2 = [1,2,5,7,9], arr3 = [1,3,4,5,8]
输出: [1,5]
解释: 只有 1 和 5 同时在这三个数组中出现.

示例 2:

输入: arr1 = [197,418,523,876,1356], arr2 = [501,880,1593,1710,1870], arr3 = [521,682,1337,1395,1764]
输出: []

提示：

1 <= arr1.length, arr2.length, arr3.length <= 1000
1 <= arr1[i], arr2[i], arr3[i] <= 2000

方法一：计数 · Go 实现

思考

三数组均已有序且长度不超过 $1000$ ，值域在 $2000$ 以内。将三个数组一并计数后，值为 $3$ 的元素即公共元素；因各数组内部元素互不相同，该计数不会被同一数组重复抬高。按 $a r r 1$ 的顺序输出即可保持升序。

遍历三个数组，统计每个数字出现的次数，然后遍历任意一个数组，若某个数字出现的次数为 $3$ ，则将其加入结果数组。

时间复杂度 $O (n)$ ，空间复杂度 $O (m)$ 。其中 $n$ 和 $m$ 分别为数组的长度和数组中数字的范围。

func arraysIntersection(arr1 []int, arr2 []int, arr3 []int) (ans []int) {
	cnt := [2001]int{}
	for _, x := range arr1 {
		cnt[x]++
	}
	for _, x := range arr2 {
		cnt[x]++
	}
	for _, x := range arr3 {
		cnt[x]++
		if cnt[x] == 3 {
			ans = append(ans, x)
		}
	}
	return
}

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

思考

计数需要与值域成正比的额外数组。三个数组已有序，可在 $a r r 2$ 、 $a r r 3$ 上二分判断 $a r r 1$ 的每个值是否存在，额外空间降为常数，时间变为 $O (n \log n)$ 。

遍历第一个数组，对于其中的每个数字，使用二分查找在第二个数组和第三个数组中查找该数字，若都找到，则将该数字加入结果数组。

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

func arraysIntersection(arr1 []int, arr2 []int, arr3 []int) (ans []int) {
	for _, x := range arr1 {
		i := sort.SearchInts(arr2, x)
		j := sort.SearchInts(arr3, x)
		if i < len(arr2) && j < len(arr3) && arr2[i] == x && arr3[j] == x {
			ans = append(ans, x)
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1231. 分享巧克力 🔒

困难1 种解法

标签：数组、二分查找

题目、示例与约束

你有一大块巧克力，它由一些甜度不完全相同的小块组成。我们用数组 sweetness 来表示每一小块的甜度。

你打算和 K 名朋友一起分享这块巧克力，所以你需要将切割 K 次才能得到 K+1 块，每一块都由一些连续的小块组成。

为了表现出你的慷慨，你将会吃掉 总甜度最小 的一块，并将其余几块分给你的朋友们。

请找出一个最佳的切割策略，使得你所分得的巧克力 总甜度最大，并返回这个 最大总甜度。

示例 1：

输入：sweetness = [1,2,3,4,5,6,7,8,9], K = 5
输出：6
解释：你可以把巧克力分成 [1,2,3], [4,5], [6], [7], [8], [9]。

示例 2：

输入：sweetness = [5,6,7,8,9,1,2,3,4], K = 8
输出：1
解释：只有一种办法可以把巧克力分成 9 块。

示例 3：

输入：sweetness = [1,2,2,1,2,2,1,2,2], K = 2
输出：5
解释：你可以把巧克力分成 [1,2,2], [1,2,2], [1,2,2]。

提示：

0 <= K < sweetness.length <= 10^4
1 <= sweetness[i] <= 10^5

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

思考

要把巧克力分成 $k + 1$ 段并最大化自己那一段的最小甜度。 $n \leq 10^{4}$ ，枚举切点不可行。若最小甜度 $x$ 可达，则更小的阈值也可达，具有单调性。

判定时从左到右累加，每凑满 $x$ 就切一刀；能切出多于 $k$ 段（自己再加 $k$ 位朋友）则 $x$ 可行。在 $[0, \sum s w e e t n e s s]$ 上二分最大可行 $x$ 。贪心切分保证判定正确：尽早成段只会留下更多剩余去凑后面的段。

我们注意到，如果我们能吃到一块甜度为 $x$ 的巧克力，那么甜度小于等于 $x$ 的巧克力也都能吃到。这存在着单调性，因此，我们可以使用二分查找，找到最大的满足条件的 $x$ 。

我们定义二分查找的左边界 $l = 0$ ，右边界 $r = \sum_{i = 0}^{n - 1} s w e e t n e s s [i]$ 。每一次，我们取 $l$ 和 $r$ 的中间值 $m i d$ ，然后判断能否吃到一块甜度为 $m i d$ 的巧克力。如果能吃到，那么我们就尝试吃掉甜度更大的巧克力，即令 $l = m i d$ ；否则，我们就尝试吃掉甜度更小的巧克力，即令 $r = m i d - 1$ 。在二分查找结束后，我们返回 $l$ 即可。

问题的关键在于，我们如何判断能否吃到一块甜度为 $x$ 的巧克力。我们可以使用贪心的思想，从左到右遍历数组，每次累加当前的甜度，当累加的甜度大于等于 $x$ 时，那么巧克力数 $c n t$ 加 $1$ ，并将累加的甜度清零。最后判断 $c n t$ 是否大于 $k$ 即可。

时间复杂度 $O (n \times \log \sum_{i = 0}^{n - 1} s w e e t n e s s [i])$ ，空间复杂度 $O (1)$ 。其中 $n$ 是数组的长度。

func maximizeSweetness(sweetness []int, k int) int {
	l, r := 0, 0
	for _, v := range sweetness {
		r += v
	}
	check := func(x int) bool {
		s, cnt := 0, 0
		for _, v := range sweetness {
			s += v
			if s >= x {
				s = 0
				cnt++
			}
		}
		return cnt > k
	}
	for l < r {
		mid := (l + r + 1) >> 1
		if check(mid) {
			l = mid
		} else {
			r = mid - 1
		}
	}
	return l
}

力扣原题 · Doocs 题解来源

1237. 找出给定方程的正整数解

中等2 种解法

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

题目、示例与约束

给你一个函数 f(x, y) 和一个目标结果 z，函数公式未知，请你计算方程 f(x,y) == z 所有可能的正整数数对 x 和 y。满足条件的结果数对可以按任意顺序返回。

尽管函数的具体式子未知，但它是单调递增函数，也就是说：

f(x, y) < f(x + 1, y)
f(x, y) < f(x, y + 1)

函数接口定义如下：

interface CustomFunction {
public:
  // Returns some positive integer f(x, y) for two positive integers x and y based on a formula.
  int f(int x, int y);
};

你的解决方案将按如下规则进行评判：

判题程序有一个由 CustomFunction 的 9 种实现组成的列表，以及一种为特定的 z 生成所有有效数对的答案的方法。
判题程序接受两个输入：function_id（决定使用哪种实现测试你的代码）以及目标结果 z 。
判题程序将会调用你实现的 findSolution 并将你的结果与答案进行比较。
如果你的结果与答案相符，那么解决方案将被视作正确答案，即 Accepted 。

示例 1：

输入：function_id = 1, z = 5
输出：[[1,4],[2,3],[3,2],[4,1]]
解释：function_id = 1 暗含的函数式子为 f(x, y) = x + y
以下 x 和 y 满足 f(x, y) 等于 5：
x=1, y=4 -> f(1, 4) = 1 + 4 = 5
x=2, y=3 -> f(2, 3) = 2 + 3 = 5
x=3, y=2 -> f(3, 2) = 3 + 2 = 5
x=4, y=1 -> f(4, 1) = 4 + 1 = 5

示例 2：

输入：function_id = 2, z = 5
输出：[[1,5],[5,1]]
解释：function_id = 2 暗含的函数式子为 f(x, y) = x * y
以下 x 和 y 满足 f(x, y) 等于 5：
x=1, y=5 -> f(1, 5) = 1 * 5 = 5
x=5, y=1 -> f(5, 1) = 5 * 1 = 5

提示：

1 <= function_id <= 9
1 <= z <= 100
题目保证 f(x, y) == z 的解处于 1 <= x, y <= 1000 的范围内。
在 1 <= x, y <= 1000 的前提下，题目保证 f(x, y) 是一个 32 位有符号整数。

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

思考

$f$ 对两个自变量均严格递增， $z \leq 100$ 且解在 $1 \dots 1000$ 。双重线性枚举最坏 $10^{6}$ 次调用，可以接受但可再降。固定 $x$ 后 $f (x, \cdot)$ 单调，可在 $y$ 上二分定位等于 $z$ 的位置。

对每个 $x$ 二分 $y$ ，命中则记录。单调性把内层从线性变成对数。

根据题目我们可以知道，函数 $f (x, y)$ 是单调递增函数，因此，我们可以枚举 $x$ ，然后在 $[1, . . . z]$ 中二分查找 $y$ ，使得 $f (x, y) = z$ 。如果找到了，就将 $(x, y)$ 加入答案中。

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

/**
 * This is the declaration of customFunction API.
 * @param  x    int
 * @param  x    int
 * @return 	    Returns f(x, y) for any given positive integers x and y.
 *			    Note that f(x, y) is increasing with respect to both x and y.
 *              i.e. f(x, y) < f(x + 1, y), f(x, y) < f(x, y + 1)
 */

func findSolution(customFunction func(int, int) int, z int) (ans [][]int) {
	for x := 1; x <= 1000; x++ {
		y := 1 + sort.Search(999, func(y int) bool { return customFunction(x, y+1) >= z })
		if customFunction(x, y) == z {
			ans = append(ans, []int{x, y})
		}
	}
	return
}

方法二：双指针 · Go 实现

思考

每个 $x$ 各做一次二分，调用次数仍带对数因子。从 $(1, 1000)$ 出发：值偏小只能增大 $x$ （再减小 $y$ 会更小），值偏大只能减小 $y$ 。相等则收入并同时移动两端。总调用 $O (z)$ 级，利用了双单调性。

我们可以定义两个指针 $x$ 和 $y$ ，初始时 $x = 1$ , $y = z$ 。

如果 $f (x, y) = z$ ，我们将 $(x, y)$ 加入答案中，然后 $x \leftarrow x + 1$ , $y \leftarrow y - 1$ ；
如果 $f (x, y) < z$ ，此时对任意的 $y^{'} < y$ ，都有 $f (x, y^{'}) < f (x, y) < z$ ，因此我们不能将 $y$ 减小，只能将 $x$ 增大，所以 $x \leftarrow x + 1$ ；
如果 $f (x, y) > z$ ，此时对任意的 $x^{'} > x$ ，都有 $f (x^{'}, y) > f (x, y) > z$ ，因此我们不能将 $x$ 增大，只能将 $y$ 减小，所以 $y \leftarrow y - 1$ 。

循环结束后，返回答案。

时间复杂度 $O (n)$ ，其中 $n$ 是 $z$ 的值，空间复杂度 $O (1)$ 。

/**
 * This is the declaration of customFunction API.
 * @param  x    int
 * @param  x    int
 * @return 	    Returns f(x, y) for any given positive integers x and y.
 *			    Note that f(x, y) is increasing with respect to both x and y.
 *              i.e. f(x, y) < f(x + 1, y), f(x, y) < f(x, y + 1)
 */

func findSolution(customFunction func(int, int) int, z int) (ans [][]int) {
	x, y := 1, 1000
	for x <= 1000 && y > 0 {
		t := customFunction(x, y)
		if t < z {
			x++
		} else if t > z {
			y--
		} else {
			ans = append(ans, []int{x, y})
			x, y = x+1, y-1
		}
	}
	return
}

力扣原题 · Doocs 题解来源

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

中等1 种解法

标签：数组、二分查找

题目、示例与约束

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

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

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

题目保证一定有解。

示例 1：

输入：nums = [1,2,5,9], threshold = 6
输出：5
解释：如果除数为 1 ，我们可以得到和为 17 （1+2+5+9）。
如果除数为 4 ，我们可以得到和为 7 (1+1+2+3) 。如果除数为 5 ，和为 5 (1+1+1+2)。

示例 2：

输入：nums = [2,3,5,7,11], threshold = 11
输出：3

示例 3：

输入：nums = [19], threshold = 5
输出：4

提示：

1 <= nums.length <= 5 * 10^4
1 <= nums[i] <= 10^6
nums.length <= threshold <= 10^6

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

思考

除数越大，向上取整之和越小，存在单调性。 $n \leq 5 \times 10^{4}$ ，枚举除数不可行。在 $[1, max n u m s]$ 上二分最小 $v$ ，使 $\sum ⌈ n u m s_{i} / v ⌉ \leq t h r e s h o l d$ 。判定一遍线性扫描。

我们注意到，对于一个数字 $v$ ，如果将 $n u m s$ 中的每个数字都除以 $v$ 的结果之和小于等于 $t h r e s h o l d$ ，那么所有大于 $v$ 的值都满足条件。这存在着单调性，因此我们可以使用二分查找的方法找到最小的满足条件的 $v$ 。

我们定义二分查找的左边界 $l = 1$ , $r = max (n u m s)$ ，每次取 $m i d = (l + r) / 2$ ，计算 $n u m s$ 中每个数字除以 $m i d$ 的结果之和 $s$ ，如果 $s$ 小于等于 $t h r e s h o l d$ ，那么说明 $m i d$ 满足条件，我们将 $r$ 更新为 $m i d$ ，否则将 $l$ 更新为 $m i d + 1$ 。

最后返回 $l$ 即可。

时间复杂度 $O (n \times \log M)$ ，其中 $n$ 是数组 $n u m s$ 的长度，而 $M$ 是数组 $n u m s$ 中的最大值。空间复杂度 $O (1)$ 。

func smallestDivisor(nums []int, threshold int) int {
	return sort.Search(slices.Max(nums), func(v int) bool {
		v++
		s := 0
		for _, x := range nums {
			s += (x + v - 1) / v
		}
		return s <= threshold
	}) + 1
}

力扣原题 · Doocs 题解来源

1292. 元素和小于等于阈值的正方形的最大边长

中等1 种解法

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

题目、示例与约束

给你一个大小为 m x n 的矩阵 mat 和一个整数阈值 threshold。

请你返回元素总和小于或等于阈值的正方形区域的最大边长；如果没有这样的正方形区域，则返回 0 。

示例 1：

输入：mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4
输出：2
解释：总和小于或等于 4 的正方形的最大边长为 2，如图所示。

示例 2：

输入：mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1
输出：0

提示：

m == mat.length
n == mat[i].length
1 <= m, n <= 300
0 <= mat[i][j] <= 10⁴
0 <= threshold <= 10⁵

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

思考

正方形区域和随边长增大而增大（元素非负），存在单调性。 $m, n \leq 300$ ，枚举边长再扫左上角若每次求和为 $O (k^{2})$ 则过慢。二维前缀和使任意正方形求和 $O (1)$ ，再对边长二分。

判定函数枚举左上角，用前缀和比较阈值。二分找最大可行边长。

我们可以先预处理得到二维前缀和数组 $s$ ，其中 $s [i + 1] [j + 1]$ 表示矩阵 $m a t$ 中从 $(0, 0)$ 到 $(i, j)$ 的元素和，那么对于任意的正方形区域，我们都可以在 $O (1)$ 的时间内得到其元素和。

接下来，我们可以使用二分查找的方法得到最大的边长。我们枚举正方形的边长 $k$ ，然后枚举正方形的左上角位置 $(i, j)$ ，那么我们可以得到正方形的元素和 $v$ ，如果 $v \leq t h r e s h o l d$ ，那么说明存在边长为 $k$ 的正方形区域的元素和小于或等于阈值，否则不存在。

时间复杂度 $O (m \times n \times \log min (m, n))$ ，空间复杂度 $O (m \times n)$ 。

func maxSideLength(mat [][]int, threshold int) int {
	m, n := len(mat), len(mat[0])
	s := make([][]int, m+1)
	for i := range s {
		s[i] = make([]int, n+1)
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + mat[i-1][j-1]
		}
	}
	check := func(k int) bool {
		for i := 0; i < m-k+1; i++ {
			for j := 0; j < n-k+1; j++ {
				if s[i+k][j+k]-s[i][j+k]-s[i+k][j]+s[i][j] <= threshold {
					return true
				}
			}
		}
		return false
	}
	l, r := 0, min(m, n)
	for l < r {
		mid := (l + r + 1) >> 1
		if check(mid) {
			l = mid
		} else {
			r = mid - 1
		}
	}
	return l
}

力扣原题 · Doocs 题解来源

1300. 转变数组后最接近目标值的数组和

中等1 种解法

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

题目、示例与约束

给你一个整数数组 arr 和一个目标值 target ，请你返回一个整数 value ，使得将数组中所有大于 value 的值变成 value 后，数组的和最接近 target （最接近表示两者之差的绝对值最小）。

如果有多种使得和最接近 target 的方案，请你返回这些整数中的最小值。

请注意，答案不一定是 arr 中的数字。

示例 1：

输入：arr = [4,9,3], target = 10
输出：3
解释：当选择 value 为 3 时，数组会变成 [3, 3, 3]，和为 9 ，这是最接近 target 的方案。

示例 2：

输入：arr = [2,3,5], target = 10
输出：5

示例 3：

输入：arr = [60864,25176,27249,21296,20204], target = 56803
输出：11361

提示：

1 <= arr.length <= 10^4
1 <= arr[i], target <= 10^5

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

思考

若对每个候选 $value$ 都扫描一遍数组求转变后的和，则复杂度为 $O (n \times M)$ 。其中 $n \leq 10^{4}$ 、 $M \leq 10^{5}$ ，难以稳定通过。

转变后的和只取决于「不超过 $value$ 的部分原样保留、超过的部分一律改成 $value$ 」。将数组排序后，分界点是一段前缀，可用二分定位，前缀和一次算出保留部分。因此按 $0$ 到 $max (arr)$ 枚举 $value$ ，每次 $O (\log n)$ 求转变和并维护与 $target$ 的最小绝对差；差值相同时取更小的 $value$ 。

我们注意到，题目中要把所有大于 value 的值变成 value，并且求和，因此我们可以考虑先对数组 arr 进行排序，然后求出前缀和数组 $s$ ，其中 $s [i]$ 表示数组前 $i$ 个元素之和。

接下来，我们可以从小到大枚举所有 value 值，对于每个 value，我们可以通过二分查找找到数组中第一个大于 value 的元素的下标 $i$ ，此时数组中大于 value 的元素个数为 $n - i$ ，因此数组中小于等于 value 的元素个数为 $i$ ，此时数组中小于等于 value 的元素之和为 $s [i]$ ，数组中大于 value 的元素之和为 $(n - i) \times value$ ，因此数组中所有元素之和为 $s [i] + (n - i) \times value$ 。如果 $s [i] + (n - i) \times value$ 与 target 的差的绝对值小于当前的最小差值 diff，则更新 diff 和 ans。

枚举完所有 value 后，即可得到最终答案 ans。

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

func findBestValue(arr []int, target int) (ans int) {
	sort.Ints(arr)
	n := len(arr)
	s := make([]int, n+1)
	mx := slices.Max(arr)
	for i, x := range arr {
		s[i+1] = s[i] + x
	}
	diff := 1 << 30
	for value := 0; value <= mx; value++ {
		i := sort.SearchInts(arr, value+1)
		d := abs(s[i] + (n-i)*value - target)
		if diff > d {
			diff = d
			ans = value
		}
	}
	return
}

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

力扣原题 · Doocs 题解来源

1337. 矩阵中战斗力最弱的 K 行

简单1 种解法

标签：数组、二分查找、矩阵、排序、堆（优先队列）

题目、示例与约束

给你一个大小为 m * n 的矩阵 mat，矩阵由若干军人和平民组成，分别用 1 和 0 表示。

请你返回矩阵中战斗力最弱的 k 行的索引，按从最弱到最强排序。

如果第 i 行的军人数量少于第 j 行，或者两行军人数量相同但 i 小于 j，那么我们认为第 i 行的战斗力比第 j 行弱。

军人总是排在一行中的靠前位置，也就是说 1 总是出现在 0 之前。

示例 1：

输入：mat = 
[[1,1,0,0,0],
 [1,1,1,1,0],
 [1,0,0,0,0],
 [1,1,0,0,0],
 [1,1,1,1,1]], 
k = 3
输出：[2,0,3]
解释：
每行中的军人数目：
行 0 -> 2 
行 1 -> 4 
行 2 -> 1 
行 3 -> 2 
行 4 -> 5 
从最弱到最强对这些行排序后得到 [2,0,3,1,4]

示例 2：

输入：mat = 
[[1,0,0,0],
 [1,1,1,1],
 [1,0,0,0],
 [1,0,0,0]], 
k = 2
输出：[0,2]
解释： 
每行中的军人数目：
行 0 -> 1 
行 1 -> 4 
行 2 -> 1 
行 3 -> 1 
从最弱到最强对这些行排序后得到 [0,2,3,1]

提示：

m == mat.length
n == mat[i].length
2 <= n, m <= 100
1 <= k <= m
matrix[i][j] 不是 0 就是 1

方法一 · Go 实现

思考

行按军人数量升序、行号升序取前 $k$ 行。每行 $1$ 在左、 $0$ 在右，军人个数等于首次 $0$ 的位置。将行反转后二分 $0$ 的右界，得到军人数量；再按该数量对行号排序，截取前 $k$ 个。

func kWeakestRows(mat [][]int, k int) []int {
	m, n := len(mat), len(mat[0])
	res := make([]int, m)
	var idx []int
	for i, row := range mat {
		idx = append(idx, i)
		left, right := 0, n
		for left < right {
			mid := (left + right) >> 1
			if row[mid] == 0 {
				right = mid
			} else {
				left = mid + 1
			}
		}
		res[i] = left
	}
	sort.Slice(idx, func(i, j int) bool {
		return res[idx[i]] < res[idx[j]] || (res[idx[i]] == res[idx[j]] && idx[i] < idx[j])
	})
	return idx[:k]
}

力扣原题 · Doocs 题解来源

1346. 检查整数及其两倍数是否存在

简单1 种解法

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

题目、示例与约束

给你一个整数数组 arr，请你检查是否存在两个整数 N 和 M，满足 N 是 M 的两倍（即，N = 2 * M）。

更正式地，检查是否存在两个下标 i 和 j 满足：

i != j
0 <= i, j < arr.length
arr[i] == 2 * arr[j]

示例 1：

输入：arr = [10,2,5,3]
输出：true
解释：N = 10 是 M = 5 的两倍，即 10 = 2 * 5 。

示例 2：

输入：arr = [7,1,14,11]
输出：true
解释：N = 14 是 M = 7 的两倍，即 14 = 2 * 7 。

示例 3：

输入：arr = [3,1,7,11]
输出：false
解释：在该情况下不存在 N 和 M 满足 N = 2 * M 。

提示：

2 <= arr.length <= 500
-10^3 <= arr[i] <= 10^3

方法一：哈希表 · Go 实现

思考

是否存在 $i \neq j$ 使 $a r r [i] = 2 a r r [j]$ 。双重循环在 $n \leq 500$ 可过，但一遍哈希即可：扫描时若 $2 x$ 或（偶数时） $x / 2$ 已出现则成功，否则把 $x$ 放入集合。集合只含左侧元素，自然保证下标不同。

我们定义一个哈希表 $s$ ，用于记录访问过的元素。

遍历数组 $a r r$ ，对于每个元素 $x$ ，如果 $x$ 的两倍或者 $x$ 的一半在哈希表 $s$ 中，那么返回 true。否则将 $x$ 加入哈希表 $s$ 。

若遍历结束后没有找到满足条件的元素，返回 false。

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

func checkIfExist(arr []int) bool {
	s := map[int]bool{}
	for _, x := range arr {
		if s[x*2] || (x%2 == 0 && s[x/2]) {
			return true
		}
		s[x] = true
	}
	return false
}

力扣原题 · Doocs 题解来源

1351. 统计有序矩阵中的负数

简单1 种解法

标签：数组、二分查找、矩阵

题目、示例与约束

给你一个 m * n 的矩阵 grid，矩阵中的元素无论是按行还是按列，都以非严格递减顺序排列。请你统计并返回 grid 中负数的数目。

示例 1：

输入：grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
输出：8
解释：矩阵中共有 8 个负数。

示例 2：

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

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 100
-100 <= grid[i][j] <= 100

进阶：你可以设计一个时间复杂度为 O(n + m) 的解决方案吗？

方法一：从左下角开始遍历 · Go 实现

思考

每行每列非严格递减，统计负数个数。逐格扫描为 $O (m n)$ 。左下角是「当前行最小、当前列最大」的分界：该格非负则本行左侧皆非负，右移；为负则本行从这里到右端全负，计入 $n - j$ 后上移。行列各走一遍，复杂度 $O (m + n)$ 。

由于矩阵是按行和按列非严格递减排序的，我们可以从矩阵的左下角开始遍历，记当前位置为 $(i, j)$ 。

如果当前位置的元素大于等于 $0$ ，说明该行的前面所有元素也都大于等于 $0$ ，因此我们将列索引 $j$ 向右移动一位，即 $j = j + 1$ 。

如果当前位置的元素小于 $0$ ，说明该列的当前元素以及其右侧的所有元素都是负数，因此我们可以将负数的数量增加 $n - j$ （其中 $n$ 是矩阵的列数），然后将行索引 $i$ 向上移动一位，即 $i = i - 1$ 。

我们重复上述过程，直到行索引 $i$ 小于 $0$ 或列索引 $j$ 大于等于 $n$ 。最终，负数的数量即为答案。

时间复杂度 $O (m + n)$ ，其中 $m$ 和 $n$ 分别是矩阵的行数和列数。空间复杂度 $O (1)$ 。

func countNegatives(grid [][]int) (ans int) {
	m := len(grid)
	n := len(grid[0])
	i := m - 1
	j := 0
	for i >= 0 && j < n {
		if grid[i][j] >= 0 {
			j++
		} else {
			ans += n - j
			i--
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1385. 两个数组间的距离值

简单1 种解法

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

题目、示例与约束

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

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

示例 1：

输入：arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2
输出：2
解释：
对于 arr1[0]=4 我们有：
|4-10|=6 > d=2 
|4-9|=5 > d=2 
|4-1|=3 > d=2 
|4-8|=4 > d=2 
所以 arr1[0]=4 符合距离要求

对于 arr1[1]=5 我们有：
|5-10|=5 > d=2 
|5-9|=4 > d=2 
|5-1|=4 > d=2 
|5-8|=3 > d=2
所以 arr1[1]=5 也符合距离要求

对于 arr1[2]=8 我们有：
|8-10|=2 <= d=2
|8-9|=1 <= d=2
|8-1|=7 > d=2
|8-8|=0 <= d=2
存在距离小于等于 2 的情况，不符合距离要求 

故而只有 arr1[0]=4 和 arr1[1]=5 两个符合距离要求，距离值为 2

示例 2：

输入：arr1 = [1,4,2,3], arr2 = [-4,-3,6,10,20,30], d = 3
输出：2

示例 3：

输入：arr1 = [2,1,100,3], arr2 = [-5,-2,10,-3,7], d = 6
输出：1

提示：

1 <= arr1.length, arr2.length <= 500
-10^3 <= arr1[i], arr2[j] <= 10^3
0 <= d <= 100

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

思考

统计 $a r r 1$ 中与 $a r r 2$ 所有元素距离都大于 $d$ 的个数。双重扫描为 $O (m n)$ 。对 $a r r 2$ 排序后，每个 $x$ 只需看是否存在落在 $[x - d, x + d]$ 内的值：二分第一个 $\geq x - d$ 的位置，若越界或该值已大于 $x + d$ ，则 $x$ 合法。

我们可以先对数组 $arr2$ 排序，然后对于数组 $arr1$ 中的每个元素 $x$ ，使用二分查找，找到数组 $arr2$ 中第一个大于等于 $x - d$ 的元素，如果元素存在，且小于等于 $x + d$ ，则说明不符合距离要求，否则说明符合距离要求。我们将符合距离要求的元素个数累加，即为答案。

时间复杂度 $O ((m + n) \times \log n)$ ，空间复杂度 $O (\log n)$ 。其中 $m$ 和 $n$ 分别是数组 $arr1$ 和 $arr2$ 的长度。

func findTheDistanceValue(arr1 []int, arr2 []int, d int) (ans int) {
	sort.Ints(arr2)
	for _, x := range arr1 {
		i := sort.SearchInts(arr2, x-d)
		if i == len(arr2) || arr2[i] > x+d {
			ans++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1428. 至少有一个 1 的最左端列 🔒

中等1 种解法

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

题目、示例与约束

行排序二进制矩阵 表示所有元素都是 0 或 1，并且矩阵的每一行都以非递减排序。

给定一个 行排序二进制矩阵 binaryMatrix，返回至少包含一个 1 的 最左端列 的索引（从 0 开始）。如果这样的列不存在，返回 -1。

您不能直接访问该二进制矩阵。你只可以通过 BinaryMatrix 接口来访问。

BinaryMatrix.get(row, col) 返回位于索引 (row, col) （从 0 开始）的元素。
BinaryMatrix.dimensions() 返回含有 2 个元素的列表 [rows, cols]，表示这是一个 rows * cols的矩阵。

如果提交的答案调用 BinaryMatrix.get 超过 1000 次，则该答案会被判定为错误答案。提交任何试图规避判定机制的答案将会被取消资格。

下列示例中， mat 为给定的二进制矩阵。您不能直接访问该矩阵。

示例 1:

输入: mat = [[0,0],[1,1]]
输出: 0

示例 2:

输入: mat = [[0,0],[0,1]]
输出: 1

示例 3:

输入: mat = [[0,0],[0,0]]
输出: -1

提示:

rows == mat.length
cols == mat[i].length
1 <= rows, cols <= 100
mat[i][j] 只会是 0 或 1。
mat[i] 已按非递减顺序排序。

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

思考

矩阵每行非递减，且访问次数受限，不能整表扫描。每一行中第一个 $1$ 的位置可用二分在 $O (\log n)$ 次 get 内求出。

对所有行取这些列号的最小值；若没有任何 $1$ ，则返回 $- 1$ 。

我们先调用 BinaryMatrix.dimensions() 得到矩阵的行数 $m$ 和列数 $n$ ，然后对于每一行，我们使用二分查找来找到最左边的 $1$ 所在的列数 $j$ ，找出所有行中最小的满足 $j$ 的值即为答案。如果不存在这样的列，则返回 $- 1$ 。

时间复杂度 $O (m \times \log n)$ ，其中 $m$ 和 $n$ 分别是矩阵的行数和列数。需要遍历每一行，每一行内使用二分查找，时间复杂度为 $O (\log n)$ 。空间复杂度 $O (1)$ 。

/**
 * // This is the BinaryMatrix's API interface.
 * // You should not implement it, or speculate about its implementation
 * type BinaryMatrix struct {
 *     Get func(int, int) int
 *     Dimensions func() []int
 * }
 */

func leftMostColumnWithOne(binaryMatrix BinaryMatrix) int {
	e := binaryMatrix.Dimensions()
	m, n := e[0], e[1]
	ans := n
	for i := 0; i < m; i++ {
		l, r := 0, n
		for l < r {
			mid := (l + r) >> 1
			if binaryMatrix.Get(i, mid) == 1 {
				r = mid
			} else {
				l = mid + 1
			}
		}
		ans = min(ans, l)
	}
	if ans >= n {
		return -1
	}
	return ans
}

力扣原题 · Doocs 题解来源

1439. 有序矩阵中的第 k 个最小数组和

困难1 种解法

标签：数组、二分查找、矩阵、堆（优先队列）

题目、示例与约束

给你一个 m * n 的矩阵 mat，以及一个整数 k ，矩阵中的每一行都以非递减的顺序排列。

你可以从每一行中选出 1 个元素形成一个数组。返回所有可能数组中的第 k 个最小数组和。

示例 1：

输入：mat = [[1,3,11],[2,4,6]], k = 5
输出：7
解释：从每一行中选出一个元素，前 k 个和最小的数组分别是：
[1,2], [1,4], [3,2], [3,4], [1,6]。其中第 5 个的和是 7 。

示例 2：

输入：mat = [[1,3,11],[2,4,6]], k = 9
输出：17

示例 3：

输入：mat = [[1,10,10],[1,4,5],[2,3,6]], k = 7
输出：9
解释：从每一行中选出一个元素，前 k 个和最小的数组分别是：
[1,1,2], [1,1,3], [1,4,2], [1,4,3], [1,1,6], [1,5,2], [1,5,3]。其中第 7 个的和是 9 。

示例 4：

输入：mat = [[1,1,10],[2,2,9]], k = 7
输出：12

提示：

m == mat.length
n == mat.length[i]
1 <= m, n <= 40
1 <= k <= min(200, n ^ m)
1 <= mat[i][j] <= 5000
mat[i] 是一个非递减数组

方法一：逐行遍历 + 排序 · Go 实现

思考

每行选一个数求和， $n^{m}$ 种组合而 $k \leq 200$ 。只需保留前 $k$ 小的部分和。行已有序，与下一行相加时只需用到该行前 $k$ 个元素。

设 $p r e$ 为已处理行的前 $k$ 小和，与当前行做笛卡尔加后排序截断前 $k$ 项。处理完所有行后 $p r e [k - 1]$ 即为答案。

根据题目描述，我们需要找出前 $m$ 行的所有可能数组中的第 $k$ 个最小数组和。

如果我们能够找出前 $m - 1$ 行的所有可能数组中的前 $k$ 个最小数组和，那么我们可以将第 $m$ 行的每个元素与前 $m - 1$ 行的前 $k$ 个最小数组和相加，将得到的所有结果排序后，取前 $k$ 个最小值，即为前 $m$ 行的所有可能数组中的前 $k$ 个最小值。

因此，我们可以定义一个数组 $p r e$ ，用于存储此前遍历到的行的前 $k$ 个最小数组和，初始时 $p r e$ 只有一个元素 $0$ 。

然后，我们遍历 $m a t$ 的每一行 $c u r$ ，将 $c u r$ 中的每个元素与 $p r e$ 中的每个元素相加，将得到的所有结果排序后，取前 $k$ 个最小值作为新的 $p r e$ 。继续遍历下一行，直到遍历完所有行。

最后返回 $p r e$ 中的第 $k$ 个数（下标 $k - 1$ ）即可。

时间复杂度 $O (m \times n \times k \times \log (n \times k))$ ，空间复杂度 $O (n \times k)$ 。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

func kthSmallest(mat [][]int, k int) int {
	pre := []int{0}
	for _, row := range mat {
		cur := []int{}
		for _, a := range pre {
			for _, b := range row {
				cur = append(cur, a+b)
			}
		}
		sort.Ints(cur)
		pre = cur[:min(k, len(cur))]
	}
	return pre[k-1]
}

力扣原题 · Doocs 题解来源

1482. 制作 m 束花所需的最少天数

中等1 种解法

标签：数组、二分查找

题目、示例与约束

给你一个整数数组 bloomDay，以及两个整数 m 和 k 。

现需要制作 m 束花。制作花束时，需要使用花园中 相邻的 k 朵花 。

花园中有 n 朵花，第 i 朵花会在 bloomDay[i] 时盛开，恰好可以用于一束花中。

请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1。

示例 1：

输入：bloomDay = [1,10,3,10,2], m = 3, k = 1
输出：3
解释：让我们一起观察这三天的花开过程，x 表示花开，而 _ 表示花还未开。
现在需要制作 3 束花，每束只需要 1 朵。
1 天后：[x, _, _, _, _]   // 只能制作 1 束花
2 天后：[x, _, _, _, x]   // 只能制作 2 束花
3 天后：[x, _, x, _, x]   // 可以制作 3 束花，答案为 3

示例 2：

输入：bloomDay = [1,10,3,10,2], m = 3, k = 2
输出：-1
解释：要制作 3 束花，每束需要 2 朵花，也就是一共需要 6 朵花。而花园中只有 5 朵花，无法满足制作要求，返回 -1 。

示例 3：

输入：bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
输出：12
解释：要制作 2 束花，每束需要 3 朵。
花园在 7 天后和 12 天后的情况如下：
7 天后：[x, x, x, x, _, x, x]
可以用前 3 朵盛开的花制作第一束花。但不能使用后 3 朵盛开的花，因为它们不相邻。
12 天后：[x, x, x, x, x, x, x]
显然，我们可以用不同的方式制作两束花。

示例 4：

输入：bloomDay = [1000000000,1000000000], m = 1, k = 1
输出：1000000000
解释：需要等 1000000000 天才能采到花来制作花束

示例 5：

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

提示：

bloomDay.length == n
1 <= n <= 10^5
1 <= bloomDay[i] <= 10^9
1 <= m <= 10^6
1 <= k <= n

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

思考

天数越大越容易凑齐 $m$ 束，具有单调性。 $n \leq 10^{5}$ 、 $b l o o m D a y_{i} \leq 10^{9}$ ，对天数二分。判定时从左到右数连续已开且长度为 $k$ 的段数是否至少 $m$ 。找不到则返回 $- 1$ 。

根据题目描述，如果一个天数 $t$ 可以满足制作 $m$ 束花，那么对任意 $t^{'} > t$ ，也一定可以满足制作 $m$ 束花。因此，我们可以使用二分查找的方法找到最小的满足制作 $m$ 束花的天数。

我们记花园中最大的开花天数为 $m x$ ，接下来，我们定义二分查找的左边界 $l = 1$ ，右边界 $r = m x + 1$ 。

然后，我们进行二分查找，对于每一个中间值 $mid = \frac{l + r}{2}$ ，我们判断是否可以制作 $m$ 束花。如果可以，我们将右边界 $r$ 更新为 $mid$ ，否则，我们将左边界 $l$ 更新为 $mid + 1$ 。

最终，当 $l = r$ 时，结束二分查找。此时如果 $l > m x$ ，说明无法制作 $m$ 束花，返回 $- 1$ ，否则返回 $l$ 。

因此，问题转换为判断一个天数 $days$ 是否可以制作 $m$ 束花。

我们可以使用一个函数 $check (days)$ 来判断是否可以制作 $m$ 束花。具体地，我们从左到右遍历花园中的每一朵花，如果当前花开的天数小于等于 $days$ ，我们将当前花加入到当前花束中，否则，我们将当前花束清空。当当前花束中的花的数量等于 $k$ 时，我们将当前花束的数量加一，并清空当前花束。最后，我们判断当前花束的数量是否大于等于 $m$ ，如果是，说明可以制作 $m$ 束花，否则，说明无法制作 $m$ 束花。

时间复杂度 $O (n \times \log M)$ ，其中 $n$ 和 $M$ 分别为花园中的花的数量和最大的开花天数，本题中 $M \leq 10^{9}$ 。空间复杂度 $O (1)$ 。

func minDays(bloomDay []int, m int, k int) int {
	mx := slices.Max(bloomDay)
	if l := sort.Search(mx+2, func(days int) bool {
		cnt, cur := 0, 0
		for _, x := range bloomDay {
			if x <= days {
				cur++
				if cur == k {
					cnt++
					cur = 0
				}
			} else {
				cur = 0
			}
		}
		return cnt >= m
	}); l <= mx {
		return l
	}
	return -1

}

力扣原题 · Doocs 题解来源

1498. 满足条件的子序列数目

中等1 种解法

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

题目、示例与约束

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

请你统计并返回 nums 中能满足其最小元素与最大元素的和小于或等于 target 的非空子序列的数目。

由于答案可能很大，请将结果对 10⁹ + 7 取余后返回。

示例 1：

输入：nums = [3,5,6,7], target = 9
输出：4
解释：有 4 个子序列满足该条件。
[3] -> 最小元素 + 最大元素 <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

示例 2：

输入：nums = [3,3,6,8], target = 10
输出：6
解释：有 6 个子序列满足该条件。（nums 中可以有重复数字）
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]

示例 3：

输入：nums = [2,3,3,4,6,7], target = 12
输出：61
解释：共有 63 个非空子序列，其中 2 个不满足条件（[6,7], [7]）
有效序列总数为（63 - 2 = 61）

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁶
1 <= target <= 10⁶

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

思考

子序列只关心最小与最大，排序不改变可组成的最值对。 $n \leq 10^{5}$ ，枚举最小值 $n u m s [i]$ ，二分最大合法 $n u m s [j]$ ，中间元素可任意选，方案为 $2^{j - i}$ 。

预处理二的幂以免重复计算。若 $2 \cdot n u m s [i] > t a r g e t$ ，更大的最小值已不可能。

由于题目中描述的是子序列，并且涉及到最小元素与最大元素的和，因此我们可以先对数组 $nums$ 进行排序。

然后我们枚举最小元素 $nums [i]$ ，对于每个 $nums [i]$ ，我们可以在 $nums [i + 1]$ 到 $nums [n - 1]$ 中找到最大元素 $nums [j]$ ，使得 $nums [i] + nums [j] \leq target$ ，此时满足条件的子序列数目为 $2^{j - i}$ ，其中 $2^{j - i}$ 表示从 $nums [i + 1]$ 到 $nums [j]$ 的所有子序列的数目。我们将所有的子序列数目累加即可。

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

func numSubseq(nums []int, target int) (ans int) {
	sort.Ints(nums)
	n := len(nums)
	f := make([]int, n+1)
	f[0] = 1
	const mod int = 1e9 + 7
	for i := 1; i <= n; i++ {
		f[i] = f[i-1] * 2 % mod
	}
	for i, x := range nums {
		if x*2 > target {
			break
		}
		j := sort.SearchInts(nums[i+1:], target-x+1) + i
		ans = (ans + f[j-i]) % mod
	}
	return
}

力扣原题 · Doocs 题解来源

1508. 子数组和排序后的区间和

中等1 种解法

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

题目、示例与约束

给你一个数组 nums ，它包含 n 个正整数。你需要计算所有非空连续子数组的和，并将它们按升序排序，得到一个新的包含 n * (n + 1) / 2 个数字的数组。

请你返回在新数组中下标为 left 到 right （下标从 1 开始）的所有数字和（包括左右端点）。由于答案可能很大，请你将它对 10^9 + 7 取模后返回。

示例 1：

输入：nums = [1,2,3,4], n = 4, left = 1, right = 5
输出：13 
解释：所有的子数组和为 1, 3, 6, 10, 2, 5, 9, 3, 7, 4 。将它们升序排序后，我们得到新的数组 [1, 2, 3, 3, 4, 5, 6, 7, 9, 10] 。下标从 le = 1 到 ri = 5 的和为 1 + 2 + 3 + 3 + 4 = 13 。

示例 2：

输入：nums = [1,2,3,4], n = 4, left = 3, right = 4
输出：6
解释：给定数组与示例 1 一样，所以新数组为 [1, 2, 3, 3, 4, 5, 6, 7, 9, 10] 。下标从 le = 3 到 ri = 4 的和为 3 + 3 = 6 。

示例 3：

输入：nums = [1,2,3,4], n = 4, left = 1, right = 10
输出：50

提示：

1 <= nums.length <= 10^3
nums.length == n
1 <= nums[i] <= 100
1 <= left <= right <= n * (n + 1) / 2

方法一：模拟 · Go 实现

思考

需要把所有子数组和排序后，求第 $left$ 到第 $right$ 项之和。子数组有 $O (n^{2})$ 个， $n \leq 10^{3}$ ，若再对每个询问区间重新求和会重复劳动，但本题只询问一次。

枚举左端点并维护向右延伸的前缀和，即可在 $O (n^{2})$ 内列出全部子数组和；排序后对指定闭区间求和并对 $10^{9} + 7$ 取模。 $n^{2} \log n$ 的量级可以接受。

我们可以按照题目的要求，生成数组 $arr$ ，然后对数组进行排序，最后求出 $[left - 1, right - 1]$ 范围的所有元素的和，得到结果。

时间复杂度 $O (n^{2} \times \log n)$ ，空间复杂度 $O (n^{2})$ 。其中 $n$ 为题目给定的数组长度。

func rangeSum(nums []int, n int, left int, right int) (ans int) {
	var arr []int
	for i := 0; i < n; i++ {
		s := 0
		for j := i; j < n; j++ {
			s += nums[j]
			arr = append(arr, s)
		}
	}
	sort.Ints(arr)
	const mod int = 1e9 + 7
	for _, x := range arr[left-1 : right] {
		ans = (ans + x) % mod
	}
	return
}

力扣原题 · Doocs 题解来源

1533. 找到最大整数的索引 🔒

中等1 种解法

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

题目、示例与约束

我们有这样一个整数数组 arr ，除了一个最大的整数外，其他所有整数都相等。你不能直接访问该数组，你需要通过 API ArrayReader 来间接访问，这个 API 有以下成员函数：

int compareSub(int l, int r, int x, int y)：其中 0 <= l, r, x, y < ArrayReader.length()， l <= r 且 x <= y。这个函数比较子数组 arr[l..r] 与子数组 arr[x..y] 的和。该函数返回：
- 1 若 arr[l]+arr[l+1]+...+arr[r] > arr[x]+arr[x+1]+...+arr[y] 。
- 0 若 arr[l]+arr[l+1]+...+arr[r] == arr[x]+arr[x+1]+...+arr[y] 。
- -1 若 arr[l]+arr[l+1]+...+arr[r] < arr[x]+arr[x+1]+...+arr[y] 。
int length()：返回数组的长度。

你最多可以调用函数 compareSub() 20 次。你可以认为这两个函数的时间复杂度都为 O(1) 。

返回 arr 中最大整数的索引。

示例 1：

输入: arr = [7,7,7,7,10,7,7,7]
输出: 4
解释: API 的调用如下：
reader.compareSub(0, 0, 1, 1) // 返回 0。比较子数组 (0, 0) 与子数组 (1, 1) （即比较 arr[0] 和 arr[1]）。
因此我们知道 arr[0] 和 arr[1] 不包含最大元素。
reader.compareSub(2, 2, 3, 3) // 返回 0。我们可以排除 arr[2] 和 arr[3]。
reader.compareSub(4, 4, 5, 5) // 返回 1。因此，可以确定 arr[4] 是数组中最大的元素。
注意，我们只调用了 3 次 compareSub，所以这个答案是有效的。

示例 2:

输入: nums = [6,6,12]
输出: 2

提示:

2 <= arr.length <= 5 * 10⁵
1 <= arr[i] <= 100
arr 中除一个最大元素外，其余所有元素都相等。

进阶

如果 arr 中有两个整数比其他数大呢？
如果有一个数比其他数大，另一个数比其他数小呢？

方法一 · Go 实现

思考

数组除一个较大值外全相等，只能通过比较两段区间和来定位，且长度可达 $5 \times 10^{5}$ ，线性次比较不够，必须对数次缩小范围。

将当前区间近似三等分：比较左段 $[t_{1}, t_{2}]$ 与中段 $[t_{2} + 1, t_{3}]$ 。和相等则大数在剩下的右段；左段更大则落在左段；否则落在中段。每次丢掉约三分之一，直至左右端重合。

/**
 * // This is the ArrayReader's API interface.
 * // You should not implement it, or speculate about its implementation
 * type ArrayReader struct {
 * }
 * // Compares the sum of arr[l..r] with the sum of arr[x..y]
 * // return 1 if sum(arr[l..r]) > sum(arr[x..y])
 * // return 0 if sum(arr[l..r]) == sum(arr[x..y])
 * // return -1 if sum(arr[l..r]) < sum(arr[x..y])
 * func (this *ArrayReader) compareSub(l, r, x, y int) int {}
 *
 * // Returns the length of the array
 * func (this *ArrayReader) length() int {}
 */

func getIndex(reader *ArrayReader) int {
	left, right := 0, reader.length()-1
	for left < right {
		t1, t2, t3 := left, left+(right-left)/3, left+(right-left)/3*2+1
		cmp := reader.compareSub(t1, t2, t2+1, t3)
		if cmp == 0 {
			left = t3 + 1
		} else if cmp == 1 {
			right = t2
		} else {
			left, right = t2+1, t3
		}
	}
	return left
}

力扣原题 · Doocs 题解来源

1539. 第 k 个缺失的正整数

简单1 种解法

标签：数组、二分查找

题目、示例与约束

给你一个 严格升序排列 的正整数数组 arr 和一个整数 k 。

请你找到这个数组里第 k 个缺失的正整数。

示例 1：

输入：arr = [2,3,4,7,11], k = 5
输出：9
解释：缺失的正整数包括 [1,5,6,8,9,10,12,13,...] 。第 5 个缺失的正整数为 9 。

示例 2：

输入：arr = [1,2,3,4], k = 2
输出：6
解释：缺失的正整数包括 [5,6,7,...] 。第 2 个缺失的正整数为 6 。

提示：

1 <= arr.length <= 1000
1 <= arr[i] <= 1000
1 <= k <= 1000
对于所有 1 <= i < j <= arr.length 的 i 和 j 满足 arr[i] < arr[j]

进阶：

你可以设计一个时间复杂度小于 O(n) 的算法解决此问题吗？

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

思考

有序正数组中求第 $k$ 个缺失正整数。线性扫描在 $n$ 与 $k$ 同阶时可行，但缺失个数 $a r r [i] - i - 1$ 随 $i$ 单调，适合二分。

若 $a r r [0] > k$ ，答案就是 $k$ 。否则二分第一个「缺失数 $\geq k$ 」的位置 $l e f t$ ，其左侧 $a r r [l e f t - 1]$ 处已缺失 $a r r [l e f t - 1] - (l e f t - 1) - 1$ 个，再向后补 $k$ 与该值的差即可。

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

力扣原题 · Doocs 题解来源

1552. 两球之间的磁力

中等1 种解法

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

题目、示例与约束

在代号为 C-137 的地球上，Rick 发现如果他将两个球放在他新发明的篮子里，它们之间会形成特殊形式的磁力。Rick 有 n 个空的篮子，第 i 个篮子的位置在 position[i] ，Morty 想把 m 个球放到这些篮子里，使得任意两球间 最小磁力 最大。

已知两个球如果分别位于 x 和 y ，那么它们之间的磁力为 |x - y| 。

给你一个整数数组 position 和一个整数 m ，请你返回最大化的最小磁力。

示例 1：

输入：position = [1,2,3,4,7], m = 3
输出：3
解释：将 3 个球分别放入位于 1，4 和 7 的三个篮子，两球间的磁力分别为 [3, 3, 6]。最小磁力为 3 。我们没办法让最小磁力大于 3 。

示例 2：

输入：position = [5,4,3,2,1,1000000000], m = 2
输出：999999999
解释：我们使用位于 1 和 1000000000 的篮子时最小磁力最大。

提示：

n == position.length
2 <= n <= 10^5
1 <= position[i] <= 10^9
所有 position 中的整数 互不相同 。
2 <= m <= position.length

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

思考

在篮子上放 $m$ 个球，最大化任意两球间距的最小值。位置坐标达 $10^{9}$ ，不能按间距枚举所有放法； $n \leq 10^{5}$ ，需要更快的判定。

间距越大能放下的球越少，存在单调性。排序后二分间距 $f$ ，从左到右贪心：与上一球距离至少为 $f$ 才放入。用「无法放下 $m$ 个」作为二分键，第一个失败的 $f$ 的前驱即为最大可行间距。

我们注意到，任意两球间的最小磁力越大，能够放入的球的数量就越少，这存在着单调性。我们可以使用二分查找，找到最大的最小磁力，使得能够放入的球的数量不小于 $m$ 。

我们首先对篮子的位置进行排序，然后使用二分查找的方法，定义二分查找的左边界 $l = 1$ ，右边界 $r = position [n - 1]$ ，其中 $n$ 为篮子的数量。在每次二分查找的过程中，我们计算取中值 $m = (l + r + 1) / 2$ ，然后判断是否存在一种放置球的方法，使得能够放入的球的数量不小于 $m$ 。

问题转换为判断一个给定的最小磁力 $f$ 是否能够放入 $m$ 个球。我们可以从左到右遍历篮子的位置，如果上一个球的位置与当前篮子的位置的距离大于等于 $f$ ，则说明可以在当前篮子放置一个球。最后判断放置的球的数量是否不小于 $m$ 即可。

时间复杂度 $O (n \times \log n + n \times \log M)$ ，空间复杂度 $O (\log n)$ 。其中 $n$ 和 $M$ 分别为篮子的数量和篮子的位置的最大值。

func maxDistance(position []int, m int) int {
	sort.Ints(position)
	return sort.Search(position[len(position)-1], func(f int) bool {
		prev := position[0]
		cnt := 1
		for _, curr := range position {
			if curr-prev >= f {
				cnt++
				prev = curr
			}
		}
		return cnt < m
	}) - 1
}

力扣原题 · Doocs 题解来源

1562. 查找大小为 M 的最新分组

中等2 种解法

标签：数组、哈希表、二分查找、模拟

题目、示例与约束

给你一个数组 arr ，该数组表示一个从 1 到 n 的数字排列。有一个长度为 n 的二进制字符串，该字符串上的所有位最初都设置为 0 。

在从 1 到 n 的每个步骤 i 中（假设二进制字符串和 arr 都是从 1 开始索引的情况下），二进制字符串上位于位置 arr[i] 的位将会设为 1 。

给你一个整数 m ，请你找出二进制字符串上存在长度为 m 的一组 1 的最后步骤。一组 1 是一个连续的、由 1 组成的子串，且左右两边不再有可以延伸的 1 。

返回存在长度恰好为 m 的 一组 1 的最后步骤。如果不存在这样的步骤，请返回 -1 。

示例 1：

输入：arr = [3,5,1,2,4], m = 1
输出：4
解释：
步骤 1："00100"，由 1 构成的组：["1"]
步骤 2："00101"，由 1 构成的组：["1", "1"]
步骤 3："10101"，由 1 构成的组：["1", "1", "1"]
步骤 4："11101"，由 1 构成的组：["111", "1"]
步骤 5："11111"，由 1 构成的组：["11111"]
存在长度为 1 的一组 1 的最后步骤是步骤 4 。

示例 2：

输入：arr = [3,1,5,4,2], m = 2
输出：-1
解释：
步骤 1："00100"，由 1 构成的组：["1"]
步骤 2："10100"，由 1 构成的组：["1", "1"]
步骤 3："10101"，由 1 构成的组：["1", "1", "1"]
步骤 4："10111"，由 1 构成的组：["1", "111"]
步骤 5："11111"，由 1 构成的组：["11111"]
不管是哪一步骤都无法形成长度为 2 的一组 1 。

示例 3：

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

示例 4：

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

提示：

n == arr.length
1 <= n <= 10^5
1 <= arr[i] <= n
arr 中的所有整数 互不相同
1 <= m <= arr.length

方法一：并查集 · Go 实现

思考

按 $a r r$ 的顺序把 $0$ 变成 $1$ ，求最后一次出现长度为 $m$ 的连续 $1$ 段的时刻。 $n \leq 10^{5}$ ，每步重建全串不可行。 $m = n$ 时整段一次填满，答案为 $n$ 。

并查集维护当前 $1$ 连通块的大小。新点与左或右已填邻居合并前，若邻居块长度恰为 $m$ ，则该时刻仍有一段长度为 $m$ （即将被合并破坏），记下步骤。合并后更新块大小。

正向遍历 $a r r$ ，利用并查集动态维护每组 $1$ 的长度。

时间复杂度 $O (n \times \log n)$ 。

相似题目：

2334. 元素值大于变化阈值的子数组

func findLatestStep(arr []int, m int) int {
	n := len(arr)
	if m == n {
		return n
	}
	p := make([]int, n)
	size := make([]int, n)
	vis := make([]bool, n)
	for i := range p {
		p[i] = i
		size[i] = 1
	}
	var find func(int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	union := func(a, b int) {
		pa, pb := find(a), find(b)
		if pa == pb {
			return
		}
		p[pa] = pb
		size[pb] += size[pa]
	}

	ans := -1
	for i, v := range arr {
		v--
		if v > 0 && vis[v-1] {
			if size[find(v-1)] == m {
				ans = i
			}
			union(v, v-1)
		}
		if v < n-1 && vis[v+1] {
			if size[find(v+1)] == m {
				ans = i
			}
			union(v, v+1)
		}
		vis[v] = true
	}
	return ans
}

方法二：动态维护区间端点的长度 · Go 实现

思考

并查集查找带来额外对数因子，而合并只发生在区间端点。在每个 $1$ 段的左右端记下长度，新点根据左右邻居的端点长度拼出新段，并写回新端点。判断与更新都是 $O (1)$ ，总时间线性。

我们其实并不需要去通过查找并查集来获取每个区间长度，我们只需要在每个区间端点处记录每个区间长度，由于合并的时候只会访问区间端点，所以合并区间的时候修改端点区间长度即可。

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

func findLatestStep(arr []int, m int) int {
	n := len(arr)
	if m == n {
		return n
	}
	cnt := make([]int, n+2)
	ans := -1
	for i, v := range arr {
		l, r := cnt[v-1], cnt[v+1]
		if l == m || r == m {
			ans = i
		}
		cnt[v-l], cnt[v+r] = l+r+1, l+r+1
	}
	return ans
}

力扣原题 · Doocs 题解来源

1574. 删除最短的子数组使剩余数组有序

中等2 种解法

标签：栈、数组、双指针、二分查找、单调栈

题目、示例与约束

给你一个整数数组 arr ，请你删除一个子数组（可以为空），使得 arr 中剩下的元素是 非递减 的。

一个子数组指的是原数组中连续的一个子序列。

请你返回满足题目要求的最短子数组的长度。

示例 1：

输入：arr = [1,2,3,10,4,2,3,5]
输出：3
解释：我们需要删除的最短子数组是 [10,4,2] ，长度为 3 。剩余元素形成非递减数组 [1,2,3,3,5] 。
另一个正确的解为删除子数组 [3,10,4] 。

示例 2：

输入：arr = [5,4,3,2,1]
输出：4
解释：由于数组是严格递减的，我们只能保留一个元素。所以我们需要删除长度为 4 的子数组，要么删除 [5,4,3,2]，要么删除 [4,3,2,1]。

示例 3：

输入：arr = [1,2,3]
输出：0
解释：数组已经是非递减的了，我们不需要删除任何元素。

示例 4：

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

提示：

1 <= arr.length <= 10^5
0 <= arr[i] <= 10^9

方法一：双指针 + 二分查找 · Go 实现

思考

删除一段连续子数组后使剩余部分非递减，求最短删除长度。 $n \leq 10^{5}$ ，不能枚举删除区间。剩余数组只能是「一段前缀加一段后缀」，且前缀的末元不超过后缀的首元。

先找出最长非递减前缀 $[0, i]$ 与后缀 $[j, n)$ 。整段有序则答案为 $0$ ；否则至少可删掉整段后缀或整段前缀。再枚举前缀右端 $l$ ，在后缀中二分第一个 $\geq a r r [l]$ 的位置 $r$ ，删除 $(l, r)$ 并取最短。

我们先找出数组的最长非递减前缀和最长非递减后缀，分别记为 $nums [0. . i]$ 和 $nums [j . . n - 1]$ 。

如果 $i \geq j$ ，说明数组本身就是非递减的，返回 $0$ 。

否则，我们可以选择删除右侧后缀，也可以选择删除左侧前缀，因此初始时答案为 $min (n - i - 1, j)$ 。

接下来，我们枚举左侧前缀的最右端点 $l$ ，对于每个 $l$ ，我们可以通过二分查找，在 $nums [j . . n - 1]$ 中找到第一个大于等于 $nums [l]$ 的位置，记为 $r$ ，此时我们可以删除 $nums [l + 1. . r - 1]$ ，并且更新答案 $ans = min (ans, r - l - 1)$ 。继续枚举 $l$ ，最终得到答案。

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

func findLengthOfShortestSubarray(arr []int) int {
	n := len(arr)
	i, j := 0, n-1
	for i+1 < n && arr[i] <= arr[i+1] {
		i++
	}
	for j-1 >= 0 && arr[j-1] <= arr[j] {
		j--
	}
	if i >= j {
		return 0
	}
	ans := min(n-i-1, j)
	for l := 0; l <= i; l++ {
		r := j + sort.SearchInts(arr[j:], arr[l])
		ans = min(ans, r-l-1)
	}
	return ans
}

方法二：双指针 · Go 实现

思考

方法一对每个 $l$ 单独二分，多出 $\log n$ 因子。前缀与后缀都有序，随着 $l$ 增大，对应的 $r$ 只增不减，右指针单调右移即可，总时间降为线性。

与方法一类似，我们先找出数组的最长非递减前缀和最长非递减后缀，分别记为 $nums [0. . i]$ 和 $nums [j . . n - 1]$ 。

如果 $i \geq j$ ，说明数组本身就是非递减的，返回 $0$ 。

否则，我们可以选择删除右侧后缀，也可以选择删除左侧前缀，因此初始时答案为 $min (n - i - 1, j)$ 。

接下来，我们枚举左侧前缀的最右端点 $l$ ，对于每个 $l$ ，我们直接利用双指针找到第一个大于等于 $nums [l]$ 的位置，记为 $r$ ，此时我们可以删除 $nums [l + 1. . r - 1]$ ，并且更新答案 $ans = min (ans, r - l - 1)$ 。继续枚举 $l$ ，最终得到答案。

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

func findLengthOfShortestSubarray(arr []int) int {
	n := len(arr)
	i, j := 0, n-1
	for i+1 < n && arr[i] <= arr[i+1] {
		i++
	}
	for j-1 >= 0 && arr[j-1] <= arr[j] {
		j--
	}
	if i >= j {
		return 0
	}
	ans := min(n-i-1, j)
	r := j
	for l := 0; l <= i; l++ {
		for r < n && arr[r] < arr[l] {
			r += 1
		}
		ans = min(ans, r-l-1)
	}
	return ans
}

力扣原题 · Doocs 题解来源

1608. 特殊数组的特征值

简单2 种解法

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

题目、示例与约束

给你一个非负整数数组 nums 。如果存在一个数 x ，使得 nums 中恰好有 x 个元素 大于或者等于 x ，那么就称 nums 是一个 特殊数组 ，而 x 是该数组的 特征值 。

注意： x 不必是 nums 的中的元素。

如果数组 nums 是一个 特殊数组 ，请返回它的特征值 x 。否则，返回 -1 。可以证明的是，如果 nums 是特殊数组，那么其特征值 x 是 唯一的 。

示例 1：

输入：nums = [3,5]
输出：2
解释：有 2 个元素（3 和 5）大于或等于 2 。

示例 2：

输入：nums = [0,0]
输出：-1
解释：没有满足题目要求的特殊数组，故而也不存在特征值 x 。
如果 x = 0，应该有 0 个元素 >= x，但实际有 2 个。
如果 x = 1，应该有 1 个元素 >= x，但实际有 0 个。
如果 x = 2，应该有 2 个元素 >= x，但实际有 0 个。
x 不能取更大的值，因为 nums 中只有两个元素。

示例 3：

输入：nums = [0,4,3,0,4]
输出：3
解释：有 3 个元素大于或等于 3 。

示例 4：

输入：nums = [3,6,7,7,0]
输出：-1

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 1000

方法一：暴力枚举 · Go 实现

思考

特数 $x$ 只能落在 $[1, n]$ ，而 $n \leq 100$ ，对每个候选 $x$ 扫描数组统计 $\geq x$ 的个数即可在 $O (n^{2})$ 内判定。

若不存在这样的 $x$ ，按题意返回 $- 1$ 。

实现上直接枚举 $x$ ，用一次线性计数比较是否等于 $x$ 。

我们在 $[1. . n]$ 范围内枚举 $x$ ，然后统计数组中大于等于 $x$ 的元素个数，记为 $c n t$ 。若存在 $c n t$ 与 $x$ 相等，直接返回 $x$ 。

时间复杂度 $O (n^{2})$ ，其中 $n$ 是数组的长度。空间复杂度 $O (1)$ 。

func specialArray(nums []int) int {
	for x := 1; x <= len(nums); x++ {
		cnt := 0
		for _, v := range nums {
			if v >= x {
				cnt++
			}
		}
		if cnt == x {
			return x
		}
	}
	return -1
}

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

思考

方法一对每个 $x$ 都整表扫描。排序之后， $\geq x$ 的个数等于 $n$ 减去第一个不小于 $x$ 的下标，可用二分在 $O (\log n)$ 内求得。

总复杂度降为 $O (n \log n)$ ，在 $n$ 更大时更稳妥，本题规模下两者均可通过。

我们也可以先对 nums 进行排序。

接下来同样枚举 $x$ ，利用二分查找，找到 nums 中第一个大于等于 $x$ 的元素，快速统计出 nums 中大于等于 $x$ 的元素个数。

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

func specialArray(nums []int) int {
	sort.Ints(nums)
	n := len(nums)
	for x := 1; x <= n; x++ {
		left, right := 0, n
		for left < right {
			mid := (left + right) >> 1
			if nums[mid] >= x {
				right = mid
			} else {
				left = mid + 1
			}
		}
		cnt := n - left
		if cnt == x {
			return x
		}
	}
	return -1
}

力扣原题 · Doocs 题解来源

1618. 找出适应屏幕的最大字号 🔒

中等1 种解法

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

题目、示例与约束

给定一个字符串 text。并能够在宽为 w 高为 h 的屏幕上显示该文本。

字体数组中包含按升序排列的可用字号，您可以从该数组中选择任何字体大小。

您可以使用FontInfo接口来获取任何可用字体大小的任何字符的宽度和高度。

FontInfo接口定义如下：

interface FontInfo {
  // 返回 fontSize 大小的字符 ch 在屏幕上的宽度。
  // 每调用该函数复杂度为 O(1)
  public int getWidth(int fontSize, char ch);

  // 返回 fontSize 大小的任意字符在屏幕上的高度。
  // 每调用该函数复杂度为 O(1)
  public int getHeight(int fontSize);
}

一串字符的文本宽度应该是 每一个字符 在对应字号(fontSize)下返回的宽度getWidth(fontSize, text[i])的总和。对应字号的文本高度可由 getHeight(fontSize) 计算得到。

请注意：文本最多只能排放一排

如果使用相同的参数调用 getHeight 或 getWidth ，则可以保证 FontInfo 将返回相同的值。

同时，对于任何字体大小的 fontSize 和任何字符 ch ：

getHeight(fontSize) <= getHeight(fontSize+1)
getWidth(fontSize, ch) <= getWidth(fontSize+1, ch)

返回可用于在屏幕上显示文本的最大字体大小。如果文本不能以任何字体大小显示，则返回-1。

示例 1:

输入: text = "helloworld", w = 80, h = 20, fonts = [6,8,10,12,14,16,18,24,36]
输出: 6

示例 2：

输入: text = "leetcode", w = 1000, h = 50, fonts = [1,2,4]
输出: 4

示例 3：

输入: text = "easyquestion", w = 100, h = 100, fonts = [10,15,20,25]
输出: -1

注意:

1 <= text.length <= 50000
text 只包含小写字母
1 <= w <= 10⁷
1 <= h <= 10⁴
1 <= fonts.length <= 10⁵
1 <= fonts[i] <= 10⁵
fonts 已经按升序排序，且不包含重复项。

方法一：Go 解法（本站整理） · Go 实现

Doocs 参考题解 · CC BY-SA 4.0

基于 Doocs 二分参考改写，并先统计字符频次，避免每次判定扫描全文。fits(s) 要求字高不超过 h，且每个字符宽度乘次数的总和不超过 w；单调性允许查找最后一个可行字号。n 为文本长度，f 为字号数，时间 O(n + 26 log f)，空间 O(1)。宽度乘法用 int64。平台接口 FontInfo 提供 GetWidth(fontSize int, ch byte) int 和 GetHeight(fontSize int) int；代码用 Go interface 表达接口，测试 mock 的单调尺寸与官方样例结果兼容，真实尺寸由平台提供。

出处：Doocs 原题与题解，固定提交 91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011；题意、参考及本 Go 改写采用 CC BY-SA 4.0。

// 题意与参考：Doocs LeetCode，CC BY-SA 4.0。
// https://github.com/doocs/leetcode/blob/91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011/solution/1600-1699/1618.Maximum%20Font%20to%20Fit%20a%20Sentence%20in%20a%20Screen/README.md
// Go 实现与测试沿用 CC BY-SA 4.0；来源性质见配套说明。
type FontInfo interface {
	GetWidth(int, byte) int
	GetHeight(int) int
}

func maxFont(text string, w, h int, fonts []int, fontInfo FontInfo) int {
	var counts [26]int64
	for i := 0; i < len(text); i++ {
		counts[text[i]-'a']++
	}
	fits := func(size int) bool {
		if fontInfo.GetHeight(size) > h {
			return false
		}
		var width int64
		for c, n := range counts {
			if n > 0 {
				width += n * int64(fontInfo.GetWidth(size, byte(c)+'a'))
				if width > int64(w) {
					return false
				}
			}
		}
		return true
	}
	lo, hi := 0, len(fonts)
	for lo < hi {
		mid := lo + (hi-lo)/2
		if fits(fonts[mid]) {
			lo = mid + 1
		} else {
			hi = mid
		}
	}
	if lo == 0 {
		return -1
	}
	return fonts[lo-1]
}

力扣原题 · Doocs 题解来源

1658. 将 x 减到 0 的最小操作数

中等2 种解法

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

题目、示例与约束

给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要修改数组以供接下来的操作使用。

如果可以将 x 恰好减到 0 ，返回 最小操作数 ；否则，返回 -1 。

示例 1：

输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。

示例 2：

输入：nums = [5,6,7,8,9], x = 4
输出：-1

示例 3：

输入：nums = [3,2,20,1,1,3], x = 10
输出：5
解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁴
1 <= x <= 10⁹

方法一：哈希表 + 前缀和 · Go 实现

思考

每次只能删左右端点，使删除之和为 $x$ 且次数最少，等价于中间留下和为 $\sum n u m s - x$ 的最长子数组。 $n$ 达 $10^{5}$ ，需要线性查找该子数组。

前缀和哈希：记下和第一次出现的下标，当 $t - s$ 已出现则更新最长长度，答案为 $n$ 减该长度。

根据题目描述，我们需要移除数组 $n u m s$ 左右两端的元素，使得移除的元素和等于 $x$ ，且移除的元素个数最少。我们可以将问题转化为：找到数组 $n u m s$ 中最长的连续子数组，使得子数组的和 $s = \sum_{i = 0}^{n} n u m s [i] - x$ 。这样，我们就可以将问题转化为求解数组 $n u m s$ 中和为 $s$ 的最长连续子数组的长度 $m x$ ，答案即为 $n - m x$ 。

我们初始化 $m x = - 1$ ，然后使用哈希表 $v i s$ 来存储前缀和，键为前缀和，值为前缀和对应的下标。

遍历数组 $n u m s$ ，对于当前元素 $n u m s [i]$ ，计算前缀和 $t$ ，如果 $t$ 不在哈希表中，则将 $t$ 加入哈希表；如果 $t - s$ 在哈希表中，则更新 $m x = max (m x, i - v i s [t - s])$ 。

最后，如果 $m x = - 1$ ，则返回 $- 1$ ，否则返回 $n - m x$ 。

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

func minOperations(nums []int, x int) int {
	s := -x
	for _, v := range nums {
		s += v
	}
	vis := map[int]int{0: -1}
	mx, t := -1, 0
	for i, v := range nums {
		t += v
		if _, ok := vis[t]; !ok {
			vis[t] = i
		}
		if j, ok := vis[t-s]; ok {
			mx = max(mx, i-j)
		}
	}
	if mx == -1 {
		return -1
	}
	return len(nums) - mx
}

方法二：双指针 · Go 实现

思考

方法一用哈希表。元素均为正，前缀和严格递增，可用双指针把窗口和压到 $s$ ，省掉额外空间。

基于方法一的分析，我们需要求解数组 $n u m s$ 中和为 $s$ 的最长连续子数组的长度 $m x$ 。由于数组 $n u m s$ 中的元素都是正整数，数组的前缀和只会单调递增，因此我们可以使用双指针来求解。

我们初始化指针 $j = 0$ ，前缀和 $t = 0$ ，最长连续子数组的长度 $m x = - 1$ 。

遍历数组 $n u m s$ ，对于当前元素 $n u m s [i]$ ，计算前缀和 $t + = n u m s [i]$ ，如果 $t > s$ ，则移动指针 $j$ ，直到 $t \leq s$ 。如果 $t = s$ ，则更新 $m x = max (m x, i - j + 1)$ 。

最后，如果 $m x = - 1$ ，则返回 $- 1$ ，否则返回 $n - m x$ 。

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

func minOperations(nums []int, x int) int {
	s := -x
	for _, v := range nums {
		s += v
	}
	mx, t, j := -1, 0, 0
	for i, v := range nums {
		t += v
		for ; j <= i && t > s; j++ {
			t -= nums[j]
		}
		if t == s {
			mx = max(mx, i-j+1)
		}
	}
	if mx == -1 {
		return -1
	}
	return len(nums) - mx
}

力扣原题 · Doocs 题解来源

1712. 将数组分成三个子数组的方案数

中等1 种解法

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

题目、示例与约束

我们称一个分割整数数组的方案是好的，当它满足：

数组被分成三个非空连续子数组，从左至右分别命名为 left ， mid ， right 。
left 中元素和小于等于 mid 中元素和，mid 中元素和小于等于 right 中元素和。

给你一个非负整数数组 nums ，请你返回好的分割 nums 方案数目。由于答案可能会很大，请你将结果对 10⁹+ 7 取余后返回。

示例 1：

输入：nums = [1,1,1]
输出：1
解释：唯一一种好的分割方案是将 nums 分成 [1] [1] [1] 。

示例 2：

输入：nums = [1,2,2,2,5,0]
输出：3
解释：nums 总共有 3 种好的分割方案：
[1] [2] [2,2,5,0]
[1] [2,2] [2,5,0]
[1,2] [2,2] [5,0]

示例 3：

输入：nums = [3,2,1]
输出：0
解释：没有好的分割方案。

提示：

3 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁴

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

思考

三段非空且前缀和满足 $s_{left} \leq s_{mid} \leq s_{right}$ 。两重枚举分割点为 $O (n^{2})$ ， $n \leq 10^{5}$ 不可行。

元素非负，前缀和单调。固定左段右端 $i$ 后， $mid$ 的右端落在一段连续区间，可用二分求出。

条件化为 $s [j] \geq 2 s [i]$ 与 $s [k] \leq (s [- 1] + s [i]) / 2$ 。对每个 $i$ 做两次二分，方案数对 $10^{9} + 7$ 取模。

我们先预处理出数组 $n u m s$ 的前缀和数组 $s$ ，其中 $s [i]$ 表述数组 $n u m s$ 前 $i + 1$ 个元素之和。

由于数组 $n u m s$ 的元素都是非负整数，因此前缀和数组 $s$ 是一个单调递增数组。

我们在 $[0, . . n - 2)$ 的范围内枚举 left 子数组所能到达的下标 $i$ ，然后利用前缀和数组单调递增的特性，通过二分查找的方式找到 mid 子数组分割的合理范围，记为 $[j, k)$ ，累加方案数 $k - j$ 。

二分细节上，子数组分割必须满足 $s [j] \geq s [i]$ ，并且 $s [n - 1] - s [k] \geq s [k] - s [i]$ 。即 $s [j] \geq s [i]$ ，且 $s [k] \leq \frac{s [n - 1] + s [i]}{2}$ 。

最后，将方案数对 $10^{9} + 7$ 取模后返回即可。

时间复杂度 $O (n \times \log n)$ 。其中 $n$ 为数组 $n u m s$ 的长度。

func waysToSplit(nums []int) (ans int) {
	const mod int = 1e9 + 7
	n := len(nums)
	s := make([]int, n)
	s[0] = nums[0]
	for i := 1; i < n; i++ {
		s[i] = s[i-1] + nums[i]
	}
	for i := 0; i < n-2; i++ {
		j := sort.Search(n-1, func(h int) bool { return h > i && s[h] >= (s[i]<<1) })
		k := sort.Search(n-1, func(h int) bool { return h >= j && s[h] > (s[n-1]+s[i])>>1 })
		ans = (ans + k - j) % mod
	}
	return
}

力扣原题 · Doocs 题解来源

LeetCode Go · 二分查找（3） ​

1099. 小于 K 的两数之和 🔒 ​

1150. 检查一个数是否在数组中占绝大多数 🔒 ​

1170. 比较字符串最小字母出现频次 ​

1198. 找出所有行中最小公共元素 🔒 ​

1201. 丑数 III ​

1208. 尽可能使字符串相等 ​

1213. 三个有序数组的交集 🔒 ​

1231. 分享巧克力 🔒 ​

1237. 找出给定方程的正整数解 ​

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

1292. 元素和小于等于阈值的正方形的最大边长 ​

1300. 转变数组后最接近目标值的数组和 ​

1337. 矩阵中战斗力最弱的 K 行 ​

1346. 检查整数及其两倍数是否存在 ​

1351. 统计有序矩阵中的负数 ​

1385. 两个数组间的距离值 ​

1428. 至少有一个 1 的最左端列 🔒 ​

1439. 有序矩阵中的第 k 个最小数组和 ​

1482. 制作 m 束花所需的最少天数 ​

1498. 满足条件的子序列数目 ​

1508. 子数组和排序后的区间和 ​

1533. 找到最大整数的索引 🔒 ​

1539. 第 k 个缺失的正整数 ​

1552. 两球之间的磁力 ​

1562. 查找大小为 M 的最新分组 ​

1574. 删除最短的子数组使剩余数组有序 ​

1608. 特殊数组的特征值 ​

1618. 找出适应屏幕的最大字号 🔒 ​

1658. 将 x 减到 0 的最小操作数 ​

1712. 将数组分成三个子数组的方案数 ​

继续阅读

LeetCode Go · 二分查找（3）

1099. 小于 K 的两数之和 🔒

1150. 检查一个数是否在数组中占绝大多数 🔒

1170. 比较字符串最小字母出现频次

1198. 找出所有行中最小公共元素 🔒

1201. 丑数 III

1208. 尽可能使字符串相等

1213. 三个有序数组的交集 🔒

1231. 分享巧克力 🔒

1237. 找出给定方程的正整数解

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

1292. 元素和小于等于阈值的正方形的最大边长

1300. 转变数组后最接近目标值的数组和

1337. 矩阵中战斗力最弱的 K 行

1346. 检查整数及其两倍数是否存在

1351. 统计有序矩阵中的负数

1385. 两个数组间的距离值

1428. 至少有一个 1 的最左端列 🔒

1439. 有序矩阵中的第 k 个最小数组和

1482. 制作 m 束花所需的最少天数

1498. 满足条件的子序列数目

1508. 子数组和排序后的区间和

1533. 找到最大整数的索引 🔒

1539. 第 k 个缺失的正整数

1552. 两球之间的磁力

1562. 查找大小为 M 的最新分组

1574. 删除最短的子数组使剩余数组有序

1608. 特殊数组的特征值

1618. 找出适应屏幕的最大字号 🔒

1658. 将 x 减到 0 的最小操作数

1712. 将数组分成三个子数组的方案数