力扣练习——40 区间和的个数

40 区间和的个数

1.问题描述
给定一个整数数组 nums，返回区间和在 [lower, upper] 之间的个数，包含 lower 和 upper。

区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。

说明:

最直观的算法复杂度是 O(n2) ，请在此基础上优化你的算法。

示例:

输入: nums = [-2,5,-1], lower = -2, upper = 2,

输出: 3

解释: 3个区间分别是: [0,0], [2,2], [0,2]，它们表示的和分别为: -2, -1, 2。

可使用以下main函数：

int main()

{

vector<int> nums;

int n,data,lower,upper;

cin>>n;

for(int j=0; j<n; j++)

{

    cin>>data;

    nums.push_back(data);

}

cin>>lower>>upper;

int res=Solution().countRangeSum(nums,lower,upper);

cout<<res<<endl;

return 0;

}

2.输入说明
首先输入nums数组的长度n，

然后输入n个整数，以空格分隔。

最后输入两个整数lower和upper。

1<=n<=10000
3.输出说明
输出一个整数
4.范例
输入
3
-2 5 -1
-2 2
输出
3
5.代码

#include <iostream>
#include <queue>
#include <cstdlib>
#include <cstring>
#include<set>
using namespace std;

int countRangeSum(vector<int>nums, int lower, int upper)
{
       
	//参考题解：https://leetcode.cn/problems/count-of-range-sum/solution/327qu-jian-he-de-ge-shu-ti-jie-zong-he-by-xu-yuan-/
	int len = nums.size();//数组长度
	int presum = 0;//前缀和 
	multiset<int> S;//平衡树
	S.insert(0);
	int res = 0;//结果
	for (int i = 0; i < len; i++) {
    
		presum += nums[i];
		//lower_bound返回数值第一个出现的位置
		//upper_bound返回的是最后一个大于等于val的位置，也是有一个新元素val进来时的插入位置
		res += distance(S.lower_bound(presum - upper), S.upper_bound(presum - lower));
		//distance()计算两个迭代器表示的范围内包含元素的个数
		S.insert(presum);
	}
	return res;
}


int main()

{
    

	vector<int> nums;

	int n, data, lower, upper;

	cin >> n;

	for (int j = 0; j < n; j++)

	{
    

		cin >> data;

		nums.push_back(data);

	}

	cin >> lower >> upper;

	int res = countRangeSum(nums, lower, upper);

	cout << res << endl;

	return 0;

}