找出长度< = k且总和== s的子阵列数

Question

我遇到了以下问题：

给定一个整数数组arr，一个正整数k和一个整数s，您的任务是查找长度不大于k且和等于s的非空连续子阵列的数量。

对于< code>arr = [1，2，4，-1，6，1]，< code>k = 3，以及< code>s = 6，输出应为< code >解(arr，k，s) = 3。

• 长度1和等于s=6的连续子数组之间存在1子数组，它是[6]，
• 长度2和等于s=6的连续子数组之间存在1子数组，它是[2,4]，
• 长度3和等于s=6的连续子数组之间存在1子数组，它是[-1,6,1]。

请注意，子数组 [1， 2， 4， -1] 的总和也为 s，但其长度大于 k，因此不适用。

所以答案是3。

下面是我在Python中的尝试。我的想法是将每个前缀和出现的索引存储在字典中。例如，如果前缀和6出现在索引1、3，则字典中的条目将是六：[1，3]。然后，在每个步骤中，我们可以检查是否遇到了目标和＜code＞s＜/code＞以及子阵列的范围。

这通过了10/15的测试案例，但是超出了剩余隐藏案例的时间限制。如果有人有优化的算法，我会很感激。

import collections
def solution(arr, k, s):
    res = 0
    curr = 0
    d = collections.defaultdict(list)
    d[0].append(-1)
    for i, num in enumerate(arr):
        curr += num
        if curr - s in d:
            for idx in d[curr-s]:
                if i - idx <= k:
                    res += 1
        d[curr].append(i)
    return res

Answer 1

我们使用计数字典来跟踪前缀和的计数。我们还将使用大小为k的滑动窗口，根据前面的索引增加前缀和的计数，并根据后面的索引递减它。在我们递减之前，我们将根据累积和的计数添加到有效子数组的计数中，该计数比我们的后面累积和多k。

  def solution(arr, k, s)
    num_subarrays = 0
    front_cumulative_sum = 0
    rear_cumulative_sum = 0
    cumulative_sum_to_count = Hash.new { |h, cumsum| h[cumsum] = 0 }
    0.upto(arr.size - 1 + k) do |front_index|
      front_cumulative_sum += arr[front_index] if front_index <= arr.size - 1
      cumulative_sum_to_count[front_cumulative_sum] += 1 if front_index <= arr.size - 1
      if front_index >= k
        rear_index = front_index - k
        rear_cumulative_sum += arr[rear_index]
        num_subarrays += cumulative_sum_to_count[s + rear_cumulative_sum]
        cumulative_sum_to_count[rear_cumulative_sum] -= 1
      end
    end
    return num_subarrays
  end


> arr = [1,2,4,-1,6,1]
> k=3
> s=6
> solution(arr, k, s)
=> 3