Когда использовать: Оптимальный способ решения задач, связанных с массивами, строками и связанными списками за время O(N).
Массивы/Строки: Два указателя, каждый из которых начинается с начала и конца, пока они оба не встретятся.
Пример задачи: Two Sum II — входной массив отсортирован
class Solution {
public int[] twoSum(int[] numbers, int target) {
// use two pointer technique because the input is sorted.
int start = 0;
int end = numbers.length - 1;
int [] result = new int [2];
while (start < end){
int sum = numbers[start] + numbers[end];
if (sum == target){
result[0] = start + 1;
result[1] = end + 1;
break;
}
if (sum < target){
start++;
} else {
end--;
}
}
return result;
}
}
Связанный список: Один указатель движется медленно, а другой — в два раза быстрее.
Пример задачи: Цикл связного списка
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null){
return false;
}
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
return true;
}
}
return false;
}
}