AlgorithmTwo Pointers

LeetCode 分类刷题 —— Two Pointers

Two Pointers 的 Tips:

  • 双指针滑动窗口的经典写法。右指针不断往右移,移动到不能往右移动为止(具体条件根据题目而定)。当右指针到最右边以后,开始挪动左指针,释放窗口左边界。第 3 题,第 76 题,第 209 题,第 424 题,第 438 题,第 567 题,第 713 题,第 763 题,第 845 题,第 881 题,第 904 题,第 978 题,第 992 题,第 1004 题,第 1040 题,第 1052 题。
	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 题。
Title Solution Difficulty Time Space 收藏
3. Longest Substring Without Repeating Characters Go Medium O(n) O(1) ❤️
11. Container With Most Water Go Medium O(n) O(1)
15. 3Sum Go Medium O(n^2) O(n) ❤️
16. 3Sum Closest Go Medium O(n^2) O(1) ❤️
18. 4Sum Go Medium O(n^3) O(n^2) ❤️
19. Remove Nth Node From End of List Go Medium O(n) O(1)
26. Remove Duplicates from Sorted Array Go Easy O(n) O(1)
27. Remove Element Go Easy O(n) O(1)
28. Implement strStr() Go Easy O(n) O(1)
30. Substring with Concatenation of All Words Go Hard O(n) O(n) ❤️
42. Trapping Rain Water Go Hard O(n) O(1) ❤️
61. Rotate List Go Medium O(n) O(1)
75. Sort Colors Go Medium O(n) O(1) ❤️
76. Minimum Window Substring Go Hard O(n) O(n) ❤️
80. Remove Duplicates from Sorted Array II Go Medium O(n) O(1
86. Partition List Go Medium O(n) O(1) ❤️
88. Merge Sorted Array Go Easy O(n) O(1) ❤️
125. Valid Palindrome Go Easy O(n) O(1)
141. Linked List Cycle Go Easy O(n) O(1) ❤️
142. Linked List Cycle II Go Medium O(n) O(1) ❤️
167. Two Sum II - Input array is sorted Go Easy O(n) O(1)
209. Minimum Size Subarray Sum Go Medium O(n) O(1)
234. Palindrome Linked List Go Easy O(n) O(1)
283. Move Zeroes Go Easy O(n) O(1)
287. Find the Duplicate Number Go Easy O(n) O(1) ❤️
344. Reverse String Go Easy O(n) O(1)
345. Reverse Vowels of a String Go Easy O(n) O(1)
349. Intersection of Two Arrays Go Easy O(n) O(n)
350. Intersection of Two Arrays II Go Easy O(n) O(n)
424. Longest Repeating Character Replacement Go Medium O(n) O(1)
524. Longest Word in Dictionary through Deleting Go Medium O(n) O(1)
532. K-diff Pairs in an Array Go Easy O(n) O(n)
567. Permutation in String Go Medium O(n) O(1) ❤️
713. Subarray Product Less Than K Go Medium O(n) O(1)
763. Partition Labels Go Medium O(n) O(1) ❤️
826. Most Profit Assigning Work Go Medium O(n log n) O(n)
828. Unique Letter String Go Hard O(n) O(1) ❤️
838. Push Dominoes Go Medium O(n) O(n)
844. Backspace String Compare Go Easy O(n) O(n)
845. Longest Mountain in Array Go Medium O(n) O(1)
881. Boats to Save People Go Medium O(n log n) O(1)
904. Fruit Into Baskets Go Medium O(n log n) O(1)
923. 3Sum With Multiplicity Go Medium O(n^2) O(n)
925. Long Pressed Name Go Easy O(n) O(1)
930. Binary Subarrays With Sum Go Medium O(n) O(n) ❤️
977. Squares of a Sorted Array Go Easy O(n) O(1)
986. Interval List Intersections Go Medium O(n) O(1)
992. Subarrays with K Different Integers Go Hard O(n) O(n) ❤️
1004. Max Consecutive Ones III Go Medium O(n) O(1)
1093. Statistics from a Large Sample Go Medium O(n) O(1)
支付宝扫码打赏 微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章

一缕殇流化隐半边冰霜's Picture
一缕殇流化隐半边冰霜

我是于德志 (@halfrost),一名来自中国的 iOS 开发者,已退役 acmer 。现居上海。从 2016 年开始写博客记录自己技术成长的一点一滴,到年底,成为简书推荐作者,2016 年度掘金最优秀的 10 佳原创作者。吾笃信:天道酬勤,勤能补拙。地道酬实,实能不弱。人道酬德,德能补寡。 目前就职于 饿了么 。

Shanghai「上海」 https://halfrost.com

Subscribe to Halfrost's Field | 冰霜之地

Get the latest posts delivered right to your inbox.

or subscribe via RSS with Feedly!

Comments