C++ 中范围和的计数
c++server side programmingprogramming更新于 2024/9/27 4:18:00
假设我们有一个整数数组 nums，我们必须找到位于范围 [lower, upper](包括两者)内的范围和的数量。范围和 S(i, j) 定义为 nums 中从索引 i 到索引 j 的元素之和，其中 i ≤ j。
因此，如果输入为 [-3,6,-1]，lower = -2 且 upper = 2，则结果将为 2，因为范围为 [0,2]，总和为 2，[2,2]，总和为 -2。
为了解决这个问题，我们将遵循以下步骤 −
- 定义一个函数 mergeIt()，它将采用数组前缀、start、mid、end、lower、upper，
- i := start, j := mid + 1
- temp := end - start + 1
- low := mid + 1, high := mid + 1
- k := 0
- 定义一个大小为 temp 的数组 arr。
- 当 i <= mid 时，执行 −
- 当 (low <= end 且 prefix[low] - prefix[i] < lower) 时，执行 −
- 将 low 增加 1
- 当 (high <= end 且 prefix[high] - prefix[i] <= upper) 时，执行 −
- 将 high 增加 1
- 当 (j <= end 且 prefix[j] < prefix[i]) 时，执行 −
- arr[k] := prefix[j]
- (将 j 增加 1)
- (将 k 增加 1)
- arr[k] := prefix[i]
- (将 i 增加 1)
- (将 k 增加 1)
- count := count + high - low
- 当 (low <= end 且 prefix[low] - prefix[i] < lower) 时，执行 −
- 当 j <= end 时，执行 −
- arr[k] := prefix[j]
- (将 k 增加 1)
- (将 j 增加 1)
- 初始化 i := 0，当 i < temp 时，更新 (将 i 增加 1)，执行 −
- prefix[start] := arr[i]
- (将 start 增加 1)
- 定义一个函数merge()，它将采用prefix[]、start、end、lower、upper，
- 如果start >= end，则返回
- mid := start + (end - start)
- 调用函数merge(prefix、start、mid、lower、upper)
- 调用函数merge(prefix、mid + 1、end、lower、upper)
- 调用函数mergeIt(prefix、start、mid、end、lower、upper)
- 从main方法中，执行以下操作−
- n := nums的大小
- count := 0
- 定义一个大小为n+1的数组前缀。
- prefix[0] := 0
- 用于初始化i := 1，当 i <= n 时，更新(将 i 增加 1)，执行 −
- prefix[i] := prefix[i - 1] + nums[i - 1]
- 调用函数 merge(prefix, 0, n, lower, upper)
- return count
让我们看看下面的实现以便更好地理解 −
示例
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int count = 0;
void mergeIt(lli prefix[], lli start ,lli mid, lli end, lli lower, lli upper){
lli i = start, j = mid + 1;
lli temp = end - start + 1;
lli low = mid + 1, high = mid + 1;
lli k = 0;
lli arr[temp];
while(i <= mid){
while(low <= end && prefix[low] - prefix[i] < lower) low++;
while(high <= end && prefix[high] - prefix[i] <= upper) high++;
while(j<= end && prefix[j] < prefix[i]){
arr[k] = prefix[j];
j++;
k++;
}
arr[k] = prefix[i];
i++;
k++;
count += high - low;
}
while(j <= end){
arr[k] = prefix[j];
k++;
j++;
}
for(i = 0; i < temp; i++){
prefix[start] = arr[i];
start++;
}
}
void merge(lli prefix[], lli start, lli end, lli lower, lli upper){
if(start >= end)return;
lli mid = start + (end - start) / 2;
merge(prefix, start, mid, lower, upper);
merge(prefix, mid + 1, end, lower, upper);
mergeIt(prefix, start, mid, end, lower, upper);
}
int countRangeSum(vector<int>& nums, int lower, int upper) {
lli n = nums.size();
count = 0;
lli prefix[n + 1];
prefix[0] = 0;
for(lli i = 1; i <= n; i++){
prefix[i] = prefix[i - 1] + nums[i - 1];
}
merge(prefix, 0, n, lower, upper);
return count;
}
};
main(){
Solution ob;
vector<int> v = {-3,6,-1};
cout << (ob.countRangeSum(v, -2, 2));
}
输入
{-3,6,-1}
-2
2
输出
2
