Minimum Length Contiguous Subarray Summing to Target

Medium

Given an array of positive integers nums and a target sum target, find a contiguous subarray within nums whose elements sum up to exactly target.

If multiple such subarrays exist, you should return the one with the minimum length. If there are multiple subarrays with the same minimum length that sum to target, return the one that appears first (i.e., has the smallest starting index).

If no such subarray exists that sums to target, return an empty array.

Example 1

Input

[
  "[2, 3, 1, 2, 4, 3]",
  "7"
]

Output

[
  4,
  3
]

Explanation. The subarray `[4, 3]` sums to 7 and has a length of 2. While `[1, 2, 4]` also sums to 7, its length is 3, which is longer. Therefore, `[4, 3]` is the minimum length subarray.

Example 2

Input

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

Output

[]

Explanation. No subarray in `[1, 1, 1, 1, 1]` sums to 10.

Example 3

Input

[
  "[10, 5, 2, 7, 1, 8]",
  "7"
]

Output

[
  7
]

Explanation. The subarray `[7]` sums to 7 and has a length of 1, which is the minimum possible length.

Example 4

Input

[
  "[1, 2, 3, 4, 3]",
  "7"
]

Output

[
  3,
  4
]

Explanation. Both `[3, 4]` and `[4, 3]` sum to 7 and have a length of 2. Since `[3, 4]` appears first (starting at index 2) compared to `[4, 3]` (starting at index 3), it is the correct answer.

Example 5

Input

[
  "[100, 200, 300, 400]",
  "200"
]

Output

[
  200
]

Explanation. The subarray `[200]` sums to 200 and has a length of 1.

Example 6

Input

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

Output

[
  1,
  2,
  3,
  4
]

Explanation. The entire array `[1, 2, 3, 4]` sums to 10 and is the only subarray that does so.

Example 7

Input

[
  "[5]",
  "5"
]

Output

[
  5
]

Explanation. The subarray `[5]` sums to 5 and has a length of 1.

Example 8

Input

[
  "[8, 1, 5, 2, 3]",
  "10"
]

Output

[
  8,
  1
]

Explanation. Subarrays summing to 10 include `[8, 1]` (length 2) and `[5, 2, 3]` (length 3). `[8, 1]` is the shortest.

Example 9

Input

[
  "[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]",
  "5"
]

Output

[
  1,
  1,
  1,
  1,
  1
]

Explanation. The subarray `[1, 1, 1, 1, 1]` sums to 5 and has the minimum length of 5.

Follow-up: Can you solve this problem with a time complexity of O(N)? Consider a sliding window approach.

Constraints:

- `1 <= nums.length <= 10^5` - `1 <= nums[i] <= 10^4` - `1 <= target <= 10^9` - All numbers in `nums` are positive integers.

Views: 12

Minimum Length Contiguous Subarray Summing to Target

Solution

Judge

Minimum Length Contiguous Subarray Summing to Target

Discussion (0)

Solution

Judge