LeetCode 2300. 咒语和药水的成功对数

2026-07-14 HGNULB 约 10 分钟

文章信息 3 个分类 4 个标签

分类

题目描述

✅ 2300. 咒语和药水的成功对数

题意分析

给两个正整数数组 spells（长度 n）和 potions（长度 m），再给一个整数 success。对每个咒语 spells[i]，要数出有多少瓶药水满足 spells[i] * potions[j] >= success，把这 n 个计数按原顺序组成数组返回。

要点先说清楚三条。第一，判定是大于等于而不是严格大于，恰好等于 success 的组合算成功 —— 官方样例 2 里 2 * 8 = 16 正好取等号且被计入，这是唯一能把「等号边界」暴露出来的地方。第二，返回的是数目而不是具体配对，所以完全不需要知道是哪几瓶药水成功，只要知道有几瓶。第三，答案数组必须与 spells 的原始下标一一对应，pairs[i] 说的是第 i 个咒语，这意味着 spells 本身不能被重排。

约束给出了强烈信号：n, m <= 10^5，两两枚举是 $10^{10}$ 量级，必然超时，所以每个咒语的查询必须做到远优于 $O(m)$。另一条 1 <= spells[i], potions[i] <= 10^5 而 success 最大到 $10^{10}$，乘积最大也是 $10^{10}$ —— 这已经超出了 32 位整数的范围，题目把 success 声明成 long 就是在明示：任何一次乘法都必须在 64 位下完成。

边界方面：所有数都是正数，不存在零或负数把不等式方向搅乱的情况；某个咒语可能一瓶药水都配不上（样例里强度为 1 的那个），也可能全部配上，答案取值范围是 [0, m]，两端都要能自然产出。

解法：排序 + 二分查找

核心思路

暴力是对每个咒语扫一遍 potions 数一次，$O(nm)$，在 $10^5 \times 10^5$ 的规模下必然超时。瓶颈很清楚：同一份 potions 被反复地、以完全相同的方式扫描了 n 遍，每一遍都在重新发现「哪些药水足够强」这件事，而这件事本可以只准备一次。

关键观察是单调性。固定一个咒语强度 v，条件 v * potions[j] >= success 里 v 是正数，所以它等价于「potions[j] 足够大」。如果把 potions 升序排序，那么随着下标增大，v * potions[j] 单调不减，判定结果只会从「假」变成「真」、绝不会变回去 —— 整个数组被切成「前面一段全部失败、后面一段全部成功」的两块。于是每个咒语的答案只取决于这条分界线的位置。

有了这个结构，问题就变成经典的 lower_bound：在排序后的 potions 里找出第一个使 v * potions[j] >= success 成立的下标 p，那么下标 p 及其之后的 m - p 瓶药水全部成功，答案就是 m - p。二分维持的不变量是：区间 [lo, hi) 始终包含那条分界线，lo 左边（不含 lo）全部判定为假，hi 及其右边全部判定为真。循环终止于 lo == hi，此时它就是分界线本身；hi 初始化为 m 而不是 m - 1，正是为了让「一瓶都配不上」有一个合法落点（lo 最终等于 m，答案 m - m = 0），不必单开特判。

判定条件必须写成乘法 (long) potions[mid] * v >= success，而不是除法 potions[mid] >= success / v。整数除法向下取整，success / v 会比真实阈值偏小，把一批本该失败的药水误判为成功；这个偏差在官方样例上就能显形，不是理论风险。同时乘法要显式拓宽到 64 位：两个 int 相乘先在 32 位里算完再赋给 long 已经晚了，溢出发生在赋值之前。

排序只做一次，之后 n 个咒语各自独立二分、彼此不影响，spells 全程不动，天然满足「答案按原下标对应」的要求。

解题步骤

对 potions 升序排序。为什么：只有有序才能把判定结果整理成「假…假真…真」的单调形态，二分才有立足点；排的是药水不是咒语，因为咒语的顺序是答案的一部分。

记 m = potions.length，开一个长度为 spells.length 的答案数组。为什么：答案与 spells 一一对应，逐个填入即可，无需任何重排或回填。

对每个咒语 spells[i]，令 lo = 0、hi = m。为什么：搜索区间取左闭右开的 [0, m)，hi = m 给「全部失败」留了一个合法落点，避免为空结果单开分支。

当 lo < hi 时取 mid = (lo + hi) >>> 1，若 (long) potions[mid] * spells[i] >= success 则 hi = mid，否则 lo = mid + 1。为什么：成立时 mid 自己就可能是分界线，所以收缩到 mid 而不是 mid - 1；不成立时 mid 已被排除，从 mid + 1 起步。这样每轮至少砍掉一个元素，循环必然终止。

