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，长度为 2。
可以证明长度为 2 是和等于 target = 5 的子数组的最短长度。

示例 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，长度为 2。
可以证明长度为 2 是和等于 target = 4 的子数组的最短长度。

示例 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^5
  • 1 <= nums[i] <= 10^5
  • 1 <= target <= 10^9

解题思路

这道题的关键在于理解无限数组的本质：原数组会不断重复。我们可以将目标和分解为三部分来考虑：

核心思路：

  1. 设原数组总和为 sum，如果 target >= sum，说明我们可能需要完整的数组重复若干次
  2. 目标和可以表示为：prefix + k * sum + suffix，其中：
    • prefix 是某个前缀和
    • k 是完整数组的重复次数
    • suffix 是某个后缀和

具体步骤：

  1. 计算数组总和，如果所有元素都为正且无法组成目标和，直接返回-1
  2. 使用哈希表记录前缀和及其最早出现位置
  3. 分两种情况处理：
    • 情况1：目标和完全在单个或连续的数组副本中（滑动窗口）
    • 情况2：目标和跨越多个数组副本（前缀+完整数组+后缀的组合）

优化要点：

  • 将数组扩展为两倍长度来处理跨越边界的情况
  • 使用前缀和和哈希表快速查找符合条件的子数组
  • 计算需要的完整数组副本数量，然后寻找最优的前缀后缀组合

代码实现

class Solution {
public:
    int minSizeSubarray(vector<int>& nums, int target) {
        int n = nums.size();
        long long sum = accumulate(nums.begin(), nums.end(), 0LL);
        
        // 扩展数组为两倍长度
        vector<int> extended(nums.begin(), nums.end());
        extended.insert(extended.end(), nums.begin(), nums.end());
        
        int minLen = INT_MAX;
        unordered_map<long long, int> prefixMap;
        prefixMap[0] = -1;
        
        long long prefixSum = 0;
        for (int i = 0; i < 2 * n; i++) {
            prefixSum += extended[i];
            
            // 情况1：直接在扩展数组中找到目标和
            long long need = prefixSum - target;
            if (prefixMap.count(need)) {
                minLen = min(minLen, i - prefixMap[need]);
            }
            
            // 情况2：需要完整的数组副本
            if (sum > 0) {
                long long remainder = target % sum;
                if (remainder == 0) remainder = sum;
                
                long long need2 = prefixSum - remainder;
                if (prefixMap.count(need2)) {
                    int copies = target / sum;
                    if (remainder == sum) copies--;
                    minLen = min(minLen, copies * n + i - prefixMap[need2]);
                }
            }
            
            if (!prefixMap.count(prefixSum)) {
                prefixMap[prefixSum] = i;
            }
        }
        
        return minLen == INT_MAX ? -1 : minLen;
    }
};

class Solution:
    def minSizeSubarray(self, nums: List[int], target: int) -> int:
        n = len(nums)
        total_sum = sum(nums)
        
        # 扩展数组为两倍长度
        extended = nums + nums
        
        min_len = float('inf')
        prefix_map = {0: -1}
        prefix_sum = 0
        
        for i in range(2 * n):
            prefix_sum += extended[i]
            
            # 情况1：直接在扩展数组中找到目标和
            need = prefix_sum - target
            if need in prefix_map:
                min_len = min(min_len, i - prefix_map[need])
            
            # 情况2：需要完整的数组副本
            if total_sum > 0:
                remainder = target % total_sum
                if remainder == 0:
                    remainder = total_sum
                
                need2 = prefix_sum - remainder
                if need2 in prefix_map:
                    copies = target // total_sum
                    if remainder == total_sum:
                        copies -= 1
                    min_len = min(min_len, copies * n + i - prefix_map[need2])
            
            if prefix_sum not in prefix_map:
                prefix_map[prefix_sum] = i
        
        return min_len if min_len != float('inf') else -1

public class Solution {
    public int MinSizeSubarray(int[] nums, int target) {
        int n = nums.Length;
        long sum = nums.Sum(x => (long)x);
        
        // 扩展数组为两倍长度
        int[] extended = new int[2 * n];
        Array.Copy(nums, extended, n);
        Array.Copy(nums, 0, extended, n, n);
        
        int minLen = int.MaxValue;
        Dictionary<long, int> prefixMap = new Dictionary<long, int>();
        prefixMap[0] = -1;
        
        long prefixSum = 0;
        for (int i = 0; i < 2 * n; i++) {
            prefixSum += extended[i];
            
            // 情况1：直接在扩展数组中找到目标和
            long need = prefixSum - target;
            if (prefixMap.ContainsKey(need)) {
                minLen = Math.Min(minLen, i - prefixMap[need]);
            }
            
            // 情况2：需要完整的数组副本
            if (sum > 0) {
                long remainder = target % sum;
                if (remainder == 0) remainder = sum;
                
                long need2 = prefixSum - remainder;
                if (prefixMap.ContainsKey(need2)) {
                    int copies = (int)(target / sum);
                    if (remainder == sum) copies--;
                    minLen = Math.Min(minLen, copies * n + i - prefixMap[need2]);
                }
            }
            
            if (!prefixMap.ContainsKey(prefixSum)) {
                prefixMap[prefixSum] = i;
            }
        }
        
        return minLen == int.MaxValue ? -1 : minLen;
    }
}

var minSizeSubarray = function(nums, target) {
    const n = nums.length;
    const sum = nums.reduce((a, b) => a + b, 0);
    
    const fullCycles = Math.floor(target / sum);
    const remainder = target % sum;
    
    if (remainder === 0) {
        return fullCycles * n;
    }
    
    // Create extended array (2 cycles to handle wraparound)
    const extended = [...nums, ...nums];
    
    // Find shortest subarray with sum = remainder
    let minLen = Infinity;
    let left = 0;
    let currentSum = 0;
    
    for (let right = 0; right < extended.length; right++) {
        currentSum += extended[right];
        
        while (currentSum > remainder && left <= right) {
            currentSum -= extended[left];
            left++;
        }
        
        if (currentSum === remainder) {
            minLen = Math.min(minLen, right - left + 1);
        }
    }
    
    return minLen === Infinity ? -1 : fullCycles * n + minLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n)
空间复杂度O(n)

其中 n 为数组长度。时间复杂度主要来自遍历扩展数组，空间复杂度主要来自哈希表存储前缀和。