Here, We see Count of Range Sum LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
![Count of Range Sum LeetCode Solution](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2024/02/LeetCode-Problem-Solution.png?resize=200%2C200&ssl=1)
Count of Range Sum LeetCode Solution
Table of Contents
Problem Statement
Given an integer array nums
and two integers lower
and upper
, 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
inclusive, where i <= j
.
Example 1:
Input: nums = [-2,5,-1], lower = -2, upper = 2
Output: 3
Explanation: The three ranges are: [0,0], [2,2], and [0,2] and their respective sums are: -2, -1, 2.
Example 2:
Input: nums = [0], lower = 0, upper = 0
Output: 1
Count of Range Sum LeetCode Solution C++
class Solution {
public:
int countRangeSum(vector<int>& nums, int lower, int upper) {
if (nums.size() == 0)
return 0;
vector<long long> cums(nums.size(), 0);
cums[0] = nums[0];
for (int i = 1; i < nums.size(); ++i)
cums[i] = cums[i - 1] + nums[i];
vector<long long> tmp(nums.size());
return recursive_count(cums, 0, nums.size() - 1, tmp, lower, upper);
}
int recursive_count(vector<long long>& cums, int i, int j, vector<long long>& tmp, int lower, int upper) {
if (i == j)
return cums[i] >= lower && cums[i] <= upper;
if (i > j)
return 0;
int mid = (i + j) / 2;
int left = recursive_count(cums, i, mid, tmp, lower, upper);
int right = recursive_count(cums, mid + 1, j, tmp, lower, upper);
int p = i, q = i, k = mid + 1;
int cross = 0;
for (k = mid + 1; k <= j; ++k) {
while (p <= mid && cums[k] - cums[p] > upper)
++p;
while (q <= mid && cums[k] - cums[q] >= lower)
++q;
cross += q - p;
}
p = i; q = mid + 1; int o = i;
while (p <= mid || q <= j) {
long long v1 = (p <= mid ? cums[p] : LONG_MAX);
long long v2 = (q <= j ? cums[q] : LONG_MAX);
if (v1 < v2)
tmp[o++] = cums[p++];
else
tmp[o++] = cums[q++];
}
copy(tmp.begin() + i, tmp.begin() + j + 1, cums.begin() + i);
return left + right + cross;
}
};
Code language: PHP (php)
Count of Range Sum LeetCode Solution Java
class Solution {
public int countRangeSum(int[] nums, int lower, int upper) {
int n = nums.length;
long[] sums = new long[n + 1];
for (int i = 0; i < n; ++i)
sums[i + 1] = sums[i] + nums[i];
int ans = 0;
for (int i = 0; i < n; ++i)
for (int j = i + 1; j <= n; ++j)
if (sums[j] - sums[i] >= lower && sums[j] - sums[i] <= upper)
ans++;
return ans;
}
}
Code language: PHP (php)
Count of Range Sum Solution JavaScript
var countRangeSum = function (nums, lower, upper) {
let preSum = Array(nums.length + 1).fill(0);
let count = 0;
for (let i = 0; i < nums.length; i++) {
preSum[i + 1] = preSum[i] + nums[i];
}
const sort = function (preSum) {
if (preSum.length === 1) return preSum;
let mid = Math.floor(preSum.length / 2);
let left = sort(preSum.slice(0, mid));
let right = sort(preSum.slice(mid))
return merge(left, right);
}
const merge = function (left, right) {
let start = 0;
let end = 0;
for (let i = 0; i < left.length; i++) {
while (start < right.length && right[start] - left[i] < lower) {
start++;
}
while (end < right.length && right[end] - left[i] <= upper) {
end++;
}
count += end - start;
}
let sort = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
sort.push(left.shift());
} else {
sort.push(right.shift());
}
}
return [...sort, ...left, ...right];
}
sort(preSum);
return count;
};
Code language: JavaScript (javascript)
Count of Range Sum Solution Python
class Solution(object):
def countRangeSum(self, nums, lower, upper):
first = [0]
for num in nums:
first.append(first[-1] + num)
def sort(lo, hi):
mid = (lo + hi) / 2
if mid == lo:
return 0
count = sort(lo, mid) + sort(mid, hi)
i = j = mid
for left in first[lo:mid]:
while i < hi and first[i] - left < lower: i += 1
while j < hi and first[j] - left <= upper: j += 1
count += j - i
first[lo:hi] = sorted(first[lo:hi])
return count
return sort(0, len(first))