请求排查《成功咒语与药剂配对》问题的Python代码错误（双指针思路）

问题回顾 #

给定两个正整数数组spells和potions，长度分别为n和m，spells[i]代表第i个咒语的强度，potions[j]代表第j个药剂的强度。当咒语与药剂的强度乘积≥给定整数success时，视为成功配对。返回长度为n的数组pairs，其中pairs[i]是第i个咒语能形成成功配对的药剂数量。

示例1：

输入：spells = [5,1,3], potions = [1,2,3,4,5], success = 7
输出：[4,0,3]
解释：

• 咒语5与药剂[2,3,4,5]的乘积≥7，共4个
• 咒语1与所有药剂乘积都<7，共0个
• 咒语3与药剂[3,4,5]的乘积≥7，共3个

示例2：

输入：spells = [3,1,2], potions = [8,5,8], success = 16
输出：[2,0,2]

你的代码Bug分析 #

你写的迭代代码返回全[0,0,0]，核心问题有3个：

1. 固定乘积未更新：res = spells[first] * potions[second]只在每个咒语循环的开头计算一次，用的是初始的second=0对应的药剂值，后续for循环里没有重新计算当前遍历到的药剂乘积，导致判断的永远是同一个固定值（比如示例1中第一个咒语的res=5*1=5，始终<7，total不会增加）。
2. 循环逻辑错误：for循环的变量i完全未使用，反而用second索引药剂，但second的更新逻辑混乱——只有当res满足条件时才会+1，不满足就停在原地，导致一直重复判断同一个药剂。
3. 指针未重置：处理完一个咒语后，second没有重置为0，导致下一个咒语开始时second已经处于上一次循环的位置（甚至可能越界）。

修复后的基础迭代代码 #

先修复上述问题，写出正确的暴力迭代版本（时间复杂度O(n*m)，适合小数据量）：

def successfulPairs(self, spells, potions, success):
    arr = []
    for spell in spells:
        total = 0
        for potion in potions:
            if spell * potion >= success:
                total += 1
        arr.append(total)
    return arr

双指针优化解法（时间复杂度O(n log n + m log m)） #

如果想用双指针法，需要先对数组做预处理：

1. 对potions数组升序排序。
2. 将spells数组与对应的索引绑定后，按强度降序排序。
3. 用右指针从potions的末尾开始，遍历降序的咒语，找到能配对的最左药剂位置，统计数量后映射回原索引顺序：

def successfulPairs(self, spells, potions, success):
    m = len(potions)
    potions.sort()
    # 绑定咒语与原索引，按咒语强度降序排序
    sorted_spells = sorted([(spell, idx) for idx, spell in enumerate(spells)], key=lambda x: -x[0])
    res = [0] * len(spells)
    ptr = m - 1  # 药剂的右指针
    
    for spell, idx in sorted_spells:
        # 找到第一个无法与当前咒语配对的药剂位置
        while ptr >= 0 and spell * potions[ptr] >= success:
            ptr -= 1
        # 成功配对的数量是 m - (ptr + 1)
        res[idx] = m - (ptr + 1)
    return res

二分查找解法（最常用高效解法，时间复杂度O(n log m + m log m)） #

先排序potions，对每个咒语计算出能满足条件的最小药剂值（用向上取整避免浮点误差），然后用二分查找找到第一个≥该值的药剂索引，总数量就是数组长度减去该索引：

import bisect

def successfulPairs(self, spells, potions, success):
    potions.sort()
    m = len(potions)
    res = []
    for spell in spells:
        # 计算最小需要的药剂强度：向上取整 success / spell
        min_potion = (success + spell - 1) // spell
        # 找到第一个≥min_potion的索引
        idx = bisect.bisect_left(potions, min_potion)
        res.append(m - idx)
    return res

内容的提问来源于stack exchange，提问作者Jackie