首页 > 试题广场 >

连续子区间和

[编程题]连续子区间和
  • 热度指数:3955 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解

M给你一串含有c个正整数的数组, 想让你帮忙求出有多少个下标的连续区间, 它们的和大于等于x


输入描述:
第一行两个整数c x(0 < c <= 1000000, 0 <= x <= 100000000)

第二行有c个正整数(每个正整数小于等于100)。


输出描述:
输出一个整数,表示所求的个数。
示例1

输入

3 6
2 4 7

输出

4

说明

对于有3个整数构成的数组而言,总共有6个下标连续的区间,他们的和分别为:

2 = 2

4 = 4

7 = 7

2 + 4 = 6

4 + 7 = 11

2 + 4 + 7 = 13

其中有4个和大于等于6,所以答案等于4。
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int c = sc.nextInt();
        int x = sc.nextInt();
        int[] arr = new int[c];
        for(int i = 0; i < c; i++){
            arr[i] = sc.nextInt();
        }
        System.out.println(intervalNums(arr, x));
    }
    
    private static long intervalNums(int[] arr, int x){
        // 这里要用long记录,否则只能a45%
        long res = 0;
        int left = 0,  right = 0;
        long sum = arr[left];
        while(left < arr.length){
            // 符合条件则左指针移动,同时sum减去窗口左端值
            if(sum >= x){
                res += arr.length - right;
                sum -= arr[left];
                left++;
            }else{
                // 不符合则右指针向右移动扩大窗口,同时sum加上当前窗口右端值
                // 当窗口右端到达数组末尾则不能扩大。因为窗口都开到最大还不符合,所以可以直接退出
                right++;
                if(right == arr.length){
                    break;    
                }
                sum += arr[right];
            }
        }
        return res;
    }
}

发表于 2020-08-19 17:04:09 回复(0)
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int c,x,res=0;
    cin>>c>>x;
    int a[c];
    for(int i=0;i<c;i++)
        cin>>a[i];
    long long ans=0,sum=0,j=0;
    for(int i=0;i<c;i++)
    {
        sum+=a[i];
        if(sum>=x)
        {
            ans+=(c-i);
            while(j<=i)
            {
                sum-=a[j];
                j++;
                if(sum>=x)
                    ans+=(c-i);
                else
                    break;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

发表于 2019-07-09 22:56:13 回复(3)
滑动窗口的算法思想,不难证明复杂度为O(n)
#include <cinttypes>
#include <cstdio>
#define MAX_N 1000005
 
// input
int nums[MAX_N];
 
int_fast64_t sumN(int n) {
    if (n % 2) {
        return (n + 1) / 2 * (int_fast64_t)n;
    }
    return (int_fast64_t)n / 2 * (n + 1);
}
 
int_fast64_t solve(int n, int limit) {
    if (limit == 0) {
        return sumN(n);
    }
    int_fast64_t ans = 0;
    int curSum = 0;
    for (int i = 0, j = 0; i < n && j <= n; curSum -= nums[i++]) {
        while (curSum < limit && j < n) {
            curSum += nums[j++];
        }
        if (curSum >= limit) {
            ans += n - j + 1;
        }
    }
    return ans;
}
 
int main() {
    int n, limit;
    scanf("%d%d", &n, &limit);
    for (int i = 0; i < n; ++i) {
        scanf("%d", nums + i);
    }
    printf("%" PRIdFAST64 "\n", solve(n, limit));
    return 0;
}

编辑于 2019-04-09 20:28:44 回复(0)
#include <queue>
#include <iostream>
using namespace std;
int main()
{
    long long sum = 0;
    int c, x;
    cin >> c >> x;
    long long re = 0;
    queue<int> range;
    int v;
    for (int i = 0; i < c; ++i) {
        cin >> v;
        range.push(v);
        sum += v;
        while (sum >= x) {
             re += (c - i); 
             sum -= range.front();
             range.pop();
        }
    }
    cout << re << endl;
    return 0;
}
其实没有必要保存数组,毕竟每次删除的都是最左边的,直接上queue即可。
发表于 2019-09-19 23:12:43 回复(0)
""""
正整数数组,sum(a[i:j])>x,则sum(a[i:j+k])都大于x,j+k<=n,k为满足条件的个数
使用滑动窗口优化
"""

if __name__ == "__main__":
    n, x = map(int, input().strip().split())
    a = list(map(int, input().strip().split()))
    i, j, t_sum, ans = 0, 0, 0, 0
    while True:
        while j < n and t_sum < x:
            t_sum += a[j]
            j += 1
        if j == n and t_sum < x:
            break
        ans += n - j + 1
        t_sum -= a[i]
        i += 1
    print(ans)

发表于 2019-07-17 11:16:33 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main(){
    int c,x;
    cin>>c>>x;
    int a[c];
    for(int i=0;i<c;i++)
        cin>>a[i];
    long sum=0,t=0;
    for(int i=0,j=0;i<c;i++){
        for(;j<c && t<x;j++)
            t += a[j];
        if(j==c && t<x)
            break;
        sum += c-j+1;
        t -= a[i];
    }
    cout<<sum<<endl;
    return 0;
}

发表于 2019-11-11 02:11:15 回复(1)
这个题真是,时间复杂度要求还蛮高的,试了普通前缀和的做***超时,还是得剪枝内层循环,让滑窗的左右端点通过最少的移动来求出答案。
(1) 先将左端点j固定在0位置,移动右端点i,直到区间和>=x,在此时固定左端点的情况下,右端点已经没有必要再往右移了,右边的c-i个右端点肯定满足区间和不小于x,可以产生c-i个符合条件的区间。
(2) 固定右端点i,右移左端点j看是否还能满足区间和不小于x,满足的话,计数就不断地累加c-i
(3) 回到(1)继续右移右端点,重复(1)(2)步骤
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().trim().split(" ");
        int c = Integer.parseInt(params[0]), x = Integer.parseInt(params[1]);
        params = br.readLine().trim().split(" ");
        int[] arr = new int[c];
        for(int i = 0; i < c; i++) arr[i] = Integer.parseInt(params[i]);
        long sum = 0, count = 0;
        int j = 0;
        for(int i = 0; i < c; i++) {
            sum += arr[i];
            while(sum >= x && j <= i){
                count += c - i;
                sum -= arr[j];
                j ++;
            }
        }
        System.out.println(count);
    }
}

编辑于 2021-04-18 21:48:13 回复(1)
#include <stdio.h>
#include <stdlib.h>

int n, a[1000005];
long long x;

int main() {
  scanf("%d%lld", &n, &x);
  long long sum = 0, count = 0;
  int j = 1;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    sum += a[i];
    while (sum >= x) {
      count += n - i + 1;
      sum -= a[j];
      j++;
    }
  }
  printf("%lld\n", count);
  return 0;
}

