# Sharing c++ solution using std::sort

• ``````class Solution {
public:
int countRangeSum(vector<int>& nums, int lower, int upper) {
int n = nums.size();
if (n == 0) return 0;

vector<pair<int64_t, int>> sums(n, pair<int64_t, int>());

//'first' is the sum of range [0, i] and 'second' stores the original index i
sums[0].first = nums[0];
sums[0].second = 0;
for (int i = 1; i < n; i++)
{
sums[i].first = sums[i - 1].first + nums[i];
sums[i].second = i;
}

// sort 'sums' according to first value
sort(sums.begin(), sums.end(),
[](pair<int64_t, int>& a1, pair<int64_t, int>& a2) { return a1.first < a2.first; });

int count = 0;

// count matches for ranges [0, i]
for (int i = 0; i < n; i++)
if (sums[i].first >= lower && sums[i].first <= upper) count++;

// count matches for other ranges
int strt = 0;
for (int i = 0; i < n; i++)
{
while (strt < n && sums[strt].first < sums[i].first + lower) strt++;
if (strt >= n) break;

int end = strt;
while (end < n && sums[end].first <= sums[i].first + upper)
{
// the corresponding range in 'nums' is [sums[i].second, sums[end].second]
if (sums[i].second < sums[end].second) count++;

end++;
}
}

return count;
}
};
``````

The time complexity is O(max(N lgN, k)), where k is the value of 'count'. The disadvantage of this algorithm is that it is slower than N lgN when k is big. However, the advantage is that we can print all the matches if needed.

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