Skip to Content
CTRL K

Subarray Sums II

Problema

Nos piden hallar el número de subarreglos que suman xx dados el tamaño del arreglo y sus elementos.

Explicación

Podemos tener un mapa que lleve cuenta de las sumas de prefijos. En cada índice ii, podemos contar el número de prefijos con suma igual a prefixSum[i]−x\texttt{prefixSum}[i] - x. Esto asegurará que podemos quitar un prefijo de nuestro prefijo actual para construir un subarreglo con suma xx. Después de cada iteración, solo añadimos nuestra nueva suma de prefijos al mapa.

Implementación

Complejidad temporal: O(Nlog⁡N)\mathcal{O}(N\log N)

En C++, como std::unordered_map es vulnerable a colisiones, usamos std::map a costa de añadir un factor logarítmico extra a la complejidad.

#include <iostream>
#include <map>
#include <vector>
 
using namespace std;
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
 
	int N, X;
	cin >> N >> X;
	vector<int> T(N);
	for (int i = 0; i < N; i++) { cin >> T[i]; }
 
	long long prefix_sum = 0;
	long long ans = 0;
	map<long long, int> sums;
	sums[0] = 1;
	for (int x : T) {
		prefix_sum += x;
		/*
		 * If there is a subarray with a prefix sum of prefix_sum - X,
		 * we can exclude it from our current subarray to get the desired sum.
		 * Thus, we can add the number of those subarrays to our answer.
		 */
		ans += sums[prefix_sum - X];
		// Increment the amount of prefix sums with a sum of prefix_sum
		sums[prefix_sum]++;
	}
	cout << ans << endl;
}

Complejidad temporal: O(Nlog⁡N)\mathcal{O}(N\log N)

import java.io.*;
import java.util.*;
 
public class SubarraySumsII {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();
		int arraySize = io.nextInt();
		int target = io.nextInt();
		int[] array = new int[arraySize];
 
		for (int x = 0; x < arraySize; x++) { array[x] = io.nextInt(); }
 
		long prefixSum = 0;
		long answer = 0;
		Map<Long, Integer> sums = new HashMap<>();
		sums.put((long)0, 1);
 
		for (int x : array) {
			prefixSum += x;
			/*
			 * If there is a subarray with a prefix sum of prefix_sum - X,
			 * we can exclude it from our current subarray to get the desired
			 * sum. Thus, we can add the number of those subarrays to our
			 * answer.
			 */
			if (sums.containsKey(prefixSum - target)) {  // check if it is in our map
				answer += sums.get(prefixSum - target);
			}
 
			// Increment the amount of prefix sums with a sum of prefix_sum
			if (!sums.containsKey(prefixSum)) {  // not yet in map, so add it
				sums.put(prefixSum, 1);
			} else {  // already in map, add one to it
				sums.put(prefixSum, sums.get(prefixSum) + 1);
			}
		}
		io.println(answer);
		io.close();
	}
	// CodeSnip{Kattio};
}

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

import random
 
RANDOM = random.randrange(2**62)
 
 
def Wrapper(x):
	return x ^ RANDOM
 
 
def main():
	N, X = map(int, input().split())
	prefix, res = 0, 0
	mp = {Wrapper(0): 1}  # mp[0] = 1
 
	for x in input().split():
		prefix += int(x)
		res += mp.get(Wrapper(prefix - X), 0)  # if not in dict, return 0
		mp[Wrapper(prefix)] = mp.get(Wrapper(prefix), 0) + 1
	print(res)
Fundamentos