题目描述
给你一个下标从 0 开始的数组 nums
和一个整数 target
。
下标从 0 开始的数组 infinite_nums
是通过无限地将 nums
的元素追加到自己之后生成的。
请你从 infinite_nums
中找出满足 元素和 等于 target
的 最短 子数组,并返回该子数组的长度。如果不存在满足条件的子数组,返回 -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 是子数组的最短长度。
输入: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 是子数组的最短长度。
输入: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
算法
(思维题,双指针) $O(n)$
- 先求出数组的总和 $sum$。
- 令 $lp$ 等于 $target$ 除以 $sum$ 下取整的值,表示需要循环 $lp$ 轮。
- $target$ 自身模去 $sum$,后面需要在一个循环数组内找到值为 $target$ 的子数组。
- 在原数组的后面复制一份原数组,处理循环数组。
- 在新数组上使用双指针的方式求出区间和恰好等于 $target$ 的子数组,找到长度最小的区间。
- 将最小的区间加上 $lp \cdot n$ 就是答案。
时间复杂度
- 遍历数组两次,时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间处理循环数组。
C++ 代码
#define LL long long
class Solution {
public:
int minSizeSubarray(vector<int>& nums, int target) {
const int n = nums.size();
LL sum = 0;
for (int x : nums)
sum += x;
int lp = target / sum;
target %= sum;
nums.insert(nums.end(), nums.begin(), nums.end());
LL t = 0;
int ans = INT_MAX;
for (int i = 0, j = 0; i < 2 * n; i++) {
t += nums[i];
while (j <= i && t > target) {
t -= nums[j];
j++;
}
if (t == target)
ans = min(ans, i - j + 1);
}
if (ans == INT_MAX)
return -1;
return ans + lp * n;
}
};