C.滑动窗口-越长越合法/求最短/最小——2875. 无限数组的最短子数组
·
题目链接：2875. 无限数组的最短子数组（中等）
算法原理：
解法：滑动窗口
击败99.18%
时间复杂度O(N)
Java代码：
class Solution {
public int minSizeSubarray(int[] fnums, int target) {
int n=fnums.length;
int total=0;
for(int x:fnums) total+=x;
//拼接2倍长度数组
int[] nums=new int[2*n];
int index=0;
for(int i=0;i<2*n;i++){
if(i==n) index=0;
nums[i]=fnums[index++];
}
int rem=target%total,sum=0,ret=2*n;
for(int right=0,left=0;right<2*n;right++){
//进窗口
sum+=nums[right];
//出窗口
while(sum>rem) sum-=nums[left++];
//更新
if(sum==rem) ret=Math.min(ret,right-left+1);
}
return ret==2*n?-1:(ret+(target/total)*n);
}
}
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
2
0- 0
已为社区贡献9条内容
所有评论(0)