小力将 N 个零件的报价存于数组
nums。小力预算为target,假定小力仅购买两个零件,要求购买零件的花费不超过预算,请问他有多少种采购方案。注意:答案需要以
1e9 + 7 (1000000007)为底取模,如:计算初始结果为:1000000008,请返回1
思路:
因为只需要买两个零件考虑到只需要计算两个数值的和是否在预算以内即可,故而采用双指针的办法,依次判断之和是否满足条件即可。最后结果对1000000007取余即可(因为可能零件和预算变大之后方法也会变多)。主要难理解的可能是其中判断依据排序后为什么是right-left是一个数学问题,他如果最小的和最大的和满足题意,等价于一个搭配问题,两个两个取能取几次,是个排列问题,他的次数为最右边的序数减去最左边的序数就是次数。
class Solution: def purchasePlans(self,nums:List[int],target:int)->int: left,right=0,len(nums)-1 count=0 nums.sort() while left<right: if nums[left]+nums[right]<=target: count+=right-left left+=1 else: right-=1 return count%1000000007难点分析:
- 排序保证了 “单调性”:左指针固定时,右指针往左的所有数都更小,因此和左指针的和也更小;
- 双指针的 “贪心”:找到最大的合法右指针,就能覆盖所有更小的右指针的合法情况;
- 计数的 “数学本质”:
left+1到right的元素个数 = 终止索引 - 起始索引 =right - left(起始索引是 left+1,终止索引是 right → 个数 = right - (left+1) + 1 = right - left)。