涉及知识点
归并排序
题目
给你一个整数数组 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;
}
};相关下载
想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版
鄙人想对大家说的话 |
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
墨家名称的来源：有所得以墨记之。 |
如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：
VS2022 C++17
