02-13：leetcode重刷1之双指针

双指针的思路：

一般在排好序的数组中寻找某种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