LeetCode 刷题进大厂(2)— Two Pointers

今天介绍数组中 two pointers 方法，或者说是模板来解决一些数组的问题，two pointers 这里按照同向和反向方式给大家进行介绍，所谓同向就是两个指针同时朝着一个方向进行运动，反向也就是两个指针相对面对面地去移动。

涉及到 LeetCode 题目

通常许多问题都是数组有关，数组作为一种数据结构是大部分算法主要操作的对象，一般都是在数组上做文章。

同向

两个指针朝着一个方向移动，就是同向。

有关每一个区间是左闭右开，还是其他形式定义需要根据题目而定，需要保持一致，而且区间边界上元素不能同时具有两个含义。

反向

反向相对于同向要简单一些，也就是 0 – i 和 j – n 都是处理过的数据。

通用解题步骤

• 初始化 2 指针，如果是从左往右则初始化指针为 0 否则初始化指针为 n
• 接下来就是向前移动 j 指针知道数组(列表)的末尾，每次向前移动 j 检查 j 是否我们需要值，如果 j 位置是我们需要的值，就将 j 位置值 copy 到 i 位置上，同时将 i 向前移动一个位置，来等待接受下一个我们需要的值。如果 j 位置不是我们需要值，则继续向前移动到下一个位置。

实战

Reverse String

这是一道翻转字符串的题目，编写一个可以反转字符串的函数。输入的字符串是一个字符数组 s。在不开辟新的空间在原有数组上进行调整来实现字符串翻转。

有关这个题目我们就可以用到上面介绍过模板来套用这道题，其实这个步骤算是比较复杂的一步。当我们拿到一道题如何将其对应到一个知识点，这也是面试官要考察的你的方面，也是难点，通常我们也可以读懂问题，也熟悉各种算法，但是就是不知道如何将算法对号入座。

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        i = 0
        j = len(s) - 1
        while i < j:
            tmp = s[i]
            s[i] = s[j]
            s[j] = tmp
            i += 1
            j -= 1
复制代码

这道题就是我们数组的起始端和结束端出发来交换 i 和 j 位置元素从而实现了字符串反转的效果。字符串字符数量可能是偶数也可能是奇数，对于 $i < j$ 如果是偶数时

这个过程我用图解的形式表示清楚，希望能够换来大家一个点赞。

Two Sum II – Input array is sorted

已知条件是有一个从小到大已经排序好的整数数组，从中找到两个数字，这两数字相加和等于特定的数字。要求返回的一个数组，数组包含两个数字的对应的索引，索引起始注意不是 0 而是 1 这样的表达。

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left = 0
        right = len(numbers) - 1
        
        while left < right:
            curr = numbers[left] + numbers[right]
            if curr < target:
                left += 1
            elif curr > target:
                right -= 1
            else:
                return [left + 1,right+1]
        return [-1,-1]
复制代码

问题简单是因为这是一个从小到大的数组，然后从左右两侧指针。

Remove Duplicates from Sorted Array

给出一个按从小到大排列的整数数组 nums，要求将其中重复的元素删除，也就是每个元素只出现一次。去掉重复元素后各个元素的相对位置应该保持不变，要求是不可以开辟额外空间。

通过图示方式已经给大家解释如何用同向方式来解决这个去重的问题，接下来我们就来看一看代码，只要我们把问题分析清楚了，代码看起来应该不算很难。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        print(len(nums))
        i = 0
        j = 0
        while j < len(nums):
            if i == 0 or (nums[j] != nums[i-1]):
                nums[i] = nums[j]
                i += 1
                j += 1
                
                
            else:
                j+=1
        
        return i
复制代码