线性表中的双指针法是指通过两个指针（游标）来指示线性表中的元素的方法。双指针的使用本身并没有什么神奇之处，但是通过合适地操纵指针的移动，在某些特定问题中却能化腐朽为神奇，大大降低算法的时间复杂度。
根据对双指针不同的移动规则，整理了常用的双指针方法及其所用来解决的问题：
| 双指针法 | 操作说明 | 经典问题 |
|---|---|---|
| 首尾指针 | 使用两个指针指示线性表的首尾元素 | 二分查找、NSum |
| 口袋指针 | 一个指针指示口袋口，另一个指针用于遍历 | 数组划分 |
| 窗口指针 | 两个指针指示窗口范围 | 窗口蠕动法求解连续子序列问题 |
| 快慢指针 | 使用两个移动速度不同的指针 | 环的检测和交点确定 |
| 早晚指针 | 使用出发时间不同的两个指针 | 消除距离差额 |
| 双表指针 | 两个指针分别指示两个线性表当前位置 | 数组归并 |
1. 首尾指针
- 适用问题：需要同时操作首尾元素，或者需要指示变化中的线性表范围，使用首尾指针经常需要先对数组进行排序；
- 使用思路：
- 指针含义：l指示线性表首部元素，r指示线性表尾部元素
- 移动规则：依条件向内移动，直至相遇
1.1 反转线性表
- 问题：[344] 反转字符串，请编写一个函数，其功能是将输入的字符串反转过来；
- 思路：使用首尾指针交换元素，然后首尾指针向内移动，直至首指针不再小于尾指针；
- 代码：
class Solution(object):
def reverseString(self, s):
"""
:type s: str
:rtype: str
"""
l, r = 0, len(s) - 1
res = list(s)
while l < r:
res[l],res[r] = res[r],res[l]
l += 1
r -= 1
return ''.join(res)
- 分析：空间O(n)，时间O(n)
1.2 盛最多水的容器
- 问题：[11]盛最多水的容器，给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。画 n 条垂直线，使得垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
- 思路：分治+首尾指针，问题首先划分为两个子问题，使用两侧较小边和不使用两侧较小边，然后取二者中的最大值；使用较小边时，容器两侧容纳最多的水，不使用较小边的子问题可以是原始问题的同类子问题，可以用递归求解，也可以用首尾指针来求，如果使用了较小边l，收集当前最大后l++，反之较小边为r则r--，直至l==r
image.png
- 代码：
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
l,r = 0,len(height) - 1
res = 0
while l < r:
if height[l] < height[r]:
res = max(res,height[l]*(r-l))
l += 1
else:
res = max(res,height[r]*(r-l))
r -= 1
return res
- 分析：空间O(1)，时间O(n)
1.3 二分查找
# 闭区间写法:用[l,r]代表当前查找范围
def Binary_search(L,key):
'''
@L:有序数组
@key:目标值
@return:如果查找成功则返回目标元素索引，如果查找失败则返回目标值应插入的位置
'''
# 闭区间-初始化窗口
l,r = 0,len(L)-1
# 闭区间-退出条件：窗口内不含元素，l=r+1，目标值在l,r之间
while l <= r:
mid = (l + r)//2
if key == L[mid]:
return mid
elif key > L[mid]:
l = mid + 1
else:
r = mid - 1
return l
1.4 2Sum
1.4.1 无序数组的2Sum
- 问题：[1] 两数之和，给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用
- 思路：使用哈希表存储元素残差，如果元素在哈希表则说明和为target，返回
- 代码：
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
d = {}
for i,num in enumerate(nums):
if num not in d:
d[target-num] = i
else:
return [d[num],i]
- 分析:空间O(n)，时间O(n)
1.4.2 有序数组的2Sum
- 问题：[167] 两数之和 II，给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2
- 思路：首尾指针法，如果量元素之和小于target则移动右移左指针，如果大于则左移右指针，如果相等，则返回两下标
- 代码：
class Solution(object):
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
low,high = 0,len(numbers)-1
while low <= high:
total = numbers[low] + numbers[high]
if total == target:
return [low+1,high+1]
elif total < target:
low += 1
else:
high -= 1
- 分析：空间O(1)，时间O(n)
1.4.3 3Sum
- 问题：[15]三数之和，给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
- 思路：先排序+2Sum，先对数组进行排序，从前向后每次选取一个不同的元素x作为基准，然后在后面的数组中找到所有不重复的2Sum等于target-x的组合，再合并收集；保证解完备且不重复的核心有两点（选择下一个不同元素中的第一个）：①基准选择：每次选择下一个不同元素中的第一个，不同基准不会有重复解，第一个元素作为基准不会漏解②2Sum时：每次移动指针到第一个不重复的位置，也保证了2Sum的完备且不重复
- 代码：
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
n = len(nums)
target = 0
res = []
for i in xrange(n-2):
if i == 0 or nums[i] != nums[i-1]:
base = nums[i]
l,r = i + 1, n - 1
while l < r:
if nums[l] + nums[r] == target - base:
res.append([base,nums[l],nums[r]])
l,r = l+1,r-1
while l < r and nums[l] == nums[l-1]: l += 1
while l < r and nums[r] == nums[r+1]: r -= 1
elif nums[l] + nums[r] < target - base:
l += 1
else:
r -= 1
return res
- 分析：空间$O(1)$，时间$O(n^2)$
1.4.4 Nsum
- 问题：[18] 四数之和，给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组
- 思路：排序+递归+2Sum，NSum可以转化为N-1Sum，逐步转化为2Sum，类似的只要每次选取下一个不同元素中的第一个元素，就能保证最终解的完备且不重复
- 代码：
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
def NSum(nums, target, N):
n = len(nums)
if n < N or nums[0] * N > target or nums[-1] * N < target:
return []
res = []
if N == 2:
l,r = 0, n-1
while l < r:
if nums[l] + nums[r] < target:
l += 1
elif nums[l] + nums[r] > target:
r -= 1
else:
res.append([nums[l],nums[r]])
l += 1
r -= 1
while l < r and nums[l] == nums[l-1]:l += 1
while l < r and nums[r] == nums[r+1]:r -= 1
return res
else:
for i in xrange(n-N+1):
# 核心，保证了两轮解中不包含重复解
if i == 0 or nums[i] != nums[i-1]:
for pre in NSum(nums[i+1:],target-nums[i],N-1):
res.append([nums[i]] + pre)
return res
return NSum(sorted(nums),target,4)
- 分析：空间$O(1)$，时间$O(n^{N-1})$
1.4.5. 最接近的三数之和
- 问题：[16. 最接近的三数之和]给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
- 思路：排序后转化为2Sum，收集绝对差值最小的组合
- 代码：
class Solution(object):
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
n = len(nums)
if n < 3:
return None
nums.sort()
res = None
delta = float('inf')
for i in xrange(n-2):
if i == 0 or nums[i] != nums[i-1]:
l, r = i + 1, n-1
while l < r:
cur = nums[i] + nums[l] + nums[r] - target
if abs(cur) < delta:
res = [nums[i],nums[l],nums[r]]
delta = abs(cur)
if cur == 0:
return target
elif cur > 0:
r -= 1
else:
l += 1
return sum(res)
2. 口袋指针
- 适用问题：将数组中满足条件的元素移至一端，要求原地修改且满足条件的元素相互位置保持稳定；
- 使用思路：假想用一只“袋子”盛放满足条件的元素，初始时袋子为空，用l=-1指示袋子口的位置，使用另一个指针从0开始遍历整个数组，如果当前元素满足条件，则袋口+1，将当前元素通过交换放入袋中，当遍历结束时，所有满足条件的元素就都被放入到袋子中了。
2.1 移动0
- 问题：[283] 移动零，给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序
- 思路：口袋指针法，初始口袋口-1，遍历整个数组，如果元素不等于0，袋口扩充，并将该元素和袋口元素交换
- 代码：
class Solution(object):
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
i = -1
for j in range(len(nums)):
if nums[j]:
i += 1
nums[i],nums[j] = nums[j], nums[i]
- 分析：空间O(1)，时间O(n)
2.2 红白蓝划分
- 问题：[75] 分类颜色，给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色
- 思路：两次口袋指针法，先把0放头部，再把1放0后面数组的头部；或者使用首尾两个口袋，一次遍历将0放头口袋，将2放尾口袋
- 代码：
class Solution(object):
"""
思路1：使用前后指针，口袋交换法，将等于0的交换至前面，将等于2的交换至右边
开区间表示两次装袋
思路2：双边装袋，略显复杂，还不如遍历两次
"""
def sortColors(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
n = len(nums)
i,j = -1,n
k = 0
while k < j:
if nums[k] == 0:
i += 1
nums[k],nums[i] = nums[i],nums[k]
k += 1
elif nums[k] == 2:
j -= 1
nums[k],nums[j] = nums[j],nums[k]
else:
k += 1
- 分析：空间O(1)，时间O(n)
2.3 快排划分
- 问题：选取首元素作为枢轴值，将数组中小于等于该值的元素交换至头部，大于该值的交换置数组尾部，返回枢轴值最终的位置
- 思路：口袋指针法
- 代码：
def partition(A,low,high):
"""
在A[low:high+1]中选取枢轴点，并按首轴值排序
"""
i = low
for j in xrange(low+1,high+1):
if A[j] <= A[low]:
i += 1
A[i],A[j] = A[j],A[i]
A[i],A[low] = A[low],A[i]
return i
- 分析:空间O(1)，时间O(n)
2.4 寻找第k大
- 问题：[215] 数组中的第K个最大元素,在未排序的数组中找到第 k 个最大的元素
- 思路：有很多方法可以求解此问题，但最高效的方法是口袋指针法，类似于快排划分，将首元素作为枢轴值，将所有大于等于它的元素交换至数组头部，返回数轴值最终位置pivot，如果枢轴值位置刚好是k-1，则说明该位置的值即为第k大的值，如果i <k-1,在有半部分nums[i+1:]寻找k-i-1大，如果i > k-1，在左半边nums[:i]寻找第k大
- 代码：
class Solution(object):
"""
思路1：先排序，时间O(nlgn)
思路2：建立大根堆，弹出第k个O(n+klgn)
思路3：口袋指针法，平均O(n)，以首元素为枢轴值，进行划分
1. 如果数轴位置i==k-1则直接返回i对应的值
2. 如果i <k-1,在有半部分nums[i+1:]寻找k-i-1大
3. 如果i > k-1，在左半边nums[:i]寻找第k大
"""
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
n = len(nums)
if n < 1 or n < k:
return None
if n == 1:
return nums[0]
pivot = self.partition(nums,0,n-1)
if pivot == k - 1:
return nums[pivot]
elif pivot < k - 1:
return self.findKthLargest(nums[pivot+1:],k-pivot-1)
else:
return self.findKthLargest(nums[:pivot],k)
def partition(self,nums,low,high):
bag = low
for i in range(low+1,high+1):
if nums[i] >= nums[low]:
bag += 1
nums[bag],nums[i] = nums[i], nums[bag]
nums[bag], nums[low] = nums[low],nums[bag]
return bag
- 分析：最好情形$T(n)=T(n/2)+O(n)$，空间复杂度O(lgn)，时间复杂度为O(n)
3. 窗口指针
包含剪枝条件的连续子序列问题：
- 连续子序列问题：求解满足条件f的连续子序列；
- 包含剪枝条件：如果在找到了一个首次满足特定条件g的连续子序列之后，发现可以排除掉(l<=x<r,x<=y<r)以及(x=l,y>r)部分的解，就可以左移连续子序列的左侧边界l直至条件g不再满足，即(l'<=x,r<=y)不能排除；
image.png
常见的这类问题有：
- 满足条件的最长连续子序列问题；
- 满足条件的最短连续子序列问题；
- 内在的满足剪枝条件的其他类型连续子序列问题；
窗口蠕动法：将连续子序列看做是一个“窗口”，用左右指针l,r来标识窗口，起初窗口为空(l=0,r=-1)，备选解解存在于(x>=l,y>r)，每次通过右移右指针来扩展窗口(l,r)，如果当前窗口满足上述减枝条件g，则通过右移左指针实现剪枝(l',r)，移动过程中收集满足条件f的解，剩余备选解在(x>=l',y>r)中，循环以上过程得到所有满足条件的连续子序列。因为窗口移动的过程通常是由右指针来扩展，由左指针来收缩，很像虫子向前蠕动的过程，因此叫窗口蠕动更形象。
image.png
窗口蠕动包含三个步骤：扩展-剪枝-收集（核心是设计出合适的减枝条件）
- 初始化空窗口l=0,r=-1
- 循环以下过程直至右指针越界
- 扩展：右移右指针
- 剪枝：如果达到下一个可剪枝的窗口，则右移左指针，直至不能再剪枝
- 在窗口满足条件时收集备选解
- 返回最终解
3.1 满足条件的最长连续子序列
3.1.1 无重复最长子串
-
问题:[3] 无重复字符的最长子串，给定一个字符串，找出不含有重复字符的最长子串的长度
-
思路：当窗口首次包含重复时，(r>x>l,r>y>l)(不是最长)以及(x=l,y>r)(包含重复)部分可以剪枝，右移左指针直至包含重复
- ① 初始化窗口l=0,r=-1
- ② 循环以下过程直至右指针越界r==n
- 右移右指针
- 如果当前窗口包含重复，右移左指针，直至当前窗口不包含重复
- 更新不包含重复字符的子串的最大长度
- ③ 返回最大长度
-
代码：
from collections import Counter
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
n = len(s)
dic = Counter()
res = 0
l = 0
for r in xrange(n):
dic[s[r]] += 1
while dic[s[r]] > 1:
dic[s[l]] -= 1
l += 1
res = max(res,r-l+1)
return res
- 分析：空间O(n)，时间O(n)
3.2 满足条件的最短连续子序列
3.2.1 和大于s的最短子数组
- 问题：[209] 长度最小的子数组，给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的子数组。如果不存在符合条件的子数组，返回 0
- 思路：当窗口和首次大于等于s时，(r>x>l,r>y>l)(小于s)以及(x=l,y>r)(不是最短)部分可以剪枝，右移左指针直至窗口和小于s
- ① 初始化窗口l=0,r=-1
- ② 循环以下过程直至右指针越界r==n
- 右移右指针
- 如果当前窗口和>=s，更新最短数组的的长度，右移左指针，直至当前窗口<s
- ③ 返回最大长度
- 代码：
def minSubArrayLen(self, s, nums):
"""
:type s: int
:type nums: List[int]
:rtype: int
"""
n = len(nums)
cur = 0
res = n + 1
i = 0
for j in xrange(n):
cur += nums[j]
while cur >= s:
res = min(res,j-i+1)
cur -= nums[i]
i += 1
return res if res <= n else 0
- 分析：空间O(1)，时间O(n)
3.2.2 最小覆盖子串
连续序列覆盖子串问题是一类非常经典的问题，值得认真体会，关键点有两个：
- 剪枝条件：当已经覆盖时，可以剪枝，l右移至不再覆盖，即第一次need[s[l]]从0变成1的时候
- 用count和need标识总需求和每个字符的需求数：count=0时表示已经覆盖，need为负数时表示已超出需求
- 问题：[76] 最小覆盖子串，给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
- 思路:当窗口首次覆盖子串时，继续扩展r不是最优，(l,r)内不能覆盖，可进行剪枝，右移l直至不再覆盖，不再覆盖不好判断，但不再覆盖的前一位置可以判断。用count统计当前窗口还缺多少个字符，用need记录当前每种字符需求数，如果是负数代表多余个个数。（覆盖问题使用need存放每个元素的需求，使用count存放总需求对于剪枝判断是个很好的技巧，下面我们还会反复遇到）
- 代码：
def minWindow(self, s, t):
"""
:type s: str
:type t: str
:rtype: str
"""
count,need = len(t), Counter(t)
l, L, R = 0, 0, -1
for r, c in enumerate(s):
count -= need[c] > 0
need[c] -= 1
while count == 0:
if R == -1 or r - l < R - L:
L, R = l, r
need[s[l]] += 1
count += need[s[l]] > 0
l += 1
return s[L:R+1]
-分析：空间O(n)，时间O(n)
3.2.3 最小区间
- 问题:[632] 最小区间， 你有 k 个升序排列的整数数组。找到一个最小区间，使得 k 个列表中的每个列表至少有一个数包含在其中。我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小
输入:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
输出: [20,24]
解释:
列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。
列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。
- 思路：同最小覆盖子串，核心在于如何判断刚好已覆盖和刚好未覆盖，将所有值按照(值,所属分组号)排序，在排序后的数组上进行窗口滑动，当刚好都覆盖时进行剪枝，同时收集最优结果，右值l直至刚好不再覆盖。
- 代码：
from collections import Counter
def smallestRange(self, nums):
"""
:type nums: List[List[int]]
:rtype: List[int]
"""
count = len(nums)
need = Counter(range(count))
p = [(val,i) for i in xrange(count) for val in nums[i]]
n = len(p)
p.sort()
l = 0
res = [p[0][0],p[-1][0]]
for r in xrange(n):
count -= need[p[r][1]] > 0
need[p[r][1]] -= 1
while count == 0:
if res[-1] - res[0] > p[r][0] - p[l][0]:
res = [p[l][0],p[r][0]]
need[p[l][1]] += 1
count += need[p[l][1]] > 0
l += 1
return res
- 分析：涉及到排序，空间O(n)，时间O(nlgn)
3.3 其他包含剪枝的连续子序列问题
3.3.1 包含字符串的排列
- 问题：[567] 字符串的排列，给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列
- 思路：窗口蠕动法，只要s2的某个子串的字符统计量等于s1的字符统计量，即返回True。该问题包含减枝条件，当加入的字符统计量超出s1的需求时可以剪枝，右移左指针直至不超，此时判断s1的需求数是否刚好满足，满足则返回True（不多、又刚好满足需求），否则继续扩展窗口。仍然使用need代表每个元素的需求数，用count代表总体需求数。
- 代码：可以看到，代码与上面两题基本上相同
def checkInclusion(self, s1, s2):
"""
:type s1: str
:type s2: str
:rtype: bool
"""
count,need = len(s1),Counter(s1)
l = 0
for r,c in enumerate(s2):
count -= need[c] > 0
need[c] -= 1
while need[c] < 0:
need[s2[l]] += 1
count += need[s2[l]] > 0
l += 1
if count == 0:
return True
return False
- 分析：空间O(n)，时间O(n)
3.3.2 乘积小于K的子数组
- 问题：[713] 乘积小于K的子数组，给定一个正整数数组 nums，找出该数组内乘积小于 k 的连续的子数组的个数
- 思路：直接应用窗口移动法时，不满足剪枝条件，因为(l<x<r,x<=y<r)这部分不能被剪掉，但如果这一部分已被统计过了，就仍然可以正常剪枝。当窗口满足条件时，我们统计以r结束的满足条件的连续数组个数，当r放入后如果不满足条件，我们就可以进行正常的剪枝了，因为后面的肯定不满足，前面的已经被统计过，此时只需要将l移至下个满足条件的位置即可。
- 代码：
def numSubarrayProductLessThanK(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
n = len(nums)
i,j,count,prod = 0,0,0,1
while i <= j < n:
j += 1
prod *= nums[j-1]
while i < j and prod >= k:
prod /= nums[i]
i += 1
count += j - i
return count
- 分析：空间O(1)，时间O(n)
4. 快慢指针
快慢指针：使用移动速度不同的两个指针slow,fast(通常fast移动速度是slow的两倍)来遍历线性表。
环形检测：如果线性表中存在环，那么快慢指针从同一起点出发，如果能够再次相遇，则说明线性表中存在环。
寻找中位数：快慢指针同时从线性表首元素出发，当快指针无法前进时，慢指针会指向下中位。
链表中用的最多，比如[141] 环形链表，[142] 环形链表 II，[234]回文链表，详情参考链表，这里仅讨论在顺序表中的使用
4.1 寻找重复数
- 问题：[287]寻找重复数，给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字，但它可能不止重复出现一次
- 思路:1~n的n+1个整数组成的数组，可以看作是一条静态链表，下标0代表头指针，列表中的值代表next指针，类似于链表中寻找环的交点算法，可以找到数组中的重复元素
- 代码：
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
slow = fast = 0
# 首先找到下一个交点
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
# 排除另一个慢指针，与上一个慢指针同时出发，交点即重复元素
slow2 = 0
while True:
slow = nums[slow]
slow2 = nums[slow2]
if slow == slow2:
return slow
- 分析：空间O(1)，时间O(n^2)
5. 早晚指针
早晚指针：在指针移动某位置时，另一个指针从头出发，主要用处在于产生/消除差额。
使用快慢指针判断环的交点问题中也使用到了早晚指针，另一个经典的应用是寻找链表中倒数第k个节点，原理是当第一个指针移动了k次时，再派出一个指针从头开始同步移动，最后当早指针不能前进时，晚指针指向的就是倒数第k个节点。
5. 双表指针
- 指针含义：两个指针分别用于指示两个线性表中的当前位置
- 指针移动：具体问题具体分析
- 问题特点：当需要同时操作两个线性表时，典型的有数组归并，链表逆序
5.1 数组交集
- 问题：[349] 两个数组的交集，给定两个数组，写一个函数来计算它们的交集
- 思路：该问题使用集合很容易在O(n)时间复杂度下求解，如果不使用集合，可先对数组排序，用两个指针指示两个数组的出现不同元素的第一个元素，如果相等则收集，直至其中一个遍历完。虽然是一种笨的方法，但用到的方法在很多问题中都会遇到。
- 代码：
class Solution(object):
def intersection(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
nums1.sort()
nums2.sort()
m,n = len(nums1),len(nums2)
res = []
i = j = 0
while i < m and j < n:
if nums1[i] == nums2[j]:
res.append(nums1[i])
i,j = i + 1, j + 1
while i < m and nums1[i] == nums1[i-1]: i+= 1
while j < n and nums2[j] == nums2[j-1]: j+= 1
elif nums1[i] > nums2[j]:
j += 1
else:
i += 1
return res
5.2 归并排序
详见链表或者排序
5.3 链表逆序
详见链表
网友评论