Back to Leetcode Go

2.03 ✅ Two Pointers

website/content/ChapterTwo/Two_Pointers.md

1.7.111.3 KB
Original Source

Two Pointers

  • 双指针滑动窗口的经典写法。右指针不断往右移,移动到不能往右移动为止(具体条件根据题目而定)。当右指针到最右边以后,开始挪动左指针,释放窗口左边界。第 3 题,第 76 题,第 209 题,第 424 题,第 438 题,第 567 题,第 713 题,第 763 题,第 845 题,第 881 题,第 904 题,第 978 题,第 992 题,第 1004 题,第 1040 题,第 1052 题。
c
	left, right := 0, -1

	for left < len(s) {
		if right+1 < len(s) && freq[s[right+1]-'a'] == 0 {
			freq[s[right+1]-'a']++
			right++
		} else {
			freq[s[left]-'a']--
			left++
		}
		result = max(result, right-left+1)
	}
  • 快慢指针可以查找重复数字,时间复杂度 O(n),第 287 题。
  • 替换字母以后,相同字母能出现连续最长的长度。第 424 题。
  • SUM 问题集。第 1 题,第 15 题,第 16 题,第 18 题,第 167 题,第 923 题,第 1074 题。
No.TitleSolutionDifficultyTimeComplexitySpaceComplexityFavoriteAcceptance
0011Container With Most Water[Go]({{< relref "/ChapterFour/0001~0099/0011.Container-With-Most-Water.md" >}})MediumO(n)O(1)54.0%
00153Sum[Go]({{< relref "/ChapterFour/0001~0099/0015.3Sum.md" >}})MediumO(n^2)O(n)❤️32.6%
00163Sum Closest[Go]({{< relref "/ChapterFour/0001~0099/0016.3Sum-Closest.md" >}})MediumO(n^2)O(1)❤️45.8%
00184Sum[Go]({{< relref "/ChapterFour/0001~0099/0018.4Sum.md" >}})MediumO(n^3)O(n^2)❤️35.9%
0019Remove Nth Node From End of List[Go]({{< relref "/ChapterFour/0001~0099/0019.Remove-Nth-Node-From-End-of-List.md" >}})MediumO(n)O(1)41.0%
0026Remove Duplicates from Sorted Array[Go]({{< relref "/ChapterFour/0001~0099/0026.Remove-Duplicates-from-Sorted-Array.md" >}})EasyO(n)O(1)51.5%
0027Remove Element[Go]({{< relref "/ChapterFour/0001~0099/0027.Remove-Element.md" >}})EasyO(n)O(1)53.0%
0028Find the Index of the First Occurrence in a String[Go]({{< relref "/ChapterFour/0001~0099/0028.Find-the-Index-of-the-First-Occurrence-in-a-String.md" >}})EasyO(n)O(1)39.0%
0031Next Permutation[Go]({{< relref "/ChapterFour/0001~0099/0031.Next-Permutation.md" >}})Medium37.5%
0042Trapping Rain Water[Go]({{< relref "/ChapterFour/0001~0099/0042.Trapping-Rain-Water.md" >}})HardO(n)O(1)❤️59.2%
0061Rotate List[Go]({{< relref "/ChapterFour/0001~0099/0061.Rotate-List.md" >}})MediumO(n)O(1)36.1%
0075Sort Colors[Go]({{< relref "/ChapterFour/0001~0099/0075.Sort-Colors.md" >}})MediumO(n)O(1)❤️58.5%
0080Remove Duplicates from Sorted Array II[Go]({{< relref "/ChapterFour/0001~0099/0080.Remove-Duplicates-from-Sorted-Array-II.md" >}})MediumO(n)O(152.3%
0082Remove Duplicates from Sorted List II[Go]({{< relref "/ChapterFour/0001~0099/0082.Remove-Duplicates-from-Sorted-List-II.md" >}})Medium45.9%
0086Partition List[Go]({{< relref "/ChapterFour/0001~0099/0086.Partition-List.md" >}})MediumO(n)O(1)❤️52.0%
0088Merge Sorted Array[Go]({{< relref "/ChapterFour/0001~0099/0088.Merge-Sorted-Array.md" >}})EasyO(n)O(1)❤️46.6%
0125Valid Palindrome[Go]({{< relref "/ChapterFour/0100~0199/0125.Valid-Palindrome.md" >}})EasyO(n)O(1)44.3%
0141Linked List Cycle[Go]({{< relref "/ChapterFour/0100~0199/0141.Linked-List-Cycle.md" >}})EasyO(n)O(1)❤️47.4%
0142Linked List Cycle II[Go]({{< relref "/ChapterFour/0100~0199/0142.Linked-List-Cycle-II.md" >}})MediumO(n)O(1)❤️48.7%
0143Reorder List[Go]({{< relref "/ChapterFour/0100~0199/0143.Reorder-List.md" >}})Medium52.5%
0148Sort List[Go]({{< relref "/ChapterFour/0100~0199/0148.Sort-List.md" >}})Medium55.1%
0151Reverse Words in a String[Go]({{< relref "/ChapterFour/0100~0199/0151.Reverse-Words-in-a-String.md" >}})Medium32.7%
0160Intersection of Two Linked Lists[Go]({{< relref "/ChapterFour/0100~0199/0160.Intersection-of-Two-Linked-Lists.md" >}})Easy54.3%
0167Two Sum II - Input Array Is Sorted[Go]({{< relref "/ChapterFour/0100~0199/0167.Two-Sum-II-Input-Array-Is-Sorted.md" >}})MediumO(n)O(1)60.0%
0189Rotate Array[Go]({{< relref "/ChapterFour/0100~0199/0189.Rotate-Array.md" >}})Medium39.4%
0202Happy Number[Go]({{< relref "/ChapterFour/0200~0299/0202.Happy-Number.md" >}})Easy54.8%
0234Palindrome Linked List[Go]({{< relref "/ChapterFour/0200~0299/0234.Palindrome-Linked-List.md" >}})EasyO(n)O(1)50.2%
0283Move Zeroes[Go]({{< relref "/ChapterFour/0200~0299/0283.Move-Zeroes.md" >}})EasyO(n)O(1)61.4%
0287Find the Duplicate Number[Go]({{< relref "/ChapterFour/0200~0299/0287.Find-the-Duplicate-Number.md" >}})MediumO(n)O(1)❤️59.1%
0344Reverse String[Go]({{< relref "/ChapterFour/0300~0399/0344.Reverse-String.md" >}})EasyO(n)O(1)76.7%
0345Reverse Vowels of a String[Go]({{< relref "/ChapterFour/0300~0399/0345.Reverse-Vowels-of-a-String.md" >}})EasyO(n)O(1)50.1%
0349Intersection of Two Arrays[Go]({{< relref "/ChapterFour/0300~0399/0349.Intersection-of-Two-Arrays.md" >}})EasyO(n)O(n)70.9%
0350Intersection of Two Arrays II[Go]({{< relref "/ChapterFour/0300~0399/0350.Intersection-of-Two-Arrays-II.md" >}})EasyO(n)O(n)56.0%
0392Is Subsequence[Go]({{< relref "/ChapterFour/0300~0399/0392.Is-Subsequence.md" >}})Easy47.6%
0455Assign Cookies[Go]({{< relref "/ChapterFour/0400~0499/0455.Assign-Cookies.md" >}})Easy49.9%
0457Circular Array Loop[Go]({{< relref "/ChapterFour/0400~0499/0457.Circular-Array-Loop.md" >}})Medium32.6%
0475Heaters[Go]({{< relref "/ChapterFour/0400~0499/0475.Heaters.md" >}})Medium36.5%
0524Longest Word in Dictionary through Deleting[Go]({{< relref "/ChapterFour/0500~0599/0524.Longest-Word-in-Dictionary-through-Deleting.md" >}})MediumO(n)O(1)51.0%
0532K-diff Pairs in an Array[Go]({{< relref "/ChapterFour/0500~0599/0532.K-diff-Pairs-in-an-Array.md" >}})MediumO(n)O(n)41.2%
0541Reverse String II[Go]({{< relref "/ChapterFour/0500~0599/0541.Reverse-String-II.md" >}})Easy50.5%
0557Reverse Words in a String III[Go]({{< relref "/ChapterFour/0500~0599/0557.Reverse-Words-in-a-String-III.md" >}})Easy81.9%
0567Permutation in String[Go]({{< relref "/ChapterFour/0500~0599/0567.Permutation-in-String.md" >}})MediumO(n)O(1)❤️44.3%
0581Shortest Unsorted Continuous Subarray[Go]({{< relref "/ChapterFour/0500~0599/0581.Shortest-Unsorted-Continuous-Subarray.md" >}})Medium36.4%
0611Valid Triangle Number[Go]({{< relref "/ChapterFour/0600~0699/0611.Valid-Triangle-Number.md" >}})Medium50.5%
0633Sum of Square Numbers[Go]({{< relref "/ChapterFour/0600~0699/0633.Sum-of-Square-Numbers.md" >}})Medium34.4%
0653Two Sum IV - Input is a BST[Go]({{< relref "/ChapterFour/0600~0699/0653.Two-Sum-IV-Input-is-a-BST.md" >}})Easy61.0%
0658Find K Closest Elements[Go]({{< relref "/ChapterFour/0600~0699/0658.Find-K-Closest-Elements.md" >}})Medium46.8%
0696Count Binary Substrings[Go]({{< relref "/ChapterFour/0600~0699/0696.Count-Binary-Substrings.md" >}})Easy65.5%
0719Find K-th Smallest Pair Distance[Go]({{< relref "/ChapterFour/0700~0799/0719.Find-K-th-Smallest-Pair-Distance.md" >}})Hard36.7%
0763Partition Labels[Go]({{< relref "/ChapterFour/0700~0799/0763.Partition-Labels.md" >}})MediumO(n)O(1)❤️79.7%
0795Number of Subarrays with Bounded Maximum[Go]({{< relref "/ChapterFour/0700~0799/0795.Number-of-Subarrays-with-Bounded-Maximum.md" >}})Medium52.8%
0821Shortest Distance to a Character[Go]({{< relref "/ChapterFour/0800~0899/0821.Shortest-Distance-to-a-Character.md" >}})Easy71.3%
0825Friends Of Appropriate Ages[Go]({{< relref "/ChapterFour/0800~0899/0825.Friends-Of-Appropriate-Ages.md" >}})Medium46.3%
0826Most Profit Assigning Work[Go]({{< relref "/ChapterFour/0800~0899/0826.Most-Profit-Assigning-Work.md" >}})MediumO(n log n)O(n)44.9%
0832Flipping an Image[Go]({{< relref "/ChapterFour/0800~0899/0832.Flipping-an-Image.md" >}})Easy80.8%
0838Push Dominoes[Go]({{< relref "/ChapterFour/0800~0899/0838.Push-Dominoes.md" >}})MediumO(n)O(n)57.0%
0844Backspace String Compare[Go]({{< relref "/ChapterFour/0800~0899/0844.Backspace-String-Compare.md" >}})EasyO(n)O(n)48.1%
0845Longest Mountain in Array[Go]({{< relref "/ChapterFour/0800~0899/0845.Longest-Mountain-in-Array.md" >}})MediumO(n)O(1)40.2%
0870Advantage Shuffle[Go]({{< relref "/ChapterFour/0800~0899/0870.Advantage-Shuffle.md" >}})Medium51.8%
0876Middle of the Linked List[Go]({{< relref "/ChapterFour/0800~0899/0876.Middle-of-the-Linked-List.md" >}})Easy75.6%
0881Boats to Save People[Go]({{< relref "/ChapterFour/0800~0899/0881.Boats-to-Save-People.md" >}})MediumO(n log n)O(1)53.1%
0922Sort Array By Parity II[Go]({{< relref "/ChapterFour/0900~0999/0922.Sort-Array-By-Parity-II.md" >}})Easy70.7%
09233Sum With Multiplicity[Go]({{< relref "/ChapterFour/0900~0999/0923.3Sum-With-Multiplicity.md" >}})MediumO(n^2)O(n)45.3%
0925Long Pressed Name[Go]({{< relref "/ChapterFour/0900~0999/0925.Long-Pressed-Name.md" >}})EasyO(n)O(1)33.1%
0942DI String Match[Go]({{< relref "/ChapterFour/0900~0999/0942.DI-String-Match.md" >}})Easy77.3%
0969Pancake Sorting[Go]({{< relref "/ChapterFour/0900~0999/0969.Pancake-Sorting.md" >}})Medium70.1%
0977Squares of a Sorted Array[Go]({{< relref "/ChapterFour/0900~0999/0977.Squares-of-a-Sorted-Array.md" >}})EasyO(n)O(1)71.9%
0986Interval List Intersections[Go]({{< relref "/ChapterFour/0900~0999/0986.Interval-List-Intersections.md" >}})MediumO(n)O(1)71.3%
1040Moving Stones Until Consecutive II[Go]({{< relref "/ChapterFour/1000~1099/1040.Moving-Stones-Until-Consecutive-II.md" >}})Medium55.9%
1048Longest String Chain[Go]({{< relref "/ChapterFour/1000~1099/1048.Longest-String-Chain.md" >}})Medium59.2%
1089Duplicate Zeros[Go]({{< relref "/ChapterFour/1000~1099/1089.Duplicate-Zeros.md" >}})Easy51.5%
1332Remove Palindromic Subsequences[Go]({{< relref "/ChapterFour/1300~1399/1332.Remove-Palindromic-Subsequences.md" >}})Easy76.2%
1385Find the Distance Value Between Two Arrays[Go]({{< relref "/ChapterFour/1300~1399/1385.Find-the-Distance-Value-Between-Two-Arrays.md" >}})Easy66.5%
1679Max Number of K-Sum Pairs[Go]({{< relref "/ChapterFour/1600~1699/1679.Max-Number-of-K-Sum-Pairs.md" >}})Medium57.3%
1721Swapping Nodes in a Linked List[Go]({{< relref "/ChapterFour/1700~1799/1721.Swapping-Nodes-in-a-Linked-List.md" >}})Medium67.2%
1877Minimize Maximum Pair Sum in Array[Go]({{< relref "/ChapterFour/1800~1899/1877.Minimize-Maximum-Pair-Sum-in-Array.md" >}})Medium79.9%
------------------------------------------------------------------------------------------------------------------------------------------------

<div style="display: flex;justify-content: space-between;align-items: center;"> <p><a href="https://books.halfrost.com/leetcode/ChapterTwo/String/">⬅️上一页</a></p> <p><a href="https://books.halfrost.com/leetcode/ChapterTwo/Linked_List/">下一页➡️</a></p> </div>