题目

给你两个正整数数组 spells 和 potions ，长度分别为 n 和 m ，其中 spells[i] 表示第 i 个咒语的能量强度，potions[j] 表示第 j 瓶药水的能量强度。

同时给你一个整数 success 。一个咒语和药水的能量强度 相乘 如果 大于等于 success ，那么它们视为一对 成功 的组合。

请你返回一个长度为 n 的整数数组 pairs，其中 pairs[i] 是能跟第 i 个咒语成功组合的 药水 数目。

示例 1：

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

• 第 0 个咒语：5 * [1,2,3,4,5] = [5,10,15,20,25] 。总共 4 个成功组合。
• 第 1 个咒语：1 * [1,2,3,4,5] = [1,2,3,4,5] 。总共 0 个成功组合。
• 第 2 个咒语：3 * [1,2,3,4,5] = [3,6,9,12,15] 。总共 3 个成功组合。 所以返回 [4,0,3] 。

示例 2：

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

• 第 0 个咒语：3 * [8,5,8] = [24,15,24] 。总共 2 个成功组合。
• 第 1 个咒语：1 * [8,5,8] = [8,5,8] 。总共 0 个成功组合。
• 第 2 个咒语：2 * [8,5,8] = [16,10,16] 。总共 2 个成功组合。 所以返回 [2,0,2] 。

提示：

• n == spells.length
• m == potions.length
• 1 <= n, m <= 10^5
• 1 <= spells[i], potions[i] <= 10^5
• 1 <= success <= 10^10

解题思路

方法一：排序 + 二分查找

这是最经典、最通用的解法。

• 核心思想：将“为每个咒语寻找足量药水”的重复性工作，转化为在有序集合中的高效查找问题。
• 执行步骤：
  1. 排序药水：将 potions 数组升序排序。
  2. 遍历咒语：逐个处理 spells 数组中的每个咒语。
  3. 计算目标值：对于每个咒语 s，计算出它需要的最小药水强度 min_p。
  4. 二分查找：在已排序的 potions 数组中，快速找到第一个强度 ≥ min_p 的药水。
  5. 计算数量：根据找到的药水索引，直接得出所有达标药水的总数。
• 时间复杂度：O(mlogm+nlogm)
• 空间复杂度：O(1) (不计入结果数组，假设原地排序)
• 优点：思路清晰，代码实现直观，空间效率高，不依赖数据的数值范围，适用性非常广。
• 缺点：对于每个咒语都需要进行一次对数时间的查找，虽然已经很快，但仍有理论上的优化空间。

方法二：排序 + 双指针

这种方法通过双重排序，将多次查找优化为一次线性扫描。

• 核心思想：利用咒语和药水都排序后的“单调性”，让两个指针以一种协调、不回退的方式移动，从而在线性时间内完成所有匹配。
• 执行步骤：
  1. 全部排序：对 spells（需记录原始索引）和 potions 两个数组都进行升序排序。
  2. 初始化指针：一个指针 i 指向最弱的咒语，另一个指针 j 指向最强的药水。
  3. 协同移动：遍历所有咒语（i 从左到右移动）。对于每个咒语，从 j 当前位置向左移动，找到恰好能与之匹配的药水边界。因为咒语强度递增，j 指针永远不需要向右回退。
  4. 记录结果：在遍历过程中，根据 j 的位置计算出每个咒语对应的达标药水数，并存入结果数组的原始索引位置。
• 时间复杂度：O(nlogn+mlogm)
• 空间复杂度：O(n) (需要额外空间记录 spells 的原始索引)
• 优点：复杂度与方法一相当，但由于是纯线性扫描，实际运行中可能因其简单的CPU操作和缓存友好性而稍快。
• 缺点：代码实现比二分查找法更复杂，需要额外处理索引的映射关系。

方法三：计数排序 + 后缀和

这是一种“空间换时间”的极致方法，将问题转化为查表。

• 核心思想：创建一个“速查表”，能以 O(1) 的时间回答“强度不低于 X 的药水有多少个”的问题。
• 执行步骤：
  1. 计数：创建一个以药水最大强度为大小的“桶”数组，统计每种强度的药水各有多少个。
  2. 构建速查表：对“桶”数组进行一次反向遍历，计算后缀和。完成后，table[i] 就表示强度 ≥i 的药水总数。
  3. 遍历咒语：对于每个咒语，计算出最小药水需求 min_p。
  4. 查表：直接从速查表中读取 table[min_p] 的值，这就是答案。