发表于 2023-11-21 17:42:47 回复(0)
#include <bits/stdc++.h>
using namespace std;
int main(){
    int c,x;
    cin>>c>>x;
    int a[c];
    long num=0;long sum=0;
    for(int i=0;i<c;i++)
        cin>>a[i];
    int l=0,r=0;
    while(r<c){
        while(sum<x&&r<c){
            sum+=a[r];
            r+=1;
        }
        while(sum>=x){
            sum-=a[l];
            l++;
            num+=(c-r+1);
        }
    }
    cout<<num<<endl;
    return 0;
}
发表于 2023-02-14 14:46:48 回复(0)
def func():
    c,x = map(int, input().strip().split())
    lis_array = [int(x)for x in input().split()]
    sum_num = 0
    count_num = 0
    j = 0
    for i in range(len(lis_array)):
        if sum_num < x:
            sum_num += lis_array[i]
        while j < c and sum_num >= x:
            count_num += c - i
            sum_num -= lis_array[j]
            j += 1
    print(count_num)
if __name__=="__main__":
    func()
发表于 2022-05-10 21:25:37 回复(1)
#include <cinttypes>
#include <cstdio>
#define MAX_N 1000005
 
// input
int nums[MAX_N];
 
int_fast64_t sumN(int n) {
    if (n % 2) {
        return (n + 1) / 2 * (int_fast64_t)n;
    }
    return (int_fast64_t)n / 2 * (n + 1);
}
 
int_fast64_t solve(int n, int limit) {
    if (limit == 0) {
        return sumN(n);
    }
    int_fast64_t ans = 0;
    int curSum = 0;
    for (int i = 0, j = 0; i < n && j <= n; curSum -= nums[i++]) {
        while (curSum < limit && j < n) {
            curSum += nums[j++];
        }
        if (curSum >= limit) {
            ans += n - j + 1;
        }
    }
    return ans;
}
 
