ZXAlgorithm - C7 Two Pointers

Outline
相向雙指針
同向雙指針

Two Sum
Partition
Sort

0 Templete

同向雙指針，相向雙指針，Two Sum
鏈表上的快慢指針
快速排序 & 歸并排序
Loop one variable, research the change of another variable, while(start < end)
類型：

  • 背向雙指針
    第一節(jié)課中的 Longest Palindromic Substring 的中心線枚舉算法
    第二節(jié)課中的 Find K Closest Elements
  • 相向雙指針
    Two Sum 的一大類題（兩位數(shù)的相關(guān)變形題）
    Partition 的一大類題（兩位數(shù)相關(guān)變形題）
  • 同向雙指針
    滑動(dòng)窗口類 Sliding Window
    快慢指針類 Fast & Slow Pointers

1 同向雙指針

Lintcode 604.Window Sum
http://www.lintcode.com/problem/window-sum/
https://www.jiuzhang.com/solutions/?search=window%20sum

Leetcode 283.Move zeros
https://leetcode.com/problemset/all/?search=move%20zero
http://www.lintcode.com/problem/move-zeroes/
https://www.jiuzhang.com/solutions/?search=move%20zero
右邊指針指向的數(shù)字不是0的都堆到左邊指針指向的位置
S: Int left = 0, right = 0;
D: left is the index of first 0, right is current index

LeetCode 26.Remove Duplicates from Sorted Array
https://leetcode.com/problems/remove-duplicates-from-sorted-array/
http://www.lintcode.com/problem/remove-duplicate-numbers-in-array/
https://www.jiuzhang.com/solutions/?search=remove%20duplicate%20numbers%20in%20array
https://leetcode.com/problems/remove-duplicates-from-sorted-array/discuss/11751/Simple-Python-solution-O(n)
區(qū)分Sorted和Unsorted，如果是sorted用一個(gè)pointer標(biāo)識(shí)當(dāng)前位置，如果是unsorted，還需要一個(gè)set來判斷是否有重復(fù)的
for (Map.Entry<Integer, Boolean> entry : mp.entrySet())
nums[result++] = entry.getKey();

2 相向雙指針

兩根指針一頭一尾，向中間靠攏直到相遇
時(shí)間復(fù)雜度 O(n)

Leetcode 125/680. Valid Palindrome I/II
驗(yàn)證一個(gè)字符串是否為回文串，忽略大小寫和非英文字母字符
https://leetcode.com/problemset/all/?search=valid%20palindrome
http://www.lintcode.com/problem/valid-palindrome/
http://www.jiuzhang.com/solution/valid-palindrome/
isalpha()和isdigit()來去掉非想要的字符串
Follow up: 可以刪掉一個(gè)字符
http://www.lintcode.com/problem/valid-palindrome-ii/
https://www.jiuzhang.com/solution/valid-palindrome-ii/
把is_palindrome抽象成一個(gè)函數(shù)來復(fù)用
Lintcode 8.Rotate string
http://www.lintcode.com/problem/rotate-string/
https://www.jiuzhang.com/solutions/?search=rotate%20string
S: offset = offset % str.length
D: 3 reverse method, careful with offset and place
Left,right and whole
Lintcode 39.Recover rotated sorted array
http://www.lintcode.com/en/problem/recover-rotated-sorted-array/
https://www.jiuzhang.com/solutions/?search=Recover%20rotated%20sorted%20array
三段翻轉(zhuǎn)即可，用雙指針in place翻轉(zhuǎn)數(shù)組
D: find offset
And then use 3 reverse method, careful with left++ and right-- list.get()/.set(,)
Sort
Arrays.sort(m, Collections.reverseOrder());
Collections.sort(m, Collections.reverseOrder());

3 Two sum

Leetcode 1.Two sum
https://leetcode.com/problems/two-sum/
http://www.lintcode.com/problem/two-sum/ http://www.jiuzhang.com/solutions/two-sum/
哈希表(HashMap) vs 兩根指針(Two Pointers)
D: Use two pointer or Hashmap: store negative value in map, and find if anything remain match

Lintcode 607.Two sum III data structure design
http://www.lintcode.com/problem/two-sum-data-structure-design/ https://www.jiuzhang.com/solution/two-sum-iii-data-structure-design/
D: HashMap

