Два вказівники в структурі даних: швидкість зустрічається з точністю

“Два вказівники в DSA: коли один вказівник занадто повільний, але разом вони — динамічний дует!”

Вступ :

Техніка з двома вказівниками — це стратегія, яку має знати кожен програміст, особливо під час підготовки до технічних співбесід. Як випливає з назви, вона полягає у використанні двох вказівників для навігації через структуру даних — зазвичай масив чи зв'язаний список — для оптимізації часу та простору. Це можна порівняти з розумною короткою стежкою, подібно до Бінарного пошуку, яка мінімізує кількість кроків, необхідних для досягнення рішення.

Замість того, щоб використовувати лише один вказівник, ця техніка використовує два, щоб працювати над різними частинами структури даних одночасно. Це значно скорочує зайві кроки та пришвидшує загальний процес.

Фото з Google

Як це працює :
Техніка двох вказівників має кілька варіантів, адаптованих до різних типів задач.

1. Протилежні кінці (Збіжні вказівники)

Як це працює: Два вказівники розташовуються на протилежних кінцях масиву або списку та рухаються один до одного, поки не зустрінуться або не буде задоволено певну умову.

• Звичайні варіанти використання:
• Пошук пари елементів з певною сумою в відсортованому масиві.
• Перевірка, чи є масив паліндромом.
• Розбиття масиву на дві частини.

Приклад: Знайти пару з заданою сумою в відсортованому масиві

bool findPair(int arr[], int n, int S) {  
 int i = 0, j = n - 1;  
 while (i < j) {  
 int sum = arr[i] + arr[j];  
 if (sum == S) return true;  
 if (sum < S) i++;  
 else j--;  
 }  
 return false;  
}

2. Різні швидкості (Швидкі та повільні вказівники)

Як це працює: Два вказівники починають з однакової позиції, але один рухається швидше (наприклад, удвічі швидше) за інший. Цей варіант корисний для пошуку патернів чи зв'язків у структурі даних. Цей підхід також відомий як алгоритм "Черепаха та Заєць".

• Звичайні варіанти використання:
• Пошук середини зв'язаного списку.
• Виявлення циклів у зв'язаному списку (Алгоритм Флойда для виявлення циклів).

Приклад: Виявити цикл у зв'язаному списку

bool hasCycle(ListNode* head) {  
 ListNode* slow = head;  
 ListNode* fast = head;  
 while (fast && fast->next) {  
 slow = slow->next;  
 fast = fast->next->next;  
 if (slow == fast) return true;  
 }  
 return false;  
}

3. Сковзаюче вікно (Фіксованого або змінного розміру)

Як це працює: Два вказівники використовуються для позначення початку та кінця "вікна" на підмасиві або підрядку. Вказівники рухаються вперед, динамічно коригуючи розмір вікна.

• Звичайні варіанти використання:
• Пошук максимальної суми підмасиву розміру k.
• Розв'язання задач з підрядками (наприклад, найдовший підрядок без повторюваних символів).

Приклад: Знайти максимальну суму підмасиву розміру k

int maxSumSubarray(int arr[], int n, int k) {  
 int i = 0, j = 0, sum = 0, maxSum = INT_MIN;  
 while (j < n) {  
 sum += arr[j];  
 if (j - i + 1 == k) { // Розмір вікна досягнуто  
 maxSum = max(maxSum, sum);  
 sum -= arr[i];  
 i++;  
 }  
 j++;  
 }  
 return maxSum;  
}

4. Два вказівники в вкладених циклах

Як це працює: Один вказівник ітерує через масив, а інший коригується в залежності від умов, часто використовується в відсортованих масивах.

• Звичайні варіанти використання:
• Підрахунок пар чи трійок, що задовольняють умову.
• Розв'язання задачі 3-сума або 4-сума.

Приклад: Підрахувати пари з заданою сумою

int countPairs(int arr[], int n, int S) {  
 int i = 0, j = n - 1, count = 0;  
 while (i < j) {  
 int sum = arr[i] + arr[j];  
 if (sum == S) {  
 count++;  
 i++;  
 j--;  
 } else if (sum < S) {  
 i++;  
 } else {  
 j--;  
 }  
 }  
 return count;  
}

5. Двостороннє перебирання

Як це працює: Один вказівник починає з початку, а інший — з кінця.
Обидва вказівники рухаються всередину, але в певних сценаріях вони можуть стрибати залежно від умов.

• Типові варіанти використання:
• Реверсування масиву на місці.
• Знаходження мінімального вікна, яке потребує сортування в не відсортованому масиві.

Приклад: Реверс масиву

void reverseArray(int arr[], int n) {  
 int i = 0, j = n - 1;  
 while (i < j) {  
 swap(arr[i], arr[j]);  
 i++;  
 j--;  
 }  
}