• 时间复杂度：O(n+m+K) (其中 K 是药水的最大强度值)
• 空间复杂度：O(K)
• 优点：在 K 不大的情况下，这是理论和实践上最快的方法。查询阶段的 O(1) 效率是无与伦比的。
• 缺点：性能完全依赖于数据的数值范围。如果药水最大强度 K 非常大（例如 10^9），会导致内存爆炸，算法不可行。

具体代码

方法一

func successfulPairs(spells []int, potions []int, success int64) []int {
	// 对 potions 数组进行升序排序，这是使用二分查找的前提。
	sort.Ints(potions)
	ans := make([]int, len(spells))

	for index, spell := range spells {
		// 使用二分查找 (sort.Search) 找到第一个成功的药水索引 k。
		// 所有从 k 到数组末尾的药水也都将是成功的组合。
		// 因此，成功的组合总数就是 len(potions) - k。
		spell_pair := len(potions) - sort.Search(len(potions), func(i int) bool {
			// 判断条件：当前药水强度是否达到了成功所需的最小值。
			// (success + spell - 1) / spell 是计算 ceil(success / spell) 的技巧，
			// 用于在整数运算中实现“向上取整”，从而找到最小所需药水强度。
			return int64(potions[i]) >= (success + int64(spell) - 1) / int64(spell)
		})
		ans[index] = spell_pair
	}
	return ans
}

方法二

func successfulPairs(spells []int, potions []int, success int64) []int {
    n := len(spells)
    m := len(potions)

    // 1. 创建一个二维数组，存储 spell 的值和它的原始索引
    spellsWithIndex := make([][2]int, n)
    for i, s := range spells {
        spellsWithIndex[i] = [2]int{s, i}
    }

    // 2. 对 spellsWithIndex 按 spell 的值进行升序排序
    sort.Slice(spellsWithIndex, func(i, j int) bool {
        return spellsWithIndex[i][0] < spellsWithIndex[j][0]
    })

    // 对 potions 进行升序排序
    sort.Ints(potions)

    // 3. 初始化结果数组和 potions 的指针 j
    ans := make([]int, n)
    j := m - 1 // j 指向 potions 数组的末尾

    // 4. 遍历排好序的 spells
    for _, spellInfo := range spellsWithIndex {
        spellVal := spellInfo[0]
        originalIndex := spellInfo[1]

        // 移动 j 指针，找到第一个不满足条件的 potion
        // 当 spell 变强时，j 只会向左移动或不动，不会重置
        for j >= 0 && int64(spellVal)*int64(potions[j]) >= success {
            j--
        }

        // j 右边的所有 potions 都满足条件
        // 它们的数量是 m - 1 - j
        count := m - 1 - j
        ans[originalIndex] = count
    }

    return ans
}

方法三

func successfulPairs(spells []int, potions []int, success int64) []int {
	// 如果没有药水，直接返回全零结果
	if len(potions) == 0 {
		return make([]int, len(spells))
	}

	// --- 步骤 1: 预处理，构建速查表 ---

	// 找到最大的药水强度，以确定计数数组的大小
	maxPotion := slices.Max(potions)

	// 创建计数数组(桶)。counts[i] 用于存储强度恰好为 i 的药水数量。
	counts := make([]int, maxPotion+1)
	for _, p := range potions {
		counts[p]++
	}

	// 将计数数组转换为后缀和数组，制作成“速查表”。
	// 转换后，counts[i] 的含义变为：强度大于等于 i 的药水总数。
	for i := maxPotion; i > 0; i-- {
		counts[i-1] += counts[i]
	}

	// --- 步骤 2: 遍历咒语，使用速查表查询结果 ---

	// 创建一个新的结果数组，避免直接修改输入的 spells 数组
	result := make([]int, len(spells))
	for i, s := range spells {
		// 计算所需的最小药水强度，使用向上取整的技巧。
		requiredPotion := (success - 1) / int64(s) + 1

		// 如果所需强度在我们速查表的范围内
		if requiredPotion <= int64(maxPotion) {
			// 直接从速查表中以 O(1) 复杂度获取答案
			result[i] = counts[requiredPotion]
		} else {
			// 如果所需强度超过了任何药水的最大强度，则成功的组合数为 0
			result[i] = 0
		}
	}

	return result
}