#2875
Minimum Size Subarray in Infinite Array
expert · 1100 · lc medium +32 · verified · 32% accepted · 417 likes · top 10%
Description
A 0-indexed array nums and an integer target are given.
An infinite array infinite_nums is formed by appending nums to itself indefinitely.
Return the length of the shortest contiguous subarray of infinite_nums with sum exactly target, or -1 if no such subarray exists.
Example 1:
Input: nums = [1,2,3], target = 5
Output: 2
Explanation: In this example infinite_nums = [1,2,3,1,2,3,1,2,...].
The subarray in the range [1,2], has the sum equal to target = 5 and length = 2.
It can be proven that 2 is the shortest length of a subarray with sum equal to target = 5.
Example 2:
Input: nums = [1,1,1,2,3], target = 4
Output: 2
Explanation: In this example infinite_nums = [1,1,1,2,3,1,1,1,2,3,1,1,...].
The subarray in the range [4,5], has the sum equal to target = 4 and length = 2.
It can be proven that 2 is the shortest length of a subarray with sum equal to target = 4.
Example 3:
Input: nums = [2,4,6,8], target = 3
Output: -1
Explanation: In this example infinite_nums = [2,4,6,8,2,4,6,8,...].
It can be proven that there is no subarray with sum equal to target = 3.
Code
1
2
3