Я решаю проблему.
Count of Range Sum
Given an integer array nums, return the number of range sums that
lie in [lower, upper] inclusive. Range sum S(i, j) is defined as
the sum of the elements in nums between indices i and j (i ≤ j),inclusive.
Example: Given nums = [-2, 5, -1], lower = -2, upper = 2, Return 3.
The three ranges are : [0, 0], [2, 2], [0, 2] and their respective sums are: -2, -1, 2
Мое решение ниже:
1. получить все суммы из [0, i] как сумму [i]
2.сортируйте вектор суммы как вектор клона, и переиндексируйте элементы в сумме согласно его индексу в векторе клона. Поместите значение элемента суммы как ключ отражения карты, новый индекс как значение отражения. добавьте элемент вектора суммы от начала до конца в двоичное индексированное дерево и в то же время найдите допустимый диапазон индекса элементов [idx1, idx2] в клоне, который удовлетворяет условию нижней и верхней границ.
3. получить сумму от узла 0 до узла idx1 и сумму от узла 0 до узла idx2 в нашем BIT. Если узел уже вставлен в BIT, мы найдем узел в нашем BIT. Таким образом, количество узлов, которое удовлетворяет нашему ограниченному условию, является суммой.
public:
vector<long>tree,clone;
int countRangeSum(vector<int>& nums, int lower, int upper) {
int n=nums.size();
vector<long>sum(n+1);
for(int i=1;i<=n;i++)
sum[i]=sum[i-1]+nums[i-1];// step1
clone=sum;
sort(clone.begin(),clone.end());
tree.resize(sum.size()+1);
unordered_map<long,int>reflect;
for(int i=0;i<clone.size();i++)
reflect[clone[i]]=i;//step2
int res=0;
for(int i=sum.size()-1;i>=0;i--)
{
int idx1=binarysearch(sum[i]+lower,true);
int idx2=binarysearch(sum[i]+upper,false);
res=res+count(idx2)-count(idx1);
add(reflect[sum[i]]); //step3
}
return res;
}int binarysearch(long val, bool includeself)
{
if(includeself)
return lower_bound(clone.begin(),clone.end(),val)-clone.begin();
return upper_bound(clone.begin(),clone.end(),val)-clone.begin();
}
void add(int pos){
pos=pos+1;
while(pos<tree.size())
{
tree[pos]++;
pos=pos+(pos&-pos);
}
}int count(int pos){
int cnt=0;
pos=pos+1;
while(pos>0)
{
cnt=cnt+tree[pos];
pos=pos-(pos&-pos);
}
return cnt;
}
Ошибки:
Входные данные:
[-2,5, -1]
-2
2
Выход:
197
Ожидаемое:
3
И я действительно не знаю, как отформатировать мой код, я всегда писал C ++, как это так …
Извините, это становится немного длинным, я думал, что это в течение нескольких дней все еще понятия не имею, где идет не так, как надо. Любая мысль ценится !!
Мне было трудно понять, как вы пытаетесь использовать двоичное индексированное дерево, но я думаю, что оно у меня есть.
Позвольте мне попытаться объяснить, что я думаю, алгоритм, используя n в качестве длины входного массива.
Я думаю, что наиболее существенная проблема с вашей реализацией заключается в том, что ваше дерево недостаточно велико. Это должно быть немного больше, потому что индекс 0 не используется. Так что используйте
tree.resize(sum.size()+2);
вместо вашего текущего +1
,
Также, если вы хотите использовать метод более одного раза, вам нужно очистить дерево, вернув все значения к нулю, а не просто изменив его размер.
Исправление первой проблемы заставило его работать с вашими примерами данных. Я не заметил каких-либо других проблем с вашим кодом, но я не провел тщательного тестирования.
Других решений пока нет …