数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中区间和的计数
假设我们有一个整数数组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()，它将接收数组prefix，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到temp-1循环，执行以下操作：
- prefix[start] := arr[i]
- start自增1
- 定义一个函数merge()，它将接收prefix[]，start，end，lower，upper作为参数。
- 如果start >= end，则返回。
- 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)
- 在主方法中，执行以下操作：
- n := nums的大小
- count := 0
- 定义一个大小为n+1的数组prefix。
- prefix[0] := 0
- 对于i从1到n循环，执行以下操作：
- prefix[i] := prefix[i - 1] + nums[i - 1]
- 调用函数merge(prefix, 0, n, lower, upper)
- 返回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
更新于：2020年6月1日
508 次浏览
广告