循环结束后 ans[i] = m - lo。为什么：lo 是第一个成功的下标，按单调性，它右边（含自身）共 m - lo 瓶药水全部成功。

返回答案数组。为什么：每个咒语的计数互相独立，逐个填完即得结果。

以 spells = [5,1,3]、potions = [1,2,3,4,5]、success = 7 走一遍：排序后 potions 不变，m = 5。

第 0 个咒语 v = 5：lo=0, hi=5，mid=2，potions[2]=3，3*5=15 >= 7 成立，hi=2；lo=0, hi=2，mid=1，2*5=10 >= 7 成立，hi=1；lo=0, hi=1，mid=0，1*5=5 >= 7 不成立，lo=1；此时 lo == hi == 1 退出，ans[0] = 5 - 1 = 4。核对一下 5 * [1,2,3,4,5] = [5,10,15,20,25]，确实有 4 个不小于 7。

第 1 个咒语 v = 1：mid=2 时 3*1=3 < 7，lo=3；mid=3 时 4*1=4 < 7，lo=4；mid=4 时 5*1=5 < 7，lo=5；lo == hi == 5 退出，ans[1] = 5 - 5 = 0。lo 越过右端点正是「一瓶都配不上」的表达方式，既没有特判也没有越界。

第 2 个咒语 v = 3：mid=2 时 3*3=9 >= 7 成立，hi=2；mid=1 时 2*3=6 < 7，lo=2；lo == hi == 2 退出，ans[2] = 5 - 2 = 3。最终返回 [4,0,3]，与期望一致。

等号边界用样例 2 复核：spells = [3,1,2]、potions = [8,5,8]、success = 16，排序后是 [5,8,8]。第 2 个咒语 v = 2，2*5=10 < 16，2*8=16 >= 16 恰好取等号、必须算成功，分界线落在下标 1，ans[2] = 3 - 1 = 2。若判定误写成严格大于，这里会得到 0。

代码实现

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        // 排序让「是否成功」沿下标单调，二分才有立足点。
        Arrays.sort(potions);
        int m = potions.length;
        int[] ans = new int[spells.length];
        for (int i = 0; i < spells.length; i++) {
            // 左闭右开 [lo, hi)，hi = m 给「一瓶都配不上」留合法落点。
            int lo = 0, hi = m;
            while (lo < hi) {
                int mid = (lo + hi) >>> 1;
                // 乘积可达 1e10，必须先转 long 再乘；用除法会因向下取整放宽阈值。
                if ((long) potions[mid] * spells[i] >= success) {
                    hi = mid;
                } else {
                    lo = mid + 1;
                }
            }
            // lo 是第一个成功的下标，它右边（含自身）全部成功。
            ans[i] = m - lo;
        }
        return ans;
    }
}

func successfulPairs(spells []int, potions []int, success int64) []int {
    // 排序让「是否成功」沿下标单调，二分才有立足点。
    sort.Ints(potions)
    m := len(potions)
    ans := make([]int, len(spells))
    for i, v := range spells {
        // 左闭右开 [lo, hi)，hi = m 给「一瓶都配不上」留合法落点。
        lo, hi := 0, m
        for lo < hi {
            mid := (lo + hi) / 2
            // 乘积可达 1e10，必须先转 int64 再乘；用除法会因向下取整放宽阈值。
            if int64(potions[mid])*int64(v) >= success {
                hi = mid
            } else {
                lo = mid + 1
            }
        }
        // lo 是第一个成功的下标，它右边（含自身）全部成功。
        ans[i] = m - lo
    }
    return ans
}

复杂度分析

时间复杂度：$O((m + n) \log m)$，排序 potions 是 $O(m \log m)$，之后 n 个咒语各做一次区间长度为 m 的二分、每次 $O(\log m)$，两部分相加即得；相比暴力的 $O(nm)$，在 $n = m = 10^5$ 时从 $10^{10}$ 降到约 $1.7 \times 10^6$ 次判定。

空间复杂度：$O(\log m)$，答案数组是必须返回的输出不计入额外空间，二分只用了常数个变量，唯一的额外开销来自排序内部的递归栈深度。

关键点总结

「多次查询同一份数据」就该先把数据整理好。暴力的浪费不在于算得慢，而在于每次查询都从零开始理解同一个数组；排序是一次性的预处理成本，摊到 n 次查询上几乎可以忽略，这个「预处理换查询」的权衡是所有二分类题目的共同底色。

把「乘积够大」翻译成「元素够大」是二分成立的前提。因为乘数恒正，不等式方向不变，判定才具备单调性；一旦乘数可能为零或负数，单调性立刻崩塌。这个前提必须在动手前从约束里确认，而不是默认成立。

