js滑动窗口
连续子区间和
http://www.nowcoder.com/questionTerminal/c7db49124acd415f801eb67de09c6d81
原理:若数组从下标0累加到i,会超过x,则从1累加到c的数字也必然超过x(数组是正整数)。
故使用滑动窗口,l、r分别为左右指针,length为数组长度(c)。
- r持续向右移动,直到和超过x,此时length-r就是从l开始的解的数量。
- 随后,将l+1,求下一个起点的解的数量。
while(line = readline()){
const sp = line.split(" ");
const c = parseInt(sp[0]), x = parseInt(sp[1]);
const nums = readline().split(" ").map((val)=>parseInt(val)), length = c;
let result = 0, l = 0, r = 0, sum = nums[0];
while(l < length){
// 移动r直到超过x
while(r < length && sum < x){
r++;
sum += nums[r];
}
if(r === length && sum < x){
// r移动到结尾,还是没有超过x,则后续的循环都没有意义,break
fin = true;
break;
}
result += length - r;
sum -= nums[l];
l++;
}
console.log(result);
}
查看3道真题和解析