无限数组的最短子数组

You are given a 0-indexed array nums and an integer target.

A 0-indexed array infinite_nums is generated by infinitely appending the elements of nums to itself.

Return the length of the shortest subarray of the array infinite_nums with a sum equal to target. If there is no such subarray return -1.

 

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.

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105
• 1 <= target <= 109

/*
 * 思路：使用Java Stream API的部分功能，例如IntStream生成重复序列，
 * 但由于滑动窗口和更新最小长度的操作，stream并不完全合适。
 * 为了模拟无限数组，我们在滑动窗口中直接操作原数组。
 */
import java.util.stream.IntStream;

public class StreamSolution {
    public int minSubarrayLength(int[] nums, int target) {
        int n = nums.length;
        int minLength = Integer.MAX_VALUE;
        int currentSum = 0;
        int left = 0;

        for (int right = 0; right < 2 * n; right++) {
            currentSum += nums[right % n];

            while (currentSum >= target) {
                minLength = Math.min(minLength, right - left + 1);
                currentSum -= nums[left % n];
                left++;
            }
        }

        return minLength == Integer.MAX_VALUE ? -1 : minLength;
    }
}

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

O(n)

O(n)