用乘法判定，别用除法反推阈值。整数除法向下取整会把阈值放宽导致多算；改成向上取整又要讨论整除的特例。只要提前拓宽到 64 位，乘法既准确又免于分类讨论。

左闭右开区间让空结果不必特判。hi 初始化为 m，lo 最终可以合法地等于 m 表示「没有任何元素满足」，答案 m - lo = 0 自然成立；写成闭区间 [0, m-1] 就得额外处理「全部失败」和「全部成功」两头。

面试视角：这题的追问路径几乎是固定的三步 —— 先要 $O(nm)$ 暴力确认你读懂了题，再问「$10^5$ 的规模够不够」逼出排序加二分，最后一定会盯着乘法问「spells[i] * potions[j] 会不会溢出」。能主动写出强制类型转换并说明「$10^5 \times 10^5 = 10^{10}$ 超过 int 上限，何况 success 本身就声明成了 long」是明确的加分项。有余力可以补一句：如果允许连 spells 一起排序，用双指针可以把每次查询降到均摊 $O(1)$，但本题要按原下标返回，得先记下原下标再排，收益不大。

易错点总结

乘法没转 long：spells = [100000]、potions = [100000]、success = 10000000000 → 输出 [0]，正确答案是 [1]。100000 * 100000 在 32 位里回绕成 1410065408，再拓宽到 64 位去比就已经晚了。所有官方样例的数都很小，这个 bug 只有大数据才会现形。

用除法反推阈值，写成 potions[mid] >= success / spells[i]：spells = [5,1,3]、potions = [1,2,3,4,5]、success = 7 → 输出 [5,0,4] 而不是 [4,0,3]；spells = [3,1,2]、potions = [8,5,8]、success = 16 → 输出 [3,0,2] 而不是 [2,0,2]。整数除法把 7/5 算成 1、16/3 算成 5，阈值被系统性放宽，几乎每个用例都会多算。

判定写成严格大于，即 > success：spells = [3,1,2]、potions = [8,5,8]、success = 16 → 输出 [2,0,0] 而不是 [2,0,2]。第 2 个咒语的乘积恰好等于 16 被漏掉了。只有数据里存在「乘积恰好等于 success」才会暴露，官方样例 1 完全测不出来。

答案写成 m - lo - 1：spells = [5,1,3] 那组 → 输出 [3,-1,2]，第 1 个咒语甚至出现了负数。计数为负是最容易看出来的信号；但若测试数据恰好没有零解，就只表现为「每个答案都少 1」，反而更难察觉。

对 spells 排序而不是 potions：计数值本身可能没错，但产出顺序对应的是排序后的咒语，与题目要求的原始下标全面错位。被查询的那一侧才允许重排，答案侧一旦动了顺序就必须记录原下标并回填。

二分收缩写成 hi = mid - 1 却仍用左闭右开：分界线本身可能就是 mid，减一会把它跳过，循环结束时 lo 落到分界线右边，计数普遍少 1；区间收缩到长度 1 时还可能出现 hi < lo，m - lo 得到越界的负数。左闭右开只能配 hi = mid。

hi 初始化成 m - 1：全部成功时分界线是 0 倒还正确，但一瓶都不成功时 lo 最多只能到 m - 1，会算出 1 而不是 0，等于凭空多配了一瓶。要么把 hi 设成 m，要么就得为「全部失败」单写特判。

循环条件写成 lo <= hi 配左闭右开：lo == hi 时区间已空却还要再算一次 mid，mid 可能取到 m 而下标越界；即使侥幸不越界也会多收缩一轮，把 lo 推过头。区间开闭与循环条件必须成套使用，不能混搭。

每个咒语都重新排一次 potions：结果正确但时间退化到 $O(n \cdot m \log m)$，比暴力还慢，$10^5$ 规模直接超时。排序是一次性预处理，必须留在循环外面。

相似题目

题目	难度	考察点
704. 二分查找	简单	找的是精确相等的位置而非分界线，返回下标不返回计数，是本题二分模板的最简形态
35. 搜索插入位置	简单	同样是 lower_bound，但判定直接比大小、不含乘法与溢出风险，适合单独打磨左闭右开的写法
1170. 比较字符串最小字母出现频次	中等	结构与本题几乎同构，区别在于要先把字符串映射成可比较的整数特征，再排序加二分计数
875. 爱吃香蕉的珂珂	中等	二分的是答案的取值而不是数组下标，单调性来自自己构造的判定函数，是本题思路的进阶变形
658. 找到 K 个最接近的元素	中等	二分定位之后还要向两侧扩展并处理平局规则，考察定位与后续处理的配合而不是单纯计数