Back to Leetcode Go

2.03 ✅ Two Pointers

website/content.en/ChapterTwo/Two_Pointers.md

1.7.9711.0 KB
Original Source

Two Pointers

  • Classic way to write the two-pointer sliding window. The right pointer keeps moving to the right until it can no longer move right (the specific condition depends on the problem). After the right pointer reaches the far right, start moving the left pointer to release the left boundary of the window. Problem 3, Problem 76, Problem 209, Problem 424, Problem 438, Problem 567, Problem 713, Problem 763, Problem 845, Problem 881, Problem 904, Problem 978, Problem 992, Problem 1004, Problem 1040, Problem 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)
	}
  • Fast and slow pointers can be used to find duplicate numbers, with time complexity O(n), Problem 287.
  • After replacing letters, the longest possible length of consecutive identical letters. Problem 424.
  • SUM problem set. Problem 1, Problem 15, Problem 16, Problem 18, Problem 167, Problem 923, Problem 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%
------------------------------------------------------------------------------------------------------------------------------------------------