Table of Contents

ExplanationImplementation

Explanation

This problem can be solved with two pointers. We increment the left pointer when the sum is too large, and increment the right one when it's too small. When we have a valid subarray during an iteration, we add one to our answer.

Implementation

Time Complexity: O(N)\mathcal{O}(N)

C++

#include <iostream>
#include <vector>


int main() {
	int n, x;
	std::cin >> n >> x;
	std::vector<int> arr(n);
	for (int i = 0; i < n; i++) { std::cin >> arr[i]; }


	int i = 0, j = 0;

Java

import java.io.*;
import java.util.*;


public class SubarraySumsI {
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int n = io.nextInt();
		int x = io.nextInt();


		int[] arr = new int[n];

Python

n, x = map(int, input().split())
arr = list(map(int, input().split()))


i = 0
j = 0
sum, res = 0, 0
while j < n:
	sum += arr[j]
	while sum > x:
		sum -= arr[i]

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum