双指针的思路：
一般在排好序的数组中寻找某种pair
主要有两种吧
一种是同时从前面开始
另一种是前后开始
1、两数之和为某值，167. 两数之和 II - 输入有序数组
（1）前后指针
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
i=0
k=len(numbers)
j=k-1
while i<j:
if numbers[i]+numbers[j]>target:
j=j-1
elif numbers[i]+numbers[j]<target:
i=i+1
else:
break
result=[]
result.append(i+1)
result.append(j+1)
return result
2、合并的排序数组，面试题 10.01. 合并排序的数组
（2）同向的两个指针
从头开始：
class Solution:
def merge(self, A: List[int], m: int, B: List[int], n: int) -> None:
"""
Do not return anything, modify A in-place instead.
"""
i=0
j=0
res=[]
while i<m or j<n:
if i==m:
res.append(B[j])
j=j+1
elif j==n:
res.append(A[i])
i=i+1
elif A[i]<B[j]:
res.append(A[i])
i=i+1
else:
res.append(B[j])
j=j+1
A[:]=res
return
从末尾开始
class Solution:
def merge(self, A: List[int], m: int, B: List[int], n: int) -> None:
"""
Do not return anything, modify A in-place instead.
"""
i=m-1
j=n-1
t=m+n-1
while i>=0 or j>=0:
if i==-1:
A[t]=B[j]
j=j-1
elif j==-1:
A[t]=A[i]
i=i-1
elif A[i]>B[j]:
A[t]=A[i]
i=i-1
else:
A[t]=B[j]
j=j-1
t=t-1
return
3、子序列问题
双指针
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
n, m = len(s), len(t)
i = j = 0
while i < n and j < m:
if s[i] == t[j]:
i += 1
j += 1
return i == n
网友评论