Closest Fixed Window Sum

ArraySliding Window

Given an array of integers nums, a window size k, and an integer target, find a contiguous subarray of size k whose sum is closest to target.

Return the minimum absolute difference between the sum of any contiguous subarray of length k and target.

Example 1

Input

[
  "[10]",
  "1",
  "10"
]

Output

Explanation. The only subarray of size 1 is [10] with sum 10, equal to target.

Example 2

Input

[
  "[1, 4, 2, 10, 2, 3, 1, 0]",
  "3",
  "15"
]

Output

Explanation. Subarray [10, 2, 3] of length 3 has sum 15, which matches target 15 with absolute difference 0.

Example 3

Input

[
  "[5, -2, 3, 1, -4, 6]",
  "2",
  "7"
]

Output

Explanation. Subarray [3, 1] has sum 4, giving an absolute difference of |4 - 7| = 3, which is the minimum among all size 2 subarrays.

Example 4

Input

[
  "[-5, -10, -15, -20]",
  "2",
  "-22"
]

Output

Explanation. Subarray [-10, -15] has sum -25. Absolute difference with -22 is |-25 - (-22)| = 3.

Example 5

Input

[
  "[1, 2, 3, 4, 5]",
  "5",
  "100"
]

Output

Explanation. The entire array sum is 15. The absolute difference from 100 is |15 - 100| = 85.

Follow-up: Can you solve this in O(N) time complexity and O(1) extra space using a fixed-size sliding window?

Constraints:

`1 <= k <= nums.length <= 10^5` `-10^4 <= nums[i] <= 10^4` `-10^9 <= target <= 10^9`

Views: 3