Hello, everybody. Today I would like to share with you the number of interval sum of the next LeetCode difficult problem

Here is mainly to share ideas and comments, for you to better understand the problem solution, the code part is to refer to LeetCode translated into javascript code,

The title

You are given an array of integers, nums, and two integers, lower and upper. Finds the number of ranges in the array whose values fall within the range [lower, upper] (including lower and upper).

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

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 are -2, -1, and 2 respectively.Copy the code

Analysis of the

Calculate the interval S(I,j), using the definition of prefix S(I,j)===preSum(j) -presum (I -1),

Such as array [1, 2, 3, 4, 5] prefix preSum = = =,3,6,10,15 [1], the S (1, 3) = preSum (3) – preSum 10-1 (0) = = = = = = 9

So this is equivalent to lower<= preSum(j) -presum (I -1)<=upper

So the number of intervals is just to find how many times (j, I minus 1) are members of [lower,upper]

There are many ways to do this, and I’ll share two of them here

1. Merge sort

2. Binary search

Solution a:Merge sort

The code is reproduced at leetcode-cn.com/problems/co…

Train of thought1.The idea of merge sort is to take an array and break it up into its smallest units, and then compare the sizes and sort them and then combine them layer by layer, so that's pretty much the way we want it to be, and all we need to do is2a1.i-1<j
  2.Ordered sequence (it doesn't matter if it's ordered or not ordered, because the total number of intervals that satisfy the condition is the same)2.When you find the conditions j and I - at each level of the recursion1And take the j - (I -1) to obtain the number of groups that meet the condition3.And then you add up the numbers that satisfyvar countRangeSum = (nums, lower, upper) = > {
  let sum = 0;
  // The first value of the preSum is 0 because the coopers preSum(i-1) is required
  let preSum = [0];
  for (let i = 0; i < nums.length; i++) {
    sum += nums[i];
    preSum.push(sum);
  }

  return countRangeSumRecursive(preSum, lower, upper, 0, preSum.length - 1);
};

function countRangeSumRecursive(preSum, lower, upper, left, right) {
  // Return 0 when I -1===j
  if (left === right) {
    return 0;
  }

  const mid = Math.floor((left + right) / 2);
  // preSum[left] -Number of preSum[mid] that satisfy the condition
  const n1 = countRangeSumRecursive(preSum, lower, upper, left, mid);
  PreSum [mid+1] -presum [right] Specifies the number of preSum[right] that satisfies the condition
  const n2 = countRangeSumRecursive(preSum, lower, upper, mid + 1, right);
  // res records the total number
  let res = n1 + n2;

  // Solve for the number of satisfying conditions
  let i = left,
    l = mid + 1,
    r = mid + 1;
  When I >mid, it terminates when I >mid, where I represents the ordered array on the left, and L and r represent the ordered array */ on the right

  while (i <= mid) {
    while (l <= right && preSum[l] - preSum[i] < lower) l++;
    while (r <= right && preSum[r] - preSum[i] <= upper) r++;
    // Find the number of intervals that satisfy the condition
    res += r - l;
    i++;
  }

  // Merge ordered arrays
  let sorted = [];
  let p = 0;
  let p1 = left;
  let p2 = mid + 1;

  while (p1 <= mid || p2 <= right) {
    if (p1 > mid) {
      sorted[p++] = preSum[p2++];
    } else if (p2 > right) {
      sorted[p++] = preSum[p1++];
    } else {
      if (preSum[p1] <= preSum[p2]) {
        sorted[p++] = preSum[p1++];
      } else{ sorted[p++] = preSum[p2++]; }}}// Update preSum to an ordered sequence
  for (let i = 0; i < sorted.length; i++) {
    preSum[left + i] = sorted[i];
  }

  return res;
}
/* Complexity time O(n logn) space O(n) */
Copy the code

Method 2:Binary search

The code is reproduced at leetcode-cn.com/problems/co…

Train of thought1.lower<=preSum(j)-preSum(i-1) < =upper= > preSum(j)-upper<=pre(i-1) < = preSum (j) - the lower,2.PreSum (j)-upper<=pre(I -)1)<=preSum(j)-lower satisfies the interval condition3.This refers to bisect_left and bisect_right (which I'll share later, but won't go into detail here) */ in binary search// Find the leftmost index
function bisect_left(nums, target) {
  let l = 0,
    r = nums.length - 1;

  while (l <= r) {
    const mid = Math.floor(l + (r - l) / 2);
    if (nums[mid] >= target) {
      r = mid - 1;
    } else {
      l = mid + 1; }}return l;
}

// Find the rightmost index
function bisect_right(nums, target) {
  let l = 0,
    r = nums.length - 1;

  while (l <= r) {
    const mid = Math.floor(l + (r - l) / 2);
    if (nums[mid] <= target) {
      l = mid + 1;
    } else {
      r = mid - 1; }}return l;
}

var countRangeSum = (nums, lower, upper) = > {
  let sum = 0;
  // The first value of the preSum is 0 because the coopers preSum(i-1) is required
  let preSum = [0];
  let res = 0;

  // Iterate over each nums value
  for (const num of nums) {
    sum += num;

    PreSum (j); preSum(I -1);
    const n1 = bisect_right(preSum, sum - lower);
    const n2 = bisect_left(preSum, sum - upper);
    res += n1 - n2;

    preSum.push(sum);
    / / sorting
    preSum.sort((a, b) = > a - b);
  }

  return res;
};

/* Complexity time O(n logn) space O(n) */


Copy the code

conclusion

This problem is a little bit difficult, it requires a lot of prefixes, prefixes, binary search, merge sort, you need to know to understand

You can look at a column I share (front-end algorithm) there are more questions about the algorithm to share, I hope to help you, I will try to keep updated every night, if you like the trouble to help me a like, thank you very much

The purpose of this article is to study, discuss and share the experience in the process of learning algorithm. Part of the material in this article comes from the network. If there is infringement, please contact delete, [email protected]