Two pointers is a technique that uses two indices to traverse a data structure, such as an array or a linked list. The two pointers can move in the same direction or in opposite directions, depending on the problem being solved.
Any problem that involves two elements in a data structure can potentially be solved using two pointers. The brute-force approach can be considered as using two pointers. Even the binary search can be considered as three pointers.
We only focus on two pointers that move in a more strategic way to improve efficiency:
- Finding, counting or finding the best intervals or contiguous subarrays that meet certain criteria (e.g., sum, product, etc.). In this case, the two pointers is usually called sliding window. Two pointers indicate the left and right end of the interval, and sweeps for the same direction (right). The intervals can be:
- Fixed-length. Example: 1456. 定长子数组中元素的最大和, 643. 子数组最大平均数 I, 1343. 大小为 K 且平均值大于等于阈值的子数组数目, 2090. 半径为k的子数组平均值,
- Variable-length. Example: 209. 长度最小的子数组, 3. 无重复字符的最长子串
- Locate certain pairs in a sorted array that meet certain criteria (e.g., sum, difference, etc.). To solve such problems, the array or linked list need be sorted first. The two pointers can go:
- Same direction. Example: 611. 有效三角形的个数
- Towards each other. Example: 15. 三数之和, 16. 最接近的三数之和
- Against each other from a certain point.
- Fast & slow pointers can be used to detect cycles in a linked list or array. The fast pointer moves two steps at a time, while the slow pointer moves one step at a time. If there is a cycle, the two pointers will eventually meet. Some information about the linear list (e.g., circle length, circle entry point, mid point) can also be derived. Example: 142. 环形链表 II, 287. 寻找重复数
The technique can also be extended to solve problems that require more than two pointers, such as finding triplets or quadruplets in an array that meet certain criteria.
The problems can be extended on more than one array.