How do I approach the 'Minimum Size Subarray in Infinite Array' problem?

You can solve it by utilizing a sliding window and hash table to efficiently track prefix sums and check for subarrays matching the target sum.

What is the time complexity of solving this problem?

The time complexity is generally O(n), where n is the number of elements in the nums array, depending on how the sliding window and hash table are implemented.

What common mistakes should I avoid in this problem?

Make sure you correctly handle the infinite nature of the array, avoid brute force solutions, and be careful with edge cases where no subarray sums to the target.

Can the 'Minimum Size Subarray in Infinite Array' problem have multiple solutions?

Yes, but you are only asked to return the shortest subarray. The algorithm must minimize the length of the valid subarray that sums to the target.

How does the infinite nature of the array impact the solution?

The infinite nature of the array can be abstracted by recognizing the repetition of nums, allowing you to solve the problem efficiently without generating an actual infinite array.

#2875

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

无限数组的最短子数组

给你一个下标从 0 开始的数组 nums 和一个整数 target 。下标从 0 开始的数组 infinite_nums 是通过无限地将 nums 的元素追加到自己之后生成的。请你从 infinite_nums 中找出满足元素和等于 target 的最短子数组，并返回该子数组的长度。如果…

数组哈希表滑动窗口前缀和

题目描述

给你一个下标从 0 开始的数组 nums 和一个整数 target 。

下标从 0 开始的数组 infinite_nums 是通过无限地将 nums 的元素追加到自己之后生成的。

请你从 infinite_nums 中找出满足 元素和 等于 target 的最短子数组，并返回该子数组的长度。如果不存在满足条件的子数组，返回 -1 。

示例 1：

输入：nums = [1,2,3], target = 5
输出：2
解释：在这个例子中 infinite_nums = [1,2,3,1,2,3,1,2,...] 。
区间 [1,2] 内的子数组的元素和等于 target = 5 ，且长度 length = 2 。
可以证明，当元素和等于目标值 target = 5 时，2 是子数组的最短长度。

示例 2：

输入：nums = [1,1,1,2,3], target = 4
输出：2
解释：在这个例子中 infinite_nums = [1,1,1,2,3,1,1,1,2,3,1,1,...].
区间 [4,5] 内的子数组的元素和等于 target = 4 ，且长度 length = 2 。
可以证明，当元素和等于目标值 target = 4 时，2 是子数组的最短长度。

示例 3：

输入：nums = [2,4,6,8], target = 3
输出：-1
解释：在这个例子中 infinite_nums = [2,4,6,8,2,4,6,8,...] 。
可以证明，不存在元素和等于目标值 target = 3 的子数组。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵
1 <= target <= 10⁹

lightbulb

解题思路

方法一：前缀和 + 哈希表

我们先算出数组 $nums$ 的元素总和，记为 $s$ 。

如果 $target \gt s$ ，那么我们可以将 $target$ 减去 $\lfloor \frac{target}{s} \rfloor \times s$ ，这样就可以将 $target$ 减小到 $[0, s)$ 的范围内。那么此时子数组的长度为 $a = \lfloor \frac{target}{s} \rfloor \times n$ ，其中 $n$ 是数组 $nums$ 的长度。

接下来，我们只需要在数组 $nums$ 中，找出长度最短的且元素和等于 $target$ 的子数组，或者长度最短的且前缀和加上后缀和等于 $target$ ，即子数组元素和等于 $s - target$ 的子数组，记长度为 $b$ 。我们可以通过前缀和加哈希表的方法，找出这样的子数组。

如果找到了这样的子数组，那么最终的答案就是 $a + b$ 。否则，答案就是 $-1$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def minSizeSubarray(self, nums: List[int], target: int) -> int:
        s = sum(nums)
        n = len(nums)
        a = 0
        if target > s:
            a = n * (target // s)
            target -= target // s * s
        if target == s:
            return n
        pos = {0: -1}
        pre = 0
        b = inf
        for i, x in enumerate(nums):
            pre += x
            if (t := pre - target) in pos:
                b = min(b, i - pos[t])
            if (t := pre - (s - target)) in pos:
                b = min(b, n - (i - pos[t]))
            pos[pre] = i
        return -1 if b == inf else a + b

speed

复杂度分析

指标	值
时间	complexity depends on the chosen approach. The sliding window and hash table method generally has a time complexity of O(n), while space complexity depends on how the hash table is implemented, usually O(n) for storing prefix sums.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for familiarity with sliding window and hash table patterns.
question_mark
Assess the candidate's ability to handle large arrays and optimize for time and space.
question_mark
Check if the candidate can abstract the infinite array structure into a manageable algorithm using prefix sums.

warning

常见陷阱

外企场景

error
Failing to account for the infinite nature of the array when calculating prefix sums.
error
Using brute force methods that do not leverage the repeating pattern of nums.
error
Not handling edge cases, such as when no subarray sums to the target.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to ask for the longest subarray with a sum equal to the target.
arrow_right_alt
Extend the problem to handle negative numbers in nums.
arrow_right_alt
Change the target to a range (e.g., subarray sum between min and max) instead of a fixed value.

help

常见问题

外企场景

继续练习

#2848 与车相交的点 #2902 和带限制的子多重集合的数目 #2845 统计趣味子数组的数目