Dos punteros

Recursos

Video de YouTube (zmadiUuUeAA)

Dos punteros

El método de dos punteros recorre un arreglo con dos punteros para llevar la cuenta de índices que satisfacen alguna condición. Hay dos variantes habituales:

1. Dos punteros que empiezan en extremos distintos del arreglo y se mueven el uno hacia el otro.
2. Dos punteros que se mueven en la misma dirección a distinta velocidad. Esta variante se conoce como el algoritmo de ventana deslizante (Sliding Window).

Sum of Two Values

Solución - Sum of Two Values

El método de “extremos opuestos” permite encontrar el par objetivo en tiempo lineal si el arreglo está ordenado. En lugar de revisar todos los pares posibles (lo que tomaría tiempo $\mathcal{O}(N^2)$), usamos la propiedad de estar ordenado para reducir el espacio de búsqueda en una sola pasada.

Queremos encontrar dos índices $i$ y $j$ tales que $a_i + a_j = x$.

Podemos empezar ordenando el arreglo. Luego inicializamos un puntero izquierdo al comienzo del arreglo ($l=0$) y un puntero derecho al final ($r=N-1$).

Mientras $l < r$:

1. Si $a[l] + a[r] == x$, encontramos la suma objetivo.
2. Si $a[l] + a[r] < x$, la suma es demasiado chica. Para aumentarla, incrementamos $l$.
3. Si $a[l] + a[r] > x$, la suma es demasiado grande. Para disminuirla, decrementamos $r$.

Como el arreglo está ordenado, mover el puntero izquierdo hacia la derecha nunca disminuye la suma, y mover el puntero derecho hacia la izquierda nunca aumenta la suma.

Implementación

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

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
 
using namespace std;
 
int main() {
	int n, x;
	cin >> n >> x;
	vector<pair<int, int>> nums(n);
	for (int i = 0; i < n; i++) {
		cin >> nums[i].first;
		nums[i].second = i;
	}
	sort(nums.begin(), nums.end());
	int l = 0, r = n - 1;
	while (l < r) {
		int sum = nums[l].first + nums[r].first;
		if (sum == x) {
			cout << nums[l].second + 1 << " " << nums[r].second + 1 << endl;
			return 0;
		} else if (sum < x) {
			l++;
		} else if (sum > x) {
			r--;
		}
	}
	cout << "IMPOSSIBLE" << endl;
}

import java.io.*;
import java.util.*;
 
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int x = Integer.parseInt(st.nextToken());
 
		List<int[]> nums = new ArrayList<>();
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			nums.add(new int[] {Integer.parseInt(st.nextToken()), i});
		}
		nums.sort(Comparator.comparingInt(a -> a[0]));
		int l = 0, r = n - 1;
		while (l < r) {
			int sum = nums.get(l)[0] + nums.get(r)[0];
			if (sum == x) {
				System.out.println((nums.get(l)[1] + 1) + " " + (nums.get(r)[1] + 1));
				return;
			} else if (sum < x) {
				l++;
			} else {
				r--;
			}
		}
 
		System.out.println("IMPOSSIBLE");
	}
}

n, x = map(int, input().split())
 
nums = [(int(val), i) for i, val in enumerate(input().split())]
nums.sort()
 
l = 0
r = n - 1
while l < r:
	sum = nums[l][0] + nums[r][0]
	if sum == x:
		print(nums[l][1] + 1, nums[r][1] + 1)
		exit()
	elif sum < x:
		l += 1
	else:
		r -= 1
 
print("IMPOSSIBLE")

Ventana deslizante

El método de ventana deslizante es una variante de la técnica de dos punteros en la que ambos se mueven en la misma dirección para mantener un rango o “ventana” específica de elementos. Mientras que en dos punteros estándar a menudo se mueven el uno hacia el otro, la ventana deslizante se usa para encontrar un subarreglo contiguo que satisfaga una condición.

Solución - Books

Queremos encontrar el segmento contiguo más largo de libros que se pueden leer en $t$ minutos.

Para eso, podemos definir $\texttt{left}$ y $\texttt{right}$ como el inicio y el fin del segmento. Ambos empiezan al comienzo del arreglo. Estos números se pueden pensar como punteros, de ahí el nombre “dos punteros”.

Para cada valor de $\texttt{left}$ en orden creciente, aumentamos $\texttt{right}$ hasta maximizar el tiempo total del segmento sin superar $t$.

$\texttt{ans}$ guarda el valor máximo de $\texttt{right} - \texttt{left}+1$ (tamaño del segmento) que hayamos visto hasta el momento.

Después de incrementar $\texttt{left}$ en uno, el tiempo usado disminuye, así que el puntero derecho nunca tiene que moverse hacia la izquierda. Por lo tanto:

Como ambos punteros se mueven a lo sumo $N$ veces, la complejidad temporal total es $\mathcal{O}(N)$.

Como ejemplo, consideremos el primer caso de las entradas de ejemplo:

Podemos mover el puntero derecho al índice $1$:

La suma de los valores en este rango es $4$, y hay $2$ valores. Así, la longitud máxima actual del segmento es $\texttt{ans}=2$. Al incrementar el puntero izquierdo en $1$, podemos restar $3$ de la suma de valores y obtener $1$. El arreglo queda así:

Ahora podemos mover el puntero derecho hasta el final. Esto hace que la suma de valores sea $1+2+1=4$ y que la longitud del segmento sea $3$. Así, $\texttt{ans}$ pasa a ser $3$.

Como el puntero derecho llegó al final del arreglo, terminamos en este punto. Nos queda $\texttt{ans}=3$.

Acá hay una animación del ejemplo anterior:

Implementación

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

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int N, T;
	cin >> N >> T;
	vector<int> A(N);
	for (int &a : A) cin >> a;
 
	int r = -1, sum = 0, ans = 0;
	// sum guarda la suma de A[l ... r inclusive]
	for (int l = 0; l < N; sum -= A[l++]) {
		while (r + 1 < N && sum + A[r + 1] <= T) sum += A[++r];
		ans = max(ans, r - l + 1);
	}
	cout << ans << "\n";
}

import java.io.*;
import java.util.*;
 
public class Books {
	public static void main(String[] args) {
		Kattio io = new Kattio();
 
		int N = io.nextInt();
		int T = io.nextInt();
		int[] A = new int[N];
		for (int i = 0; i < N; i++) { A[i] = io.nextInt(); }
 
		int r = -1, sum = 0, ans = 0;
		// sum guarda la suma de A[l ... r inclusive]
		for (int l = 0; l < N; sum -= A[l++]) {
			while (r + 1 < N && sum + A[r + 1] <= T) sum += A[++r];
			ans = Math.max(ans, r - l + 1);
		}
 
		io.println(ans);
		io.close();
	}
 
	// CodeSnip{Kattio}
}

N, T = map(int, input().split())
A = list(map(int, input().split()))
 
r = -1
window_sum = 0  # suma de A[l ... r inclusive]
ans = 0
 
for l in range(N):
	while r + 1 < N and window_sum + A[r + 1] <= T:
		r += 1
		window_sum += A[r]
	ans = max(ans, r - l + 1)
	window_sum -= A[l]
 
print(ans)

Problemas

Quiz