脚撕LeetCode(LCP28)Easy
脚撕LeetCode(LCP28)Easy
用户6203048
发布于 2022-01-18 08:25:40
发布于 2022-01-18 08:25:40
题目地址：https://leetcode-cn.com/problems/4xy4Wx/
小力将 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^这道题的题意是：如果出现了数组中两个非同一索引的元素和小于等于target则返回数字+1；
一、爆破法
直接for-for没什么好解释，就是这么暴躁，注意内层for的索引必须是外层for的后面，防止重复统计。
public int purchasePlansMe(int[] nums, int target) {
int ans = 0;
for (int i = 0; i < nums.length - 1; i++) {
for (int j = i + 1; j < nums.length; j++) {
if(nums[i] + nums[j] <= target) {
ans++;
}
}
}
return ans;
}免不了要看看评论区大佬的做法
二、评论区大佬法
public int purchasePlans(int[] nums, int target) {
final int N = (int)1e9+7;
long[] presum = new long[10_0001];
for (int num : nums) {
presum[num]++;
}
for (int i = 1; i < presum.length; i++) {
presum[i] += presum[i-1];
}
long ans = 0;
for (int num : nums) {
if(num >= target)continue;
long other = target - num;
ans += presum[(int)other];
if(other>=num) {
ans--;
}
}
return (int)((ans>>>1)%N);
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2021-06-15，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读