# Yet another std::lower_bound-based C++ solution

• ``````class Solution {
private:
multimap<int64_t,int> hash; // associating a sum on numbers in the range [0,pos) to pos
vector<int64_t> sums;       // other way around: associating pos to sum of numbers in the range [0,pos)
public:
int countRangeSum(vector<int>& nums, int lower, int upper) {
// preprocessing step: fill in the association arrays above
sums.clear();
hash.clear();
sums.push_back(0); // make sum[0,0] = sum[0,1) to be 0
for(int64_t i=0, sum=0; i<nums.size(); i++){
sum += nums[i];
sums.push_back( sum );
hash.insert( pair<int64_t,int>(sum,i+1) );
}
// now a sum within an interval [i:j] is just sums[j+1]-sums[i] and it should be between lower-upper
// to have a quick (log(N)) check for the lower-upper interval we take advantage of ordering in hash
int retval = 0;
for(int i=0; i<sums.size(); i++){
int64_t s = sums[i];
for( multimap<int64_t,int>::const_iterator it = hash.lower_bound( s + lower ); // find first it that it->first - s >= lower
it != hash.end() && it->first - s <= upper; it++ ){ // iterate till end or till it->first - s <= upper
if( it->second > i ) // make sure it is a non-empty range [i,j] with i<j
retval++;
}
}
return retval;
}
};``````

• @koskot77
Time complexity of this solution should be O(n^2) at least;
Look at this part,

``````for(int i=0; i<sums.size(); i++){
int64_t s = sums[i];
for( multimap<int64_t,int>::const_iterator it = hash.lower_bound( s + lower ); // find first it that it->first - s >= lower
it != hash.end() && it->first - s <= upper; it++ ){ // iterate till end or till it->first - s <= upper
if( it->second > i ) // make sure it is a non-empty range [i,j] with i<j
retval++;
}
}
``````

Even thought you use `hash.lower_bound` which take log(n), but the size between `hash.lower_bound( s + lower )` might be `n` too.
Think about {1,1,1,1,1,1,1} range [-1, 100]

• @yong-cao-7731
Yep, in you example my code will take O(N^2) time to complete because there will be total N^2 ranges to count. I don't yet see a simple way to stay with this design and avoid the nested loop. Guess, I'll need another approach here.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.