Subarray Size Equals K

The Problem

Given an integer array arr, an integer k, and a target integer target, count the number of contiguous subarrays of size exactly k whose elements sum to exactly target.

arr = [1, 2, 3, 4, 5],  k = 3,  target = 9   →  1   ([2, 3, 4])
arr = [1, 1, 1, 1, 1],  k = 2,  target = 2   →  4   ([1,1],[1,1],[1,1],[1,1])
arr = [3, 1, 4, 1, 5],  k = 2,  target = 5   →  2   ([1,4],[4,1])
arr = [1, 2, 3],         k = 4,  target = 6   →  0   (no window of size 4 exists)

Examples

Example 1

Input:  arr = [1, 2, 3, 4, 5],  k = 3,  target = 9
Output: 1
Explanation: Only [2, 3, 4] sums to 9.

Example 2

Input:  arr = [1, 1, 1, 1, 1],  k = 2,  target = 2
Output: 4
Explanation: Every adjacent pair [1,1] sums to 2, and there are 4 such pairs.

Example 3

Input:  arr = [3, 1, 4, 1, 5],  k = 2,  target = 5
Output: 2
Explanation: [1,4] at indices 1-2 and [4,1] at indices 2-3 both sum to 5.

Intuition

There are exactly n − k + 1 windows of size k in an array of length n. The brute force sums each window from scratch — recomputing k − 1 shared elements every time a window slides.

The fixed sliding window fixes this: maintain a running window_sum. When the window slides right by one step, subtract the element leaving from the left and add the element entering from the right. One subtraction + one addition replaces an entire inner loop.

For this problem, after each slide we simply check: does window_sum == target? If yes, increment the count.

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart TB
  Init(["start=0, end=0, window_sum=0, count=0"])
  Loop{"end < len(arr)?"}
  Expand["① window_sum += arr[end]"]
  Contract{"end − start + 1 > k?"}
  Remove["window_sum -= arr[start]<br/>start += 1"]
  Process{"end − start + 1 == k?"}
  Check{"window_sum == target?"}
  Inc["count += 1"]
  Advance["end += 1"]
  Done(["return count"])

  Init --> Loop
  Loop -->|"yes"| Expand --> Contract
  Contract -->|"yes"| Remove --> Process
  Contract -->|"no"| Process
  Process -->|"yes"| Check
  Process -->|"no"| Advance
  Check -->|"yes"| Inc --> Advance
  Check -->|"no"| Advance
  Advance --> Loop
  Loop -->|"no"| Done

Subarray Size Equals K — expand, contract if oversized, then check the sum when the window reaches exactly size k.

Brute Force: Nested Loops, O(N × k)

from typing import List

def count_subarrays_brute(arr: List[int], k: int, target: int) -> int:
    n     = len(arr)
    count = 0

    # Try every valid starting position
    for i in range(n - k + 1):
        window_sum = 0

        # Sum the k elements starting at index i — recomputes shared elements every time
        for j in range(k):
            window_sum += arr[i + j]

        if window_sum == target:
            count += 1

    return count

print(count_subarrays_brute([1, 2, 3, 4, 5], 3, 9))  # 1
print(count_subarrays_brute([1, 1, 1, 1, 1], 2, 2))  # 4

n=5,  valid windows: i = 0, 1, 2  (n - k + 1 = 3)

i=0: 1+2+3 = 6  ≠ 9
i=1: 2+3+4 = 9  == 9 → count=1   (2 and 3 were already summed in i=0 — recomputed)
i=2: 3+4+5 = 12 ≠ 9              (3 and 4 were already summed in i=1 — recomputed again)

Return: 1 ✓  —  total additions: 9 (3 windows × 3 elements)

Solution

from typing import List

class Solution:
    def count_subarrays_with_sum(self, arr: List[int], k: int, target: int) -> int:
        # Initialize the window boundaries
        start      = 0
        end        = 0
        # Running sum of elements in the current window
        window_sum = 0
        count      = 0

        while end < len(arr):
            # ① Expand: add the incoming element to the window sum
            window_sum += arr[end]

            # ② Contract: if window grew past k, evict the outgoing element
            if end - start + 1 > k:
                window_sum -= arr[start]
                start += 1

            # ③ Process: when window is exactly k, check if sum matches target
            if end - start + 1 == k:
                if window_sum == target:
                    count += 1

            end += 1

        return count


sol = Solution()
print(sol.count_subarrays_with_sum([1, 2, 3, 4, 5], 3, 9))   # 1
print(sol.count_subarrays_with_sum([1, 1, 1, 1, 1], 2, 2))   # 4
print(sol.count_subarrays_with_sum([3, 1, 4, 1, 5], 2, 5))   # 2
print(sol.count_subarrays_with_sum([1, 2, 3], 4, 6))          # 0
print(sol.count_subarrays_with_sum([5], 1, 5))                # 1

Dry Run — Example 2

arr = [1, 1, 1, 1, 1], k = 2, target = 2

start=0, end=0, window_sum=0, count=0

end=0: ① sum += arr[0]=1 → sum=1. size=1, not k=2.
end=1: ① sum += arr[1]=1 → sum=2. size=2==k → sum==target=2 → count=1.
end=2: ① sum += arr[2]=1 → sum=3. ② size=3>k → sum-=arr[0]=1 → sum=2, start=1.
       ③ size=2==k → sum==target=2 → count=2.
end=3: ① sum += arr[3]=1 → sum=3. ② size=3>k → sum-=arr[1]=1 → sum=2, start=2.
       ③ size=2==k → sum==target=2 → count=3.
end=4: ① sum += arr[4]=1 → sum=3. ② size=3>k → sum-=arr[2]=1 → sum=2, start=3.
       ③ size=2==k → sum==target=2 → count=4.
end=5: end >= n=5 → loop exits.

Return: 4 ✓

Every adjacent pair [1,1] sums to 2.
Each iteration: add right, remove left, check — all in O(1).

Complexity Analysis

Versus brute force O(N × k) — the sliding window replaces the inner loop of k additions with 2 operations (one add, one subtract).

Edge Cases

Key Takeaway

Subarray Size Equals K is the simplest fixed sliding window problem: maintain a running sum, add on expand, subtract on contract, check on full-size. The count increments every time the window sum hits the target. The time drops from O(N × k) to O(N) because the shared elements between adjacent windows are updated in O(1) instead of recomputed.