int main() {
    int n, limit;
    scanf("%d%d", &n, &limit);
    for (int i = 0; i < n; ++i) {
        scanf("%d", nums + i);
    }
    printf("%" PRIdFAST64 "\n", solve(n, limit));
    return 0;
}
发表于 2022-05-09 14:31:16 回复(0)
#include<stdio.h>
int main (void)
{
    int c,x;
    int arr[1000000]={0};
    scanf("%d %d",&c,&x);
    for(int i=0;i<c;i++)
        scanf("%d",&arr[i]);
    long long count=0;
    int left=0;
    int right=0;
    int sum=arr[0];
    while(right<c)
    {
        if(sum>=x)
        {
            count+=(c-right);
            sum-=arr[left++];
        }else{
            sum+=arr[++right];
        }
    }
    printf("%ld\n",count);
    return 0;
}

发表于 2021-12-16 21:47:23 回复(0)
调了半天一直是45% 然后对比了别人的代码才醒悟没有用long long啊啊啊啊
发表于 2020-06-12 23:35:54 回复(1)
#include <iostream>
using namespace std;

int nums[1000001];

int main(int argc, char* argv[]){
    int c, x, a;
    cin >> c >> x;
    for(int i = 0; i < c; i++) cin >> nums[i];
    int low = 0, high = 0, sum = 0;
    long long cnt = 0;
    while(high < c){
        while(high < c && sum < x) sum += nums[high++];
        while(sum >= x) {
            cnt += (c - high + 1);
            sum -= nums[low++];
        }
    }
    cout << cnt << endl;
    return 0;
}

发表于 2020-05-12 17:15:50 回复(0)
#include<iostream>
(720)#include<vector>

using namespace std;

int main(void){
    int c, x;
    cin>>c>>x;
    int num;
    vector<int> v;
    long long ans = 0;
    int sum = 0;
    for (int i = 0; i < c; i++){
        cin>>num;
        v.push_back(num);
    }
    int i = 0;
    for (int j = 0; j < c; j++){
        sum += v[j];
       
        while (sum >= x){
            ans += c - j;
            sum -= v[i];
            i++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

发表于 2020-05-10 18:15:57 回复(0)
import sys
c,x = sys.stdin.readline().split(' ')
list_c = list(map(int,sys.stdin.readline().split(' ')))
x = int(x)
count = 0
if list_c is None:
    print(0)
else:
    list_c_sum = 0
    j = 0
    for i in range(len(list_c)):
        if i >= 1:
            list_c_sum = list_c_sum - list_c[i-1] 
            #精髓之处,迭代sum时将第一个删掉,而不是从list_c[i]重新开始加,可避免报时间超出的错
        while list_c_sum < x and j <= len(list_c)-1:
            list_c_sum = list_c_sum + list_c[j]
            j = j+1
        if j == 1:
            if list_c_sum < x:
                print(0)
        if list_c_sum >= x:
            count = count + (len(list_c)-j+1)
    print(count)
发表于 2020-03-17 00:42:14 回复(0)
线下IDE自测各种样例没啥问题,不知道为啥线上不行,等个菊苣找错吧
let num = readline().split(' ');
let length = parseInt(num[0]);
let x = parseInt(num[1]);
let arr = readline().split(' ');
let sum = 0;
let qur = 0;
for (let i = 0; i < length; i++) {
    for (let j = i; j < length; j++) {
        sum += arr[j];
        if (sum >= x) {
            qur += length - j;
            break;
        }
    }
    sum = 0;
}
print(qur);


发表于 2020-03-13 04:06:18 回复(1)
不需要每次都去计算,重要的关键在于要保存计算好的数列和



import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int count = 0;
        int threold = 0;
        int n = 0;
        Scanner in = new Scanner(System.in);

        while (in.hasNextLine()){
            n++;
            List<Integer> list = new ArrayList<>();

            if (n % 2 == 1){
                String s=in.nextLine().trim();
                String[] str=s.split(" ");
                count = Integer.parseInt(str[0]);
                threold = Integer.parseInt(str[1]);
            }else {
                String s=in.nextLine().trim();
                String[] str=s.split(" ");
                for(int i=0;i<str.length;i++) {
                    list.add(Integer.parseInt(str[i]));
                }
            }
            if (n % 2 == 0){
                System.out.println(getCount(count, threold,list));
                return;
            }
        }
    }

    private static long getCount(int count, int threold,List<Integer>list){
        long res = 0;

        long tmp = 0;

        for (int i = 0, before = 0; before <= count && i < count; tmp -= list.get(i++)){
            while (tmp<threold && before < count){
                tmp += list.get(before++);
            }
            if (tmp>=threold){
                res += (count - before +1);
            }
            
        }
        return res;
    }
}


发表于 2019-09-19 23:19:20 回复(0)