LeetCode 2300题暴力解法无法通过第48测试用例求助

给定两个正整数数组spells和potions，长度分别为n和m，其中spells[i]表示第i个咒语的强度，potions[j]表示第j个药水的强度。
同时给定整数success。若咒语和药水的强度乘积至少为success，则该对为成功配对。
返回长度为n的整数数组pairs，其中pairs[i]是能与第i个咒语形成成功配对的药水数量。

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int n = spells.length;
        int m = potions.length;
        int pairs[] = new int[n];
        for(int i = 0; i<n; i++) {
            int successful = 0;
            for(int j = 0; j<m; j++) {
                int prod = spells[i]*potions[j];
                if(prod >= (int)success) {
                    successful++;
                }
            }
            pairs[i] = successful;
        }
        return pairs;
    }
}

你的代码存在两个致命的整数溢出问题，直接导致结果错误：

• 乘积溢出：spells[i]和potions[j]都是int类型，当两者数值较大时，乘积会超出int的最大值（2^31-1），此时prod会变成负数或错误的小数值，完全破坏判断逻辑。
• success强制转换溢出：success是long类型，若它的值超过int最大值，(int)success会被截断成错误的int值，导致判断阈值完全失真，这就是你输出结果与预期差异极大的核心原因。

方法1：修复溢出的暴力解法（仅保证正确性，仍会超时） #

将乘积计算和比较全部改用long类型，避免溢出：

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int n = spells.length;
        int m = potions.length;
        int[] pairs = new int[n];
        for (int i = 0; i < n; i++) {
            int count = 0;
            long spell = spells[i];
            for (int j = 0; j < m; j++) {
                if (spell * potions[j] >= success) {
                    count++;
                }
            }
            pairs[i] = count;
        }
        return pairs;
    }
}

但该方法时间复杂度为O(n*m)，当n、m达到题目上限（1e5）时会超时，因此需要更优解法。

方法2：排序+二分查找（最优解，时间复杂度O(m log m + n log m)） #

1. 先对potions数组排序，这样每个咒语可以通过二分查找快速定位符合条件的最小药水强度。
2. 排序后，从该最小位置到数组末尾的所有药水都满足配对条件，数量为m - 找到的索引。

代码实现：

import java.util.Arrays;

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int n = spells.length;
        int m = potions.length;
        int[] pairs = new int[n];
        Arrays.sort(potions);
        
        for (int i = 0; i < n; i++) {
            long spell = spells[i];
            // 计算满足条件的最小药水强度，用(success + spell -1)/spell实现向上取整，避免浮点运算
            long minPotion = (success + spell - 1) / spell;
            
            // 二分查找第一个>=minPotion的药水索引
            int left = 0, right = m;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (potions[mid] >= minPotion) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            pairs[i] = m - left;
        }
        return pairs;
    }
}

该方法既解决了溢出问题，又大幅降低时间复杂度，可通过所有测试用例。

内容的提问来源于stack exchange，提问作者Sri Midhinesh Sankurabhukta