LeetCode LCP 28. 采购方案
小力将 N 个零件的报价存于数组 nums。小力预算为 target,假定小力仅购买两个零件,要求购买零件的花费不超过预算,请问他有多少种采购方案。
注意:答案需要以 1e9 + 7 (1000000007) 为底取模,如:计算初始结果为:1000000008,请返回 1
示例 1:
输入:nums = [2,5,3,5], target = 6
输出:1
解释:预算内仅能购买 nums[0] 与 nums[2]。
示例 2:
输入:nums = [2,2,1,9], target = 10
输出:4
解释:符合预算的采购方案如下: nums[0] + nums[1] = 4 nums[0] + nums[2] = 3 nums[1] + nums[2] = 3 nums[2] + nums[3] = 10
提示:
2 <= nums.length <= 10^5
1 <= nums[i], target <= 10^5
双指针
- 本题的重点在于排序预处理,预先排序是对双指针使用的一个不错的小技巧,有时候不好解决的问题只要预先排序就变得十分好处理。
- 后面的主要思路就是选中第一个元素,找到最大的那个能满足预算的那个,那么中间的与第一个元素构成的方案都可以满足预算,所以假设满足预算的那个最大的序号为j,则整个方案数量就是j-0,依次类推,求出第二个元素的对应的j,直到求出第i个元素对应的j,注意由于需要保证方案不重复,i<j是一个限制条件,如此可以获得最终结果。
class Solution:def purchasePlans(self, nums: List[int], target: int) -> int:nums.sort()n = len(nums)j = n - 1res = 0for i in range(n):while nums[i] + nums[j] > target and i < j:j -= 1if i < j:res = (res + j - i) % int((1e9 + 7))else:breakreturn res