double_pointer.md

双指针

双指针法经常应用在数组，字符串与链表的题目上。 对于很多问题，双指针法能带来更简洁的解法，带来更快的性能。

remove-element

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

很经典的题目，有多种解法。但文中只要求给出新数组的长度，因此使用双指针如下:

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        bef = 0
        for aft in range(len(nums)):
            if nums[aft] != val:
                nums[bef], nums[aft] = nums[aft], nums[bef]
                bef += 1
        
        return bef

[reverse-string] (https://leetcode.cn/problems/reverse-string/)

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

class Solution:
    def reverseString(self, s: List[str]) -> None:
				left, right = 0, len(s) - 1
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

当然python自带函数

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        s[:] = s[::-1]

ti-huan-kong-ge-lcof

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

注意：实现函数，就不能用python的官方函数

class Solution:
    def replaceSpace(self, s: str) -> str:
        ### 双指针解法
        kongge = [i for i in s if i == ' ']
        cnt = len(kongge)
        ns = ['' for i in range(len(s) + 3 * cnt)]
        new = 0
        for org in range(len(s)):
            if s[org] == ' ':
                ns[new:new+3] = ['%', '2', '0']
                new = new + 3
            else:
                ns[new] = s[org]
                new = new + 1
        
        return ''.join(ns)

数组：移除元素 字符串：反转字符串 字符串：替换空格 字符串：翻转字符串里的单词 链表：翻转链表 链表：删除链表的倒数第 N 个结点 链表：链表相交 链表：环形链表 双指针：三数之和 双指针：四数之和 双指针：总结篇！