Algorithm
Problem Name: 327. Count of Range Sum
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int count_and_sort(int sort, double *sum, int start, int end, int l, int h, double *tmp) {
int mid;
int n, i, j, k, x, stop;
if (end - start < = 1) return 0;
mid = start + (end - start) / 2;
// divide
n = count_and_sort(1, sum, start, mid, l, h, tmp) +
count_and_sort(1, sum, mid, end, l, h, tmp);
// count
x = 0;
for (i = start; i < mid; i ++) {
stop = 0;
for (j = mid; !stop && j < end; j ++) {
k = sum[j] - sum[i];
// because the second part of sum are sorted, the inner loop can stop early.
if (k > h) stop = 1;
else if (k >= l) n ++;
}
}
// merge sort
if (sort) {
i = start;
j = mid;
k = 0;
while (i < mid && j < end) {
if (sum[i] <= sum[j]) {
tmp[k] = sum[i];
i ++;
} else {
tmp[k] = sum[j];
j ++;
}
k ++;
}
if (i < mid) memcpy(&tmp[k], &sum[i], (mid - i) * sizeof(sum[0]));
if (j < end) memcpy(&tmp[k], &sum[j], (end - j) * sizeof(sum[0]));
memcpy(&sum[start], tmp, (end - start) * sizeof(sum[0]));
}
return n;
}
int countRangeSum(int* nums, int numsSize, int lower, int upper) {
double *sum, *tmp;
int i, j, k, n;
sum = malloc((numsSize + 1) * sizeof(double));
//assert(sum);
sum[0] = 0;
for (i = 0; i < numsSize; i ++) {
sum[i + 1] = sum[i] + (double)nums[i];
}
#if 0 // this is O(n^2) 169ms
n = 0;
for (i = 0; i < numsSize; i ++) {
for (j = i + 1; j < = numsSize; j ++) {
k = sum[j] - sum[i];
if (k >= lower && k < = upper) n ++;
}
}
#else // this is 285ms :)
tmp = malloc((numsSize + 1) * sizeof(double));
//assert(tmp);
n = count_and_sort(0, sum, 0, numsSize + 1, lower, upper, tmp);
free(tmp);
#endif
free(sum);
return n;
}
Input
nums = [-2,5,-1], lower = -2, upper = 2
Output
3
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const countRangeSum = function (nums, lower, upper) {
if (nums.length === 0) return 0
const sums = [nums[0]]
for (let i = 1; i < nums.length; i++) {
sums[i] = sums[i - 1] + nums[i]
}
function merge_sort(A, lo, hi) {
if (hi - lo === 1) {
return sums[lo] >= lower && sums[lo] <= upper ? 1 : 0
}
const mid = lo + Math.floor((hi - lo) / 2)
let counter = merge_sort(A, lo, mid) + merge_sort(A, mid, hi)
let m = mid,
n = mid
for (let i = lo; i < mid; i++) {
while (m !== hi && sums[m] - sums[i] < lower) {
m++
}
while (n !== hi && sums[n] - sums[i] <= upper) {
n++
}
counter += n - m
}
const M = A.slice(lo, mid)
const N = A.slice(mid, hi)
M.push(Number.MAX_SAFE_INTEGER)
N.push(Number.MAX_SAFE_INTEGER)
for (let k = lo, i = 0, j = 0; k < hi; k++) {
A[k] = M[i] < N[j] ? M[i++] : N[j++]
}
return counter
}
return merge_sort(sums, 0, nums.length)
}
Input
nums = [-2,5,-1], lower = -2, upper = 2
Output
3
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def countRangeSum(self, nums, lower, upper):
sums, sm, res = [0], 0, 0
for num in nums:
sm += num
res += bisect.bisect_right(sums, sm - lower) - bisect.bisect_left(sums, sm - upper)
bisect.insort(sums, sm)
return res
Input
nums = [0], lower = 0, upper = 0
Output
1
#4 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0327_CountOfRangeSum
{
public int CountRangeSum(int[] nums, int lower, int upper)
{
var sums = new long[nums.Length + 1];
for (int i = 0; i < nums.Length; i++)
sums[i + 1] = sums[i] + nums[i];
return CountWhileMergeSort(sums, 0, nums.Length + 1, lower, upper);
}
private int CountWhileMergeSort(long[] sums, int start, int end, int lower, int upper)
{
if (end - start < = 1) return 0;
int mid = start + (end - start) / 2;
int count = CountWhileMergeSort(sums, start, mid, lower, upper)
+ CountWhileMergeSort(sums, mid, end, lower, upper);
int j = mid, k = mid, t = mid;
long[] cache = new long[end - start];
for (int i = start, r = 0; i < mid; ++i, ++r)
{
while (k < end && sums[k] - sums[i] < lower) k++;
while (j < end && sums[j] - sums[i] <= upper) j++;
count += j - k;
while (t < end && sums[t] < sums[i]) cache[r++] = sums[t++];
cache[r] = sums[i];
}
for (int i = start; i < t; i++)
sums[i] = cache[i - start];
return count;
}
}
}
Input
nums = [0], lower = 0, upper = 0
Output
1