Leetcode 167.Two Sum II - Input array is sorted
https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
http://www.lintcode.com/problem/two-sum-input-array-is-sorted/ http://www.jiuzhang.com/solutions/two-sum-input-array-is-sorted/
Two Pointers and narrow the range相向指針
D: Two pointers: should be sorted array, and 2 pointer from left to right

Lintcode Unique pairs
http://www.lintcode.com/en/problem/two-sum-unique-pairs/ http://www.jiuzhang.com/solutions/two-sum-unique-pairs/
D: Sort and remove duplicate in the while(left < right), that is remove duplicate before moving pointers
找到相等的時(shí)候別停下來，繼續(xù)找就行。
注意跳過相等元素避免重復(fù)方案。

Lintcode 57.Three Sum
http://www.lintcode.com/problem/3sum/
http://www.jiuzhang.com/solutions/3sum/
統(tǒng)計(jì)所有的和為 0 的三元組 (Triples)
D: Sort and fix one point(remove duplicate) and do the two sum on the right of the point, because this point is checked, it will not be checked in the next index

Lintcode 382.Triangle Count
http://www.lintcode.com/problem/triangle-count/ http://www.jiuzhang.com/solutions/triangle-count/
S: left, right, ans
D: Fix the one value t = i 0->len-1, set left and right between 0-t find 2 sides > one side then ans = ans + (right - left) remember right and left is index

Two sum計(jì)數(shù)問題

統(tǒng)計(jì)所有和 <= target 的配對(duì)數(shù)
Lintcode Two Sum - Less than or equal to target
http://www.lintcode.com/problem/two-sum-less-than-or-equal-to-target/ http://www.jiuzhang.com/solutions/two-sum-less-than-or-equal-to-target/
set a count and update count use right - left or left - right
'<=' target
D: use two pointers, when <= target, ans = ans + (right - left)
Lintcode Two Sum - Greater than target
http://www.lintcode.com/en/problem/two-sum-greater-than-target/ http://www.jiuzhang.com/solutions/two-sum-greater-than-target/
'>=' target
D: same as the above , 一個(gè)是左邊位置，一個(gè)是右邊
統(tǒng)計(jì)所有和 >= target 的配對(duì)數(shù)

Lintcode Two Sum Closest
http://www.lintcode.com/problem/two-sum-closest-to-target/ http://www.jiuzhang.com/solutions/two-sum-closest/
D: Return the difference, use Math.min()

Follow up:
Lintcode Three Sum Closest
http://www.lintcode.com/problem/3sum-closest/ http://www.jiuzhang.com/solutions/3sum-closest/
loop one value then do the 2 sumclosest

總結(jié)

對(duì)于求 2 個(gè)變量如何組合的問題
可以循環(huán)其中一個(gè)變量，然后研究另外一個(gè)變量如何變化
Trapping Rain Water
https://leetcode.com/problems/trapping-rain-water/
https://leetcode.com/problems/trapping-rain-water/discuss/17554/Share-my-one-pass-Python-solution-with-explaination

5 Partition

Leetcode 31.Partition Array
D: use two pointers, when left > target and right <= target then exchange each other
http://www.lintcode.com/problem/partition-array/ http://www.jiuzhang.com/solutions/partition-array/

Lintcode Quick select
http://www.lintcode.com/problem/kth-smallest-numbers-in-unsorted-array/
https://www.jiuzhang.com/solution/kth-smallest-numbers-in-unsorted-array/
http://www.lintcode.com/problem/kth-largest-element/
https://www.jiuzhang.com/solution/kth-largest-element/
小視頻：http://www.jiuzhang.com/video/quick-select/
Kth smallest numbers in unsorted array
D: first set the pivot and get it's place in the array, then you will know the kth is in the left or right
Kth largest element
D: same as above

5 Sort

Quick Sort(binary search)
Quick sort is not stable, merge sort is stable but need O(n) space
Sort Colors
http://www.lintcode.com/problem/sort-colors/ http://www.jiuzhang.com/solutions/sort-colors/ 分成兩個(gè)部分 vs 分成三個(gè)部分
S: pl, pr, i
D: red, white and blue, Two pointers, use I to go through, pl to represent red end, pr to blue start
Rainbow sort
http://www.lintcode.com/en/problem/sort-colors-ii/ http://www.jiuzhang.com/solutions/sort-colors-ii/
S: colors[], left, right, colorFrom, colorTo
D: Use quick sort by 1-k, use colarMid = (colorFrom + colorTo)/2 as pivot

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容