无限数组的最短子数组

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

难度: Medium

给你一个下标从 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 <= 105
  • 1 <= nums[i] <= 105
  • 1 <= target <= 109

Submission

运行时间: 87 ms

内存: 25.2 MB

class Solution:
    def minSizeSubarray(self, nums: List[int], target: int) -> int:
        def mx_sub(t, l, flag):
            # 通过滑窗寻找最长和为t的子数组
            left = 0
            cur = 0
            mx = 0 if flag else inf
            for r, x in enumerate(l):
                cur += x
                while cur > t:
                    cur -= l[left]
                    left += 1
                if cur == t:
                    if flag:
                        mx = max(mx, r - left + 1)
                    else:
                        mx = min(mx, r - left + 1)
            return mx


        total = sum(nums)
        n = len(nums)
        ans = inf
        if total > target:
            ans = mx_sub(target, nums, False)

        cnt = target // total * n
        rest = target % total
        if not rest:
            return cnt
        target = total - rest

        ans = min(ans, cnt + n - mx_sub(target, nums + nums if cnt else nums, True))
        if ans % n == 0:
            return -1
        return ans

Explain

此题解首先考虑了nums数组和target的关系。通过滑动窗口方法寻找一个或多个连续子数组的和等于给定target的最短长度。主要分为以下几步：1. 计算nums数组的总和total。2. 根据target与total的比较，决定是否可以通过简单的除法运算直接得出结果。3. 使用辅助函数mx_sub来找到和为特定值的最短或最长子数组。4. 处理target分成total的整数倍和余数的情况，通过适当的调整和组合，尝试找到符合条件的最短子数组。代码中使用了两次mx_sub函数，分别处理求最短子数组和最长子数组的情况。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def minSizeSubarray(self, nums: List[int], target: int) -> int:
        def mx_sub(t, l, flag):
            # flag为True时，寻找最长的和为t的子数组，为False时寻找最短的
            left = 0
            cur = 0
            mx = 0 if flag else inf
            for r, x in enumerate(l):
                cur += x
                while cur > t:
                    cur -= l[left]
                    left += 1
                if cur == t:
                    if flag:
                        mx = max(mx, r - left + 1)
                    else:
                        mx = min(mx, r - left + 1)
            return mx

        total = sum(nums)
        n = len(nums)
        ans = inf
        if total > target:
            ans = mx_sub(target, nums, False)

        cnt = target // total * n
        rest = target % total
        if not rest:
            return cnt
        target = total - rest

        ans = min(ans, cnt + n - mx_sub(target, nums + nums if cnt else nums, True))
        if ans % n == 0:
            return -1
        return ans

Explore

这种比较有助于快速确定解决方案的方向或简化问题。如果`total`小于`target`，那么不可能有任何子数组的和等于`target`，因此可以直接返回无解。如果`total`恰等于`target`，则整个数组就是所需的子数组，也就无需进一步查找。最后，如果`total`大于`target`，则可能存在一个或多个子数组的和等于`target`，这时候需要通过滑动窗口等方法进一步寻找。

`flag`参数在`mx_sub`函数中用以区分查找最长或最短满足条件的子数组。当`flag`为True时，函数寻找和为`t`的最长子数组；当`flag`为False时，寻找和为`t`的最短子数组。这通过在找到和为`t`的子数组时，使用`max`或`min`函数来更新结果来实现，即保留历史中最大或最小的子数组长度。

为了处理可能跨越数组边界的子数组，题解中采用了将`nums`数组自身与其副本拼接的方法（`nums + nums`），从而模拟一个循环数组的环境。这样，即使子数组从原数组的末尾开始并延续到开头，也可以被视为数组中连续的部分，从而正确地计算其长度。

选择`target = total - rest`而不是`rest`的原因在于，这样可以转换为查找数组中和为`total - rest`的最长子数组，然后用整个数组的长度减去这个最长子数组的长度，得到和为`rest`的最短子数组的长度。这种转换是基于数学关系和问题转化的思想，将原问题转换为更容易计算和理解的形式。