6. Два вказівники на кількох масивах

Як це працює: Два вказівники ітерують через різні масиви, часто відсортовані, щоб злитись або порівняти елементи.

• Типові варіанти використання:
• Злиття двох відсортованих масивів.
• Знаходження перетину або об'єднання двох відсортованих масивів.

Приклад: Злиття двох відсортованих масивів

vector mergeArrays(int arr1[], int n1, int arr2[], int n2) {  
 vector result;  
 int i = 0, j = 0;  
 while (i < n1 && j < n2) {  
 if (arr1[i] < arr2[j]) {  
 result.push_back(arr1[i]);  
 i++;  
 } else {  
 result.push_back(arr2[j]);  
 j++;  
 }  
 }  
 while (i < n1) result.push_back(arr1[i++]);  
 while (j < n2) result.push_back(arr2[j++]);  
 return result;  
}

7. Варіація з кількома вказівниками

Як це працює: Використовує більше ніж два вказівники для вирішення задач, які потребують порівнянь або групувань (наприклад, триплети чи чотирикратні елементи).

• Типові варіанти використання:
• Проблеми з 3-Sum та 4-Sum.
• Розбиття масивів на кілька підмасивів.

Приклад: Знайти всі триплети з сумою S

vector> threeSum(int arr[], int n, int S) {  
 vector> result;  
 sort(arr, arr + n);  
 for (int i = 0; i < n - 2; i++) {  
 int left = i + 1, right = n - 1;  
 while (left < right) {  
 int sum = arr[i] + arr[left] + arr[right];  
 if (sum == S) {  
 result.push_back({arr[i], arr[left], arr[right]});  
 left++;  
 right--;  
 } else if (sum < S) {  
 left++;  
 } else {  
 right--;  
 }  
 }  
 }  
 return result;  
}

K Вказівників

**Як це працює:** Розширює концепцію двох вказівників до `k` вказівників, що корисно для складних сценаріїв, таких як злиття `k` відсортованих масивів.

- **Типові варіанти використання:**
- Злиття кількох відсортованих списків.
- Знаходження найменшого діапазону, що охоплює елементи з `k` відсортованих масивів.

**Чому це заощаджує пам'ять?**  
Техніка двох вказівників часто усуває необхідність у додатковій пам'яті, що робить рішення більш ефективними за використанням простору.

Приклад: Реверс масиву

**Базовий підхід:** Використання допоміжного масиву для реверсування елементів.

int* reverseArray(int arr[], int n) {
int* reverse = new int[n];
for (int i = 0; i < n; i++) {
reverse[n - i - 1] = arr[i];
}
return reverse;
}
```

Складність по пам'яті: O(n)

Оптимізований підхід: Використовувати два вказівники на початку та в кінці масиву, міняючи елементи місцями по мірі їх руху до центру.

void reverseArray(int arr[], int n) {  
 int i = 0, j = n - 1;  
 while (i < j) {  
 swap(arr[i], arr[j]);  
 i++;  
 j--;  
 }  
}

Складність по пам'яті: O(1)

Де використовувати підхід з двома вказівниками?

- Масиви

• Пошук пар/триплетів із сумою (наприклад, два числа, що додаються до цільового значення).
• Сортування та злиття відсортованих масивів.
• Розбиття масивів (наприклад, переміщення від'ємних чисел в одну сторону).
• Проблеми з підмасивами (наприклад, ковзаюче вікно для конкретної суми).

- Рядки

• Перевірка на паліндром.
• Порівняння символів з обох кінців.
• Видалення дублікатів або стиснення рядків.

- Пов'язані списки

• Знайти середній елемент.
• Виявлення циклів (Алгоритм Флойда для виявлення циклів).
• Видалення n-го елемента з кінця.

- Інші

• Злиття інтервалів.
• Пошукові проблеми в відсортованих структурах.

Для візуалізації, зверніться до : https://30dayscoding.com/visualizer/two-pointers

Для відео-референсу, перегляньте : https://youtu.be/On03HWe2tZM?si=Xe68PMmmQzmcAmXR

Запитання Leetcode для практичного досвіду:

• https://leetcode.com/problems/valid-palindrome/description/
• https://leetcode.com/problems/merge-sorted-array/description/
• https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/
• https://leetcode.com/problems/3sum/description/
• https://leetcode.com/problems/container-with-most-water/description/
• https://leetcode.com/problems/trapping-rain-water/

Оволодійте технікою двох вказівників, і ви відкриєте для себе швидші та розумніші рішення на кожному кроці!

Буду радий почути ваші думки щодо техніки двох вказівників!

Слідуйте за мною на Linkedin та Twitter

Перекладено з: Two Pointers in DSA: Speed Meets Precision