双指针总结

ps 狗家很喜欢考dp......

同向双指针

同向双指针的问题，是指两根指针都从头出发，朝着同一个方向前进　　O(N)

eg:

http://www.lintcode.com/problem/remove-duplicate-numbers-in-array/

http://www.lintcode.com/problem/window-sum/

http://www.lintcode.com/problem/two-sum-difference-equals-to-target/

http://www.lintcode.com/problem/middle-of-linked-list/

　　快慢指针

https://www.lintcode.com/problem/linked-list-cycle/

　　背答案题...

eg1: Move Zeros

http://www.lintcode.com/problem/move-zeroes/

要求O(1)的空间

变种1：要求保持原来非0数的相对顺序？　　video 11:00

sol1.1：同向双指针，一个指从左数当前最靠后的0，一个指从左数当前第一个非0，xjb搞。O(N)

变种2：不要求保持原来的相对顺序　　　　video　 19:00

sol2.1：相向双指针，直接挪就行了...　　partition：把数组分成 [非0区 | 0区]，两个指针从两端向中间找，发现不符合的就swap（类似quicksort）

----------------------------------------------------------------------------------------

相向双指针

相向双指针，指的是在算法的一开始，两根指针分别位于数组/字符串的两端，并相向行走。

eg1: reverse string

1 """
2 @param s: a list of characters
3 """
4 def reverse(s):
5     left, right = 0, len(s)-1
6     while left < right:
7         s[left], s[right] = s[right], s[left]
8         left += 1
9         right -= 1

eg2: 判断回文字符串

1 def isPalindrome(s):
2     i, j = 0, len(s)-1
3     while i < j:
4         if s[i] != s[j]:
5             return False
6         i += 1
7         j -= 1
8     return True

eg3: 给一个整数数组，找到两个数使得他们的和等于一个给定的数 target。

 1 class Solution:
 2     def twoSum(self, numbers, target):
 3         numbers.sort()
 4 
 5         L, R = 0, len(numbers)-1
 6         while L < R:
 7             if numbers[L]+numbers[R] == target:
 8                 return (numbers[L], numbers[R])
 9             if numbers[L]+numbers[R] < target:
10                 L += 1
11             else:
12                 R -= 1
13         return None
14 
15 首先我们对数组进行排序。
16 用两个指针(L, R)从左右开始：
17 如果numbers[L] + numbers[R] == target, 说明找到，返回对应的数。
18 如果numbers[L] + numbers[R] < target, 此时L指针右移，只有这样才可能让和更大。
19 反之使R左移。
20 L和R相遇还没有找到就说明没有解。

相向双指针分类

1. reverse类

　　eg1: http://www.lintcode.com/problem/valid-palindrome/
　　follow up: 可以删掉一个字符　　　　http://www.lintcode.com/problem/valid-palindrome-ii/

2. 2sum变种

对于求 2 个变量如何组合的问题，可以循环其中一个变量，然后研究另外一个变量如何变化

　　裸2sum：先排序+相向双指针，NlogN时间+O(1)空间　　　　Video 32:00

　　　　　　也可以用hash做，O(N)时间，但空间多

　　eg: http://www.lintcode.com/problem/two-sum-data-structure-design/ 　　　　Video 38:00

　　eg: https://www.lintcode.com/problem/two-sum-unique-pairs/ 　　　　Video 44:00

　　eg: 3sum　　https://www.lintcode.com/problem/3sum/ 　　　　Video 47:00

　　　　排序+双指针，找 -a = b+c

　　　　for a的位置: {右半边双指针找b+c=-a, 2sum问题}

　　eg: https://www.lintcode.com/problem/triangle-count/ 　　　　　　Video 64:00
　　　　组成三角形的充要条件：最小的两边之和>第三边

　　　　排序+双指针，找 a+b>c

　　　　for c的位置: {左半边双指针找第一个a+b>c，然后把所有满足条件的累加一下。2sum问题}

　　eg: https://www.lintcode.com/problem/two-sum-closest-to-target 　　　　Video 1:17:00

　　eg: http://www.lintcode.com/problem/3sum-closest/

　　eg: http://www.lintcode.com/problem/4sum/

　　eg: http://www.lintcode.com/problem/two-sum-difference-equals-to-target/ 　　　　

3. partition

常用于需要in place的问题

 1 while left<=right:
 2     while left<=right and a[left]:
 3     #当前a[left]这个数就应该在左半边
 4         left+=1
 5     while left<=right and a[right]:
 6     #当前a[right]这个数就应该在右半边
 7         right-=1
 8 
 9     if(left<=right):
10         #找到一个不该在左侧和不该在右侧的，交换它们
11         nums[left], nums[right] = nums[right], nums[left]
12         left+=1
13         right-=1

　　https://www.lintcode.com/problem/partition-array/　　　　Video 1:21:00

Quick Select

随课教程：http://www.jiuzhang.com/tutorial/algorithm/321

http://www.lintcode.com/problem/kth-smallest-numbers-in-unsorted-array/
http://www.lintcode.com/problem/kth-largest-element/

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/

----------------------------
Sort Colors
http://www.lintcode.com/problem/sort-colors/
随课教程 http://www.jiuzhang.com/tutorial/algorithm/354

扩展：三指针　　　　Video 1:40:00

排序 Rainbow Sort
https://www.lintcode.com/problem/sort-colors-ii/