Force button 1343 problem, array, sliding window solution

The title

You are given an integer array arr and two integers k and threshold.

Return the number of subarrays of length k with an average value greater than or equal to threshold.

The sample

Input: arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4 output: 3

Explanation: the average values of the subarrays [2,5,5],[5,5,5] and [5,5,8] are 4,5 and 6, respectively. The average value of the other subarrays of length 3 is less than 4 (threshold).

Input: arr = [1,1,1,1,1], k = 1, threshold = 0 Output: 5

Input: arr =,13,17,23,29,31,7,5,2,3 [11], k = 3, the output threshold = 5:6

Explanation: The average value of the first six subarrays of length 3 is greater than 5. Note that the average is not an integer.

Input: arr = [7,7,7,7,7,7], k = 7, threshold = 7 Output: 1

Input: ARr = [4,4,4], k = 4, threshold = 1 Output: 1

prompt

1 <= arr.length <= 10^5
1 <= arr[i] <= 10^4
1 <= k <= arr.length
0 <= threshold <= 10^4

My answer key

var numOfSubarrays = function(arr, k, threshold) {

  // The sum of elements stored in the current window

  // The sums/k >= threshold are sums >= k * threshold

  let sums = 0;

  // Target return value

  let nums = 0;

  const len = arr.length;

  // Target total

  const target = k * threshold;



  // return 0

  if (arr.length < k) return 0;



  // The window in the first position

  for (let i = 0; i < k; i++) {

    sums += arr[i];

  }



  // Check whether the window in the first position meets the condition

  if (sums >= target)  nums++;



  // Slide the window, remove the previous bit each time, add the next bit

  for (let i = k; i < len; i++) {

    // Add the last bit

    sums += arr[i];

    // remove the previous digit

    sums -= arr[i - k];

    // Determine whether the subarray generated by this slide is valid

    if (sums >= target) nums++;

  }



  return nums;

};

Copy the code

parsing

The key word in this question is “subarray”, not “arbitrary element”. Subarrays are arrays that are joined together in the original array, not in reverse order. So this problem we can use a common array algorithm: the sliding window algorithm to do. This problem in our way of thinking is that the k value is fixed, so our window length is fixed, so every time as long as the “sliding”, remove the far left, add the most the right side of the can, and do not need to bear on the storage array, so we can use a Number type to store used for contrast k * threshold value. The following is my solution, mainly the idea rather than the concrete implementation, so I have added some comments in the code, I hope to help you.

Force button 1343 problem, array, sliding window solution