2875.无限数组的最短子数组

给你一个下标从 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^5
• 1 <= nums[i] <= 10^5
• 1 <= target <= 10^9

思路逐步进化：

class Solution {
    public int minSizeSubarray(int[] nums, int target) {

        //来考虑下思路：
        // 1. 需要让nums循环起来.
        // 2. 不能让nums无限循环
        // 3. 停止策略.

        //先按照简单情况写出来：
        // 即：在这个数组中，一次循环就行找到最短=他的数组
        //我们先按照简单情况把这个滑动窗口写出来.之后再优化.
        int result = Integer.MAX_VALUE;
        int left = 0;
        int sum = 0;
        for (int right = 0; right < nums.length ; right++){
            sum+= nums[right];
            while(sum >= target){
                //减去left的值.
                if(sum == target){
                    result = Math.min(result,right - left + 1);
                    break;
                }
                sum -= nums[left];
                left++;
            }
        }
        return result == Integer.MAX_VALUE ? -1 : result;        
    }
}

OK，我们也知道上面的程序是无法满足循环数组的情况的。

那么怎么能让数组循环起来呢？且又控制循环次数；即我们要找到控制结果值的条件是什么？

很明显，target是我们要找到的结果值，假如这个值足够大，那么是不是就需要我们循环多次这个数组才能得到。

假设：[1,2,3] target刚好是 : 7或者 9。

ok，人脑的思路是什么？1,2,3,1,2,3

7是大于 1+2+3 = sum = 6的，那么，1,2,3,1。顺利组队.

9是 大于 1+2+3 = sum = 6的，那么 3,1,2,3 顺利组队。

那么我们是否能把target都转换为7,9这些内容呢？

感觉可以.

那么思路可以是：

Target / sum = cycle (循环次数 )

然后在2n长度的数组中，找到 target%sum = 目标值.

看样子我们思路没啥问题.

结果出来啦：

class Solution {
    public int minSizeSubarray(int[] nums, int target) {

        int length = nums.length;

        int[] newNums = new int[2* length];
        int nSum = 0;
        for(int i = 0; i< nums.length ; i++){
            nSum += nums[i];
            newNums[i] = newNums[i+length] = nums[i];
        }

        int cycle = target / nSum; //循环次数
        //新目标值
        int newTarget = target % nSum;

        // System.out.println("cycle = " + cycle + "; newTarget = " + newTarget);

        int result = Integer.MAX_VALUE;
        int left = 0;
        int sum = 0;

        for (int right = 0; right < newNums.length ; right++){
            sum+= newNums[right];
            while(sum > newTarget){
                //减去left的值.
                sum -= newNums[left];
                left++;
            }
            if(sum == newTarget){
                result = Math.min(result,right - left + 1);
            }
        }
        return result == Integer.MAX_VALUE ? -1 : ((cycle == 0) ? result : (cycle * length + result));        
    }

}