1.题目基本信息

1.1.题目描述

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

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

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

1.2.题目地址

https://leetcode.cn/problems/successful-pairs-of-spells-and-potions/description/

2.解题方法

2.1.解题思路

从spells中遍历每一个魔法spell，并用二分法从升序排列后的potions中找到第一个potions[i]+spell >= success的i，len(potions)-i即为返回数组对应魔法的成功组合数

2.2.解题步骤

第一步，将药水数组进行升序排列

第二步，遍历spells，对每个spell，使用二分法获取第一个potions[i]+spell >= success的i，对应的spell的成功组合数即为len(potions)-i，将结果一项一项添加到结果数组中，最后返回结果数组。

3.解题代码

Python代码

class Solution:def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:# 从spells中遍历每一个魔法spell，并用二分法从升序排列后的potions中找到第一个potions[i]+spell >= success的i，len(potions)-i即为返回数组对应魔法的成功组合数# 第一步，将药水数组进行升序排列# 第二步，遍历spells，对每个spell，使用二分法获取第一个potions[i]+spell >= success的i，对应的spell的成功组合数即为len(potions)-i，将结果一项一项添加到结果数组中，最后返回结果数组。potions.sort()result=[0]*len(spells)for i in range(len(spells)):# 红：potions[i]+spell<success，蓝：potions[i]+spell>=success；找到第一个蓝left,right=0,len(potions)while left<right:mid=(right-left)//2+leftif spells[i]*potions[mid]<success:left=mid+1else:right=midresult[i]=len(potions)-right# print(result)return result

4.执行结果