class Solution {
public:
int minSizeSubarray(vector<int>& nums, int target) {
}
};
100076. 无限数组的最短子数组
给你一个下标从 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 <= 1051 <= nums[i] <= 1051 <= target <= 109原站题解
python3 解法, 执行用时: 176 ms, 内存消耗: 24.3 MB, 提交时间: 2023-10-02 00:16:24
class Solution:
# 滑动窗口
def minSizeSubarray(self, nums: List[int], target: int) -> int:
total = sum(nums)
n = len(nums)
ans = inf
left = s = 0
for right in range(n * 2):
s += nums[right % n]
while s > target % total:
s -= nums[left % n]
left += 1
if s == target % total:
ans = min(ans, right - left + 1)
return ans + target // total * n if ans < inf else -1
java 解法, 执行用时: 9 ms, 内存消耗: 51.6 MB, 提交时间: 2023-10-02 00:15:54
class Solution {
public int minSizeSubarray(int[] nums, int target) {
long total = 0;
for (int x : nums) total += x;
int n = nums.length;
int ans = Integer.MAX_VALUE;
int left = 0;
long sum = 0;
for (int right = 0; right < n * 2; right++) {
sum += nums[right % n];
while (sum > target % total) {
sum -= nums[left++ % n];
}
if (sum == target % total) {
ans = Math.min(ans, right - left + 1);
}
}
return ans == Integer.MAX_VALUE ? -1 : ans + (int) (target / total) * n;
}
}
cpp 解法, 执行用时: 44 ms, 内存消耗: 41.5 MB, 提交时间: 2023-10-02 00:15:42
class Solution {
public:
int minSizeSubarray(vector<int> &nums, int target) {
long long total = accumulate(nums.begin(), nums.end(), 0LL);
int n = nums.size();
int ans = INT_MAX;
int left = 0;
long long sum = 0;
for (int right = 0; right < n * 2; right++) {
sum += nums[right % n];
while (sum > target % total) {
sum -= nums[left++ % n];
}
if (sum == target % total) {
ans = min(ans, right - left + 1);
}
}
return ans == INT_MAX ? -1 : ans + target / total * n;
}
};
javascript 解法, 执行用时: 96 ms, 内存消耗: 47.4 MB, 提交时间: 2023-10-02 00:15:30
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var minSizeSubarray = function (nums, target) {
const total = _.sum(nums);
const n = nums.length;
let ans = Infinity;
let left = 0, sum = 0;
for (let right = 0; right < n * 2; right++) {
sum += nums[right % n];
while (sum > target % total) {
sum -= nums[left++ % n];
}
if (sum === target % total) {
ans = Math.min(ans, right - left + 1);
}
}
return ans === Infinity ? -1 : ans + Math.floor(target / total) * n;
};
rust 解法, 执行用时: 8 ms, 内存消耗: 2.9 MB, 提交时间: 2023-10-02 00:15:16
impl Solution {
pub fn min_size_subarray(nums: Vec<i32>, target: i32) -> i32 {
let total: i64 = nums.iter().map(|&x| x as i64).sum();
let n = nums.len();
let mut ans = usize::MAX;
let mut left = 0;
let mut sum = 0;
for right in 0..n * 2 {
sum += nums[right % n];
while sum > (target as i64 % total) as i32 {
sum -= nums[left % n];
left += 1;
}
if sum == (target as i64 % total) as i32 {
ans = ans.min(right - left + 1);
}
}
if ans < usize::MAX {
ans as i32 + (target as i64 / total) as i32 * n as i32
} else {
-1
}
}
}
golang 解法, 执行用时: 48 ms, 内存消耗: 7.1 MB, 提交时间: 2023-10-02 00:15:02
func minSizeSubarray(nums []int, target int) int {
total := 0
for _, x := range nums {
total += x
}
ans := math.MaxInt
left, sum, n := 0, 0, len(nums)
for right := 0; right < n*2; right++ {
sum += nums[right%n]
for sum > target%total {
sum -= nums[left%n]
left++
}
if sum == target%total {
ans = min(ans, right-left+1)
}
}
if ans == math.MaxInt {
return -1
}
return ans + target/total*n
}
func min(a, b int) int { if b < a { return b }; return a }