Outline
相向双指针
同向双指针
Two Sum
Partition
Sort
0 Templete
同向双指针，相向双指针，Two Sum
链表上的快慢指针
快速排序 & 归并排序
Loop one variable, research the change of another variable, while(start < end)
类型：
- 背向双指针
第一节课中的 Longest Palindromic Substring 的中心线枚举算法
第二节课中的 Find K Closest Elements - 相向双指针
Two Sum 的一大类题（两位数的相关变形题）
Partition 的一大类题（两位数相关变形题） - 同向双指针
滑动窗口类 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
右边指针指向的数字不是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)
区分Sorted和Unsorted，如果是sorted用一个pointer标识当前位置，如果是unsorted，还需要一个set来判断是否有重复的
for (Map.Entry<Integer, Boolean> entry : mp.entrySet())
nums[result++] = entry.getKey();
2 相向双指针
两根指针一头一尾，向中间靠拢直到相遇
时间复杂度 O(n)
Leetcode 125/680. Valid Palindrome I/II
验证一个字符串是否为回文串，忽略大小写和非英文字母字符
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: 可以删掉一个字符
http://www.lintcode.com/problem/valid-palindrome-ii/
https://www.jiuzhang.com/solution/valid-palindrome-ii/
把is_palindrome抽象成一个函数来复用
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
三段翻转即可，用双指针in place翻转数组
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
找到相等的时候别停下来，继续找就行。
注意跳过相等元素避免重复方案。
Lintcode 57.Three Sum
http://www.lintcode.com/problem/3sum/
http://www.jiuzhang.com/solutions/3sum/
统计所有的和为 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计数问题
统计所有和 <= target 的配对数
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 , 一个是左边位置，一个是右边
统计所有和 >= target 的配对数
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
- Related questions
4Sum
http://www.lintcode.com/problem/4sum/
http://www.jiuzhang.com/solutions/4sum/
Two Sum - difference equals to target
(同向双指针)
http://www.lintcode.com/problem/two-sum-difference-equals-to-target/
http://www.jiuzhang.com/solutions/two-sum-difference-equals-to-target/
总结
对于求 2 个变量如何组合的问题
可以循环其中一个变量，然后研究另外一个变量如何变化
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
- Related Questions
Partition Array by Odd and Even
http://www.lintcode.com/problem/partition-array-by-odd-and-even/
http://www.jiuzhang.com/solutions/partition-array-by-odd-and-even/
Interleaving Positive and Negative Numbers
http://www.lintcode.com/problem/interleaving-positive-and-negative-numbers/
http://www.jiuzhang.com/solutions/interleaving-positive-and-negative-integers/
Sort Letters by Case
http://www.lintcode.com/problem/sort-letters-by-case/
http://www.jiuzhang.com/solutions/sort-letters-by-case/
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/ 分成两个部分 vs 分成三个部分
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
- Other Sort
Pancake sort
https://en.wikipedia.org/wiki/Pancake_sorting http://www.geeksforgeeks.org/pancake-sorting/
Like selection sort , use 2 reverse process to get the maximum value in the end
Use as few reversals as possible instead of comparison( you can only use flip here)
Sleep sort
https://rosettacode.org/wiki/Sorting_algorithms/
Use thread
Spaghetti sort
https://en.wikipedia.org/wiki/Spaghetti_sort
Parallel and lowering
Bogo sort
https://en.wikipedia.org/wiki/Bogosort
Shuffle and check
