Skip to Content
CTRL K

Subarray Sums I

Solución

Explicación

Este problema se puede resolver con dos punteros. Incrementamos el puntero izquierdo cuando la suma es demasiado grande, y el derecho cuando es demasiado pequeña. Cuando tenemos un subarreglo válido durante una iteración, sumamos uno a nuestra respuesta.

Implementación

Complejidad temporal: O(N)\mathcal{O}(N)

#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;
	int res = 0;
	long long sum = 0;
	while (j < n) {
		sum += arr[j];
		while (sum > x) {
			sum -= arr[i];
			i++;
		}
		res += (sum == x);
		j++;
	}
 
	std::cout << res << std::endl;
}
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];
		for (int i = 0; i < n; i++) { arr[i] = io.nextInt(); }
 
		int i = 0;
		int j = 0;
		int res = 0;
		long sum = 0;
		while (j < n) {
			sum += arr[j];
			while (sum > x) {
				sum -= arr[i];
				i++;
			}
			res += (sum == x ? 1 : 0);
			j++;
		}
 
		io.println(res);
		io.close();
	}
 
	// CodeSnip{Kattio}
}
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]
		i = i + 1
 
	res += sum == x
	j = j + 1
 
print(res)
Fundamentos