涉及知识点
题目
给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数 。
区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。
示例 1：
输入：nums = [-2,5,-1], lower = -2, upper = 2
输出：3
解释：存在三个区间：[0,0]、[2,2] 和 [0,2] ，对应的区间和分别是：-2 、-1 、2 。
示例 2：
输入：nums = [0], lower = 0, upper = 0
输出：1
参数范围
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
-105 <= lower <= upper <= 105
题目数据保证答案是一个 32 位 的整数
2023年3月版（树状数组)
template class CTreeArr { public: CTreeArr(int iSize) :m_vData(iSize+1) { } void Add(int index, T value) { index++; while (index < m_vData.size()) { m_vData[index] += value; index += index&(-index); } } T Sum(int index) { index++; T ret = 0; while (index ) { ret += m_vData[index]; index -= index&(-index); } return ret; } private: vector m_vData; }; class Solution { public: int countRangeSum(vector& nums, int lower, int upper) { //std::multiset dp; vector vCan; long long llAdd = 0; for (const auto& n : nums) { llAdd += n; vCan.emplace_back(n - llAdd); } std::sort(vCan.begin(), vCan.end()); auto itEnd = std::unique(vCan.begin(), vCan.end()); vCan.erase(itEnd, vCan.end()); CTreeArr tree(vCan.size()); llAdd = 0; long long iRet = 0; for (const auto& n : nums) { llAdd += n; const int iIndex = std::lower_bound(vCan.begin(), vCan.end(), (long long)n - llAdd) - vCan.begin(); tree.Add(iIndex, 1); const int iBeginIndex = std::lower_bound(vCan.begin(), vCan.end(), (long long)lower - llAdd) - vCan.begin(); const int iEndIndex = std::lower_bound(vCan.begin(), vCan.end(), (long long)upper - llAdd+1) - vCan.begin(); if (0 == iEndIndex) { continue; } iRet += tree.Sum(iEndIndex - 1); if (iBeginIndex > 0) { iRet -= tree.Sum(iBeginIndex - 1); } }
return iRet; }
};
2023年8月 归并排序版
class CCountRangeSum : public CMergeSortIndex { public: CCountRangeSum(const vector& vPreSum,int lower, int upper):CMergeSortIndex(vPreSum) { m_iLower = lower; m_iUpper = upper; } using CMergeSortIndex::CMergeSortIndex; int m_iRet = 0; protected: virtual void OnSortLeftRightEnd(int left, int mid, int right) { int i2 = mid,i3=mid; for (int i1 = left; i1 < mid; i1++) { while ((i2 < right) && (m_nums[m_vIndexs[i2]] - m_nums[m_vIndexs[i1]] < m_iLower)) { i2++; } while ((i3 < right) && (m_nums[m_vIndexs[i3]] - m_nums[m_vIndexs[i1]] <= m_iUpper)) { i3++; } m_iRet += i3 - i2; } } int m_iLower ; int m_iUpper ; }; class Solution { public: int countRangeSum(vector& nums, int lower, int upper) { vector vPreSum(1); for (const auto& n : nums) { vPreSum.emplace_back(vPreSum.back() + n); } CCountRangeSum crs(vPreSum, lower, upper); crs.Sort(); return crs.m_iRet; } };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 鄙人想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 墨家名称的来源：有所得以墨记之。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：
VS2022 C++17
