class Solution {
public:
int purchasePlans(vector<int>& nums, int target) {
}
};
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^51 <= nums[i], target <= 10^5原站题解
python3 解法, 执行用时: 192 ms, 内存消耗: 27.3 MB, 提交时间: 2023-09-27 16:34:13
class Solution:
def purchasePlans(self, nums: List[int], target: int) -> int:
nums.sort()
ans = 0
i = 0
j = len(nums)-1
while i < j:
if nums[i] + nums[j] > target:
j -= 1
else:
ans += (j-i)
i += 1
if ans<=1000000007:
return ans
else:
return ans%1000000007
cpp 解法, 执行用时: 164 ms, 内存消耗: 59.1 MB, 提交时间: 2023-09-27 16:33:52
class Solution {
public:
int purchasePlans(vector<int>& nums, int target) {
long long res = 0;
long long mod = 1000000007;
sort(nums.begin(),nums.end());
int i=0,j = nums.size()-1;
for(i=0;i<j;i++)
{
while(j>i&&nums[i]+nums[j]>target)
{
j--;
}
res += j-i;
}
return res%mod;
}
};
javascript 解法, 执行用时: 208 ms, 内存消耗: 51.9 MB, 提交时间: 2023-09-27 16:33:34
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var purchasePlans = function(nums, target) {
let i = 0, j = nums.length - 1, ans = 0;
nums.sort((a, b) => a - b);
while(i < j){
if(nums[i] + nums[j] > target) j--;
else {
ans += j - i;
i++;
}
}
return ans % 1000000007;
};
java 解法, 执行用时: 32 ms, 内存消耗: 56.7 MB, 提交时间: 2023-09-27 16:33:21
class Solution {
public int purchasePlans(int[] nums, int target) {
int mod = 1_000_000_007;
int ans = 0;
// 首先对整体进行排序
Arrays.sort(nums);
// 双指针，left 从前往后找，right 从后往前
int left = 0, right = nums.length - 1;
while (left < right) {
// 如果当前左右之和大于了目标值，说明偏大了，就把右指针往左移动
if (nums[left] + nums[right] > target) right--;
else {
// 否则的话，说明找到了合适的，需要把两者中间的元素个数都累加起来
ans += right - left;
// 然后再向右移动左指针
left++;
}
ans %= mod;
}
return ans % mod;
}
}
golang 解法, 执行用时: 184 ms, 内存消耗: 7.8 MB, 提交时间: 2021-05-18 14:39:46
func purchasePlans(nums []int, target int) int {
ans := 0
sort.Ints(nums)
left, right := 0, len(nums)-1
for left < right {
if nums[left] + nums[right] > target {
right--
} else {
ans += right - left
left++
}
}
return ans % (1e9 + 7)
}