友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

微信

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

Two Pointer 双指针

双指针是这样的模式：两个指针朝着左右方向移动（双指针分为同向双指针和异向双指针），直到他们有一个或是两个都满足某种条件。双指针通常用在排好序的数组或是链表中寻找对子。比如，你需要去比较数组中每个元素和其他元素的关系时，你就需要用到双指针了。

我们需要双指针的原因是：如果你只用一个指针的话，你得来回跑才能在数组中找到你需要的答案。这一个指针来来回回的过程就很耗时和浪费空间了 — 这是考虑算法的复杂度分析的时候的重要概念。虽然brute force一个指针的解法可能会奏效，但时间复杂度一般会是O(n²)。在很多情况下，双指针能帮助我们找到空间或是时间复杂度更低的解。

识别使用双指针的招数：

  • 一般来说，数组或是链表是排好序的，你得在里头找一些组合满足某种限制条件

  • 这种组合可能是一对数，三个数，或是一个子数组

经典题目

  1. 5. 最长回文子串

  2. 11. 盛最多水的容器

  3. 15. 三数之和

  4. 16. 3Sum Closest

  5. 18. 4Sum

  6. 19. 删除链表的倒数第 N 个结点

  7. 26. Remove Duplicates from Sorted Array

  8. 27. 移除元素

  9. 28. 找出字符串中第一个匹配项的下标

  10. 31. 下一个排列

  11. 42. 接雨水

  12. 61. Rotate List

  13. 75. Sort Colors

  14. 80. Remove Duplicates from Sorted Array II

  15. 82. Remove Duplicates from Sorted List II

  16. 86. Partition List

  17. 88. 合并两个有序数组

  18. 125. Valid Palindrome

  19. 141. 环形链表

  20. 142. 环形链表 II

  21. 143. 重排链表

  22. 148. 排序链表

  23. 151. Reverse Words in a String

  24. 160. Intersection of Two Linked Lists

  25. [0161-one-edit-distance]

  26. [0165-compare-version-numbers]

  27. 167. Two Sum II - Input array is sorted

  28. [0170-two-sum-iii-data-structure-design]

  29. [0186-reverse-words-in-a-string-ii]

  30. 189. 轮转数组

  31. 202. 快乐数

  32. 234. Palindrome Linked List

  33. [0244-shortest-word-distance-ii]

  34. [0246-strobogrammatic-number]

  35. [0251-flatten-2d-vector]

  36. [0253-meeting-rooms-ii]

  37. [0259-3sum-smaller]

  38. [0272-closest-binary-search-tree-value-ii]

  39. [0277-find-the-celebrity]

  40. 283. Move Zeroes

  41. 287. Find the Duplicate Number

  42. 295. 数据流的中位数

  43. [0321-create-maximum-number]

  44. 344. Reverse String

  45. [0345-reverse-vowels-of-a-string]

  46. [0349-intersection-of-two-arrays]

  47. 350. Intersection of Two Arrays II

  48. [0360-sort-transformed-array]

  49. 392. Is Subsequence

  50. [0408-valid-word-abbreviation]

  51. [0443-string-compression]

  52. [0455-assign-cookies]

  53. [0457-circular-array-loop]

  54. [0475-heaters]

  55. [0481-magical-string]

  56. [0522-longest-uncommon-subsequence-ii]

  57. [0524-longest-word-in-dictionary-through-deleting]

  58. [0532-k-diff-pairs-in-an-array]

  59. [0541-reverse-string-ii]

  60. [0556-next-greater-element-iii]

  61. [0557-reverse-words-in-a-string-iii]

  62. 567. Permutation in String

  63. 581. Shortest Unsorted Continuous Subarray

  64. [0611-valid-triangle-number]

  65. [0633-sum-of-square-numbers]

  66. 647. Palindromic Substrings

  67. [0653-two-sum-iv-input-is-a-bst]

  68. [0658-find-k-closest-elements]

  69. [0680-valid-palindrome-ii]

  70. [0696-count-binary-substrings]

  71. [0719-find-k-th-smallest-pair-distance]

  72. [0723-candy-crush]

  73. [0763-partition-labels]

  74. [0777-swap-adjacent-in-lr-string]

  75. [0786-k-th-smallest-prime-fraction]

  76. [0795-number-of-subarrays-with-bounded-maximum]

  77. [0809-expressive-words]

  78. [0821-shortest-distance-to-a-character]

  79. [0825-friends-of-appropriate-ages]

  80. [0826-most-profit-assigning-work]

  81. [0832-flipping-an-image]

  82. [0838-push-dominoes]

  83. [0844-backspace-string-compare]

  84. [0845-longest-mountain-in-array]

  85. 870. Advantage Shuffle

  86. 876. Middle of the Linked List

  87. 881. Boats to Save People

  88. [0905-sort-array-by-parity]

  89. [0917-reverse-only-letters]

  90. [0922-sort-array-by-parity-ii]

  91. [0923-3sum-with-multiplicity]

  92. [0925-long-pressed-name]

  93. [0942-di-string-match]

  94. [0948-bag-of-tokens]

  95. [0962-maximum-width-ramp]

  96. [0969-pancake-sorting]

  97. [0977-squares-of-a-sorted-array]

  98. [0986-interval-list-intersections]

  99. [1023-camelcase-matching]

  100. [1040-moving-stones-until-consecutive-ii]

  101. [1048-longest-string-chain]

  102. [1055-shortest-way-to-form-string]

  103. [1089-duplicate-zeros]

  104. [1099-two-sum-less-than-k]

  105. [1147-longest-chunked-palindrome-decomposition]

  106. [1163-last-substring-in-lexicographical-order]

  107. [1214-two-sum-bsts]

  108. [1229-meeting-scheduler]

  109. [1237-find-positive-integer-solution-for-a-given-equation]

  110. [1265-print-immutable-linked-list-in-reverse]

  111. [1332-remove-palindromic-subsequences]

  112. [1346-check-if-n-and-its-double-exist]

  113. [1385-find-the-distance-value-between-two-arrays]

  114. [1455-check-if-a-word-occurs-as-a-prefix-of-any-word-in-a-sentence]

  115. [1471-the-k-strongest-values-in-an-array]

  116. [1498-number-of-subsequences-that-satisfy-the-given-sum-condition]

  117. [1508-range-sum-of-sorted-subarray-sums]

  118. [1537-get-the-maximum-score]

  119. [1570-dot-product-of-two-sparse-vectors]

  120. [1574-shortest-subarray-to-be-removed-to-make-array-sorted]

  121. [1577-number-of-ways-where-square-of-number-is-equal-to-product-of-two-numbers]

  122. [1616-split-two-strings-to-make-palindrome]

  123. [1634-add-two-polynomials-represented-as-linked-lists]

  124. 1650. Lowest Common Ancestor of a Binary Tree III

  125. [1679-max-number-of-k-sum-pairs]

  126. [1697-checking-existence-of-edge-length-limited-paths]

  127. [1712-ways-to-split-array-into-three-subarrays]

  128. [1721-swapping-nodes-in-a-linked-list]

  129. [1750-minimum-length-of-string-after-deleting-similar-ends]

  130. [1754-largest-merge-of-two-strings]

  131. [1755-closest-subsequence-sum]

  132. [1764-form-array-by-concatenating-subarrays-of-another-array]

  133. [1768-merge-strings-alternately]

  134. [1782-count-pairs-of-nodes]

  135. [1793-maximum-score-of-a-good-subarray]

  136. [1813-sentence-similarity-iii]

  137. [1826-faulty-sensor]

  138. [1842-next-palindrome-using-same-digits]

  139. [1850-minimum-adjacent-swaps-to-reach-the-kth-smallest-number]

  140. [1855-maximum-distance-between-a-pair-of-values]

  141. [1861-rotating-the-box]

  142. [1868-product-of-two-run-length-encoded-arrays]

  143. [1877-minimize-maximum-pair-sum-in-array]

  144. [1885-count-pairs-in-two-arrays]

  145. [1898-maximum-number-of-removable-characters]

  146. [1961-check-if-string-is-a-prefix-of-array]

  147. [1963-minimum-number-of-swaps-to-make-the-string-balanced]

  148. [2000-reverse-prefix-of-word]

  149. [2035-partition-array-into-two-arrays-to-minimize-sum-difference]

  150. [2046-sort-linked-list-already-sorted-using-absolute-values]

  151. [2095-delete-the-middle-node-of-a-linked-list]

  152. [2105-watering-plants-ii]

  153. [2108-find-first-palindromic-string-in-the-array]

  154. [2109-adding-spaces-to-a-string]

  155. [2122-recover-the-original-array]

  156. [2130-maximum-twin-sum-of-a-linked-list]

  157. [2149-rearrange-array-elements-by-sign]

  158. [2161-partition-array-according-to-given-pivot]

  159. [2193-minimum-number-of-moves-to-make-palindrome]

  160. [2200-find-all-k-distant-indices-in-an-array]

  161. [2234-maximum-total-beauty-of-the-gardens]

  162. [2300-successful-pairs-of-spells-and-potions]

  163. [2330-valid-palindrome-iv]

  164. [2332-the-latest-time-to-catch-a-bus]

  165. [2337-move-pieces-to-obtain-a-string]

  166. [2367-number-of-arithmetic-triplets]

  167. [2396-strictly-palindromic-number]

  168. [2406-divide-intervals-into-minimum-number-of-groups]

  169. [2410-maximum-matching-of-players-with-trainers]

  170. [2422-merge-operations-to-turn-array-into-a-palindrome]

  171. [2441-largest-positive-integer-that-exists-with-its-negative]

  172. [2460-apply-operations-to-an-array]

  173. [2462-total-cost-to-hire-k-workers]

  174. [2465-number-of-distinct-averages]

  175. [2472-maximum-number-of-non-overlapping-palindrome-substrings]

  176. [2486-append-characters-to-string-to-make-subsequence]

  177. [2491-divide-players-into-teams-of-equal-skill]

  178. [2503-maximum-number-of-points-from-grid-queries]

  179. [2511-maximum-enemy-forts-that-can-be-captured]

  180. [2540-minimum-common-value]

  181. [2562-find-the-array-concatenation-value]

  182. [2563-count-the-number-of-fair-pairs]

  183. [2565-subsequence-with-the-minimum-score]

  184. [2570-merge-two-2d-arrays-by-summing-values]

  185. [2576-find-the-maximum-number-of-marked-indices]

  186. [2592-maximize-greatness-of-an-array]

  187. [2604-minimum-time-to-eat-all-grains]

  188. [2674-split-a-circular-linked-list]

  189. [2697-lexicographically-smallest-palindrome]

  190. [2824-count-pairs-whose-sum-is-less-than-target]

  191. [2825-make-string-a-subsequence-using-cyclic-increments]

  192. [2838-maximum-coins-heroes-can-collect]

  193. [2856-minimum-array-length-after-pair-removals]

  194. [2868-the-wording-game]

  195. [2903-find-indices-with-index-and-value-difference-i]

  196. [2905-find-indices-with-index-and-value-difference-ii]

  197. [2911-minimum-changes-to-make-k-semi-palindromes]

  198. [2938-separate-black-and-white-balls]

  199. [2970-count-the-number-of-incremovable-subarrays-i]

  200. [2972-count-the-number-of-incremovable-subarrays-ii]

  201. [3006-find-beautiful-indices-in-the-given-array-i]

  202. [3008-find-beautiful-indices-in-the-given-array-ii]

  203. [3132-find-the-integer-added-to-array-ii]

  204. [3186-maximum-total-damage-with-spell-casting]

  205. [3194-minimum-average-of-smallest-and-largest-elements]

  206. [3239-minimum-number-of-flips-to-make-binary-grid-palindromic-i]

  207. [3240-minimum-number-of-flips-to-make-binary-grid-palindromic-ii]

  208. [3284-sum-of-consecutive-subarrays]

  209. [3302-find-the-lexicographically-smallest-valid-sequence]

  210. [3316-find-maximum-removals-from-source-string]

  211. [3400-maximum-number-of-matching-indices-after-right-shifts]

  212. [3403-find-the-lexicographically-largest-string-from-the-box-i]

  213. [3406-find-the-lexicographically-largest-string-from-the-box-ii]

  214. [3455-shortest-matching-substring]

  215. [3460-longest-common-prefix-after-at-most-one-removal]

  216. [3503-longest-palindrome-after-substring-concatenation-i]

  217. [3504-longest-palindrome-after-substring-concatenation-ii]

参考资料

  1. Two Pointer问题总结

  2. 876. 链表的中间结点 - 注意链表长度为偶数时，返回第 2 个结点的细节

  3. 876. 链表的中间结点 - 双指针，清晰图解

  4. 141. 环形链表 - 一文搞定常见的链表问题

← Previous: In-place Reversal of a LinkedList 原地链表翻转 | ↑ Up: LeetCode 解题笔记 | Next: Fast & Slow Pointers 快慢指针 →