“This is the third day of my participation in the First Challenge 2022. For details: First Challenge 2022”

327. Number of sums of intervals

You are given an integer array nums and two integers lower and upper. Find the number of sums within the range lower, upper (both lower and upper).

The interval and S(I, j) represent the sum of the elements in position from I to j in NUMS, including I and j (I ≤ j).

Example 1:

Input: nums = [-2,5,-1], lower = -2, upper = 2 output: 3 description: there are three ranges: [0,0], [2,2], and [0,2]. The corresponding ranges and sums are -2, -1, and 2 respectively.Copy the code

Example 2:

Input: nums = [0], lower = 0, upper = 0 Output: 1Copy the code

Tip:

  • 1 <= nums.length <= 105
  • -231 <= nums[i] <= 231 – 1
  • -105 <= lower <= upper <= 105
  • The question data guarantees that the answer is a 32-bit integer

Merge sort

Train of thought

I want to take the interval sum, that is, the sum of the values from I to j.

How do you merge, sort the array and get messed up?

We can use merge sort here, but how does an interval sum relate to an interval sum? Interval sum is the sum of some element in the original array, and if you sort it then the data will get confused and you won’t get the original interval sum.

Here we can use the prefix sum subtly, storing the sum of the interval from I to j in the j bit of the new prefix and array (specifically, the j+1 bit), so that we can get the sum of the interval from I +1 to j from the original array by subtracting the JTH bit from the JTH bit of the sum.

[0,1] [0,1] [0,..j] can be obtained by subtracting the JTH bit of the prefix sum from the 0th bit, so it is exactly stored in the j+1 bit

How can we quickly get the interval and the number that satisfy this condition?

It’s much faster to get [lower, upper] because you don’t have to go through all of them. In merging we get two ordered arrays sums1 and sums2. We label sums1 with I, and SUMs2 with l and R, Traversing each bit of SUMs1 and differentiating each bit of SUMs2 (sums2[l]-sums1[I])

  • If it’s less than lowwer, it doesn’t satisfy the question, and l++ continues until the difference is greater than or equal to lowwer, then it’s an interval sum satisfying the question starting at L
  • R >=l, so long as r is within the effective subindex, then r continues to move the sums[r]-sums[I] if less than upper continue to move r++ to the last sums
  • So [l,r] minus I is r times

Concrete implementation:

  • Find the prefix and merge sort
  • Split the prefix and from the middle, recursively process the left and right parts, the recursive termination condition is naturally ordered when it is divided into 1-bit elements, and directly return itself and the total number of times satisfying the condition 0
  • Find the number of conditions between two ordered sequences according to the above idea
  • And then you sort it, and at the end of the sort you get the final answer
var countRangeSum = function (nums, lower, upper) {
    // Find the interval sum associated with prefix and prefix sum
    // The interval and S(I, j) represent the sum of the elements in nums from I to j, including I and j (I ≤ j).
    // The sums (I,j) can be used to state the interval and the sums (I,j) in prefixes and sums. So in order to express the endpoints you need to add a 0 to the prefix and the initial value.
    var sums = [0]
    var total = 0
    for (var i = 0; i < nums.length; i++) {
        sums.push(total += nums[i])
    }
    const result = computedS(sums, lower, upper)
    return result[1]};var computedS = function (sums, lower, upper) {
    if (sums.length < 2) return [sums, 0]
    var mid = Math.floor((sums.length) / 2);
    var left = sums.slice(0, mid)
    var right = sums.slice(mid)
    var [sums1, n1] = computedS(left, lower, upper)
    var [sums2, n2] = computedS(right, lower, upper)
    var res = n1 + n2
    // declare l and r to point to the first item in the right array
    var i = 0;
    var l = r = 0
    // Loop statistics
    while (i <= mid - 1) {
        while (l <= sums2.length - 1 && sums2[l] - sums1[i] < lower) l++
        while (r <= sums2.length - 1 && sums2[r] - sums1[i] <= upper) r++
        res += (r - l)
        i++
    }


    var arr = []
    var p1 = p2 = 0
    var index = 0
    while (p1<sums1.length || p2<sums2.length) {
        if (p1 >= sums1.length) {
            arr[index++] = sums2[p2++]
        } else if (p2 >= sums2.length) {
            arr[index++] = sums1[p1++]
        }else if (sums1[p1] < sums2[p2]) {
            arr[index++] = sums1[p1++]
        } else {
            arr[index++] = sums2[p2++]
        }
    }
    return [arr, res]
}
Copy the code