双指针法

• 对于数组，指两个变量在数组上相向移动解决的问题。
• 对于链表，指两个变量在链表上同向移动解决的问题，也称为「快慢指针」问题，比如典型的判定链表中是否包含环。

1. 数组使用示例-1
   1. 使用两个指针，右指针始终往右移动;
   2. 如果右指针指向的值等于左指针指向的值，左指针不动,右指针右移一步;
   3. 如果右指针指向的值不等于左指针指向的值，那么左指针往右移一步，然后再把右指针指向的值赋给左指针。 ```python

      删除排序数组中的重复项，返回删除后数组的长度，不使用额外的内存空间

def test(nums):

# 设置左右指针初始值
left, right = 0, 1
# 如果左右指针没有超过数组项数，左指针的值不等于右指针的值，左指针向右移动，右指针的值赋值给左指针
while left < len(nums) and right < len(nums):
    if nums[left] != nums[right]:
        left += 1
        nums[left] = nums[right]
    right += 1
return left + 1, nums[: left + 1]

print(test([1, 4, 6, 7, 7, 7, 8, 8, 99]))

    tips：使用逆序遍历，可避免数组索引溢出的问题
```python
for i in range(len([1, 3, 4, 4, 4, 4 ,4])-1, 0, -1):
    print(i)

数组常用双指针算法

leetcode题目：二分查找—实现x的平方根

# 实现x的平方根（二分查找）
def test_2(num):
    left, right = 0, num
    if num < 2:
        return num
    while left + 1 < right:
        # 计算mid防止溢出
        mid = left + (right - left)//2
        # 如果中位数的平方小于num，则左指针右移动（中位数赋值给左指针）
        if mid * mid <= num:
            left = mid
        # 如果中位数的平方大于num，则右指针右移动（中位数赋值给右指针）
        elif mid * mid > num:
            right = mid
    # 最大右指针的平方小于等于num，则num的平方根是right
    if (right * right) <= num:
        return right
    # 否则num的平方根是left
    else:
        return left

leetcode题目：二分查找—猜数字

"""
猜数字游戏的规则如下：

每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：

-1：我选出的数字比你猜的数字小 pick < num
1：我选出的数字比你猜的数字大 pick > num
0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num
返回我选出的数字。

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/binary-search/xee4ev/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""
   class Solution:
    def guessNumber(self, n: int) -> int:
        left, right = 1, n
        while left < right:
            mid = left + (right - left) // 2
            # 我选的数字比预期小，区间在[left, mid]
            if guess(mid) <= 0:
                right = mid
            # 我选的数字比预期大，区间在[mid，right]
            elif guess(mid) > 0 :
                left = mid + 1

        return left

 """
 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。


示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-search
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 """
# 模式一
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)
        while left < right:
            # 设置中位数
            mid = left + (right - left)// 2
            # 如果目标值大于中点，则收紧左侧边界
            if nums[mid] < target:
                left = mid + 1
            # 如果目标值小于中点，则锁定右侧边界
            elif nums[mid] > target:
                right = mid
            else:
                return mid
        return -1

# 模式二    
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            # 设置中点
            mid = left + (right - left) // 2
            # 如果目标值大于中点
            if nums[mid] < target:
                # 左指针向右移动一步
                left += 1
            # 如果目标值小于中点
            elif nums[mid] > target:
                # 右指针向左移动一步
                right -= 1
            else:
                # 找到目标值
                return mid
        # 找不到目标值，返回-1
        return -1

leetcode题目：合并两个有序数组

"""
给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""


class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        # 初始化l为nums1的开始索引，r为nums2的开始索引，index为nums1从末开始的索引
        l, r, index = m - 1, n - 1, len(nums1) - 1
        # 如果nums1和nums2的索引不溢出，则循环
        while l >= 0 and r >= 0:
            # 如果nums1的值比较大，则将值赋值到nums1的最末项，从后往前
            if nums1[l] >= nums2[r]:
                # 赋值给最后项
                nums1[index] = nums1[l]
                # nums1的开始索引往前移
                l -= 1
            # 如果nums2的值比较大，则赋值到nums1当前的末项
            elif nums1[l] < nums2[r]:
                nums1[index] = nums2[r]
                # nums2的开始索引往前移
                r -= 1
            # 每次赋值index都不停的往前移动
            index -= 1

        # 因为nums1的某项如果等于nums2，移动赋值的是nums1,所以如果nums2不为空的话，直接赋值到nums1剩下的坑位
        while r >= 0:
            nums1[index] = nums2[r]
            r -= 1
            index -= 1

# 时间复杂度o(m+n),空间复杂度o(m+n)

leetcode题目：反转字符串中的单词III

# 切片
class Solution:
    def reverseWords(self, s: str) -> str:
        return ' '.join([i[::-1] for i in s.split(' ')])

# 两次切片
class Solution:
    def reverseWords(self, s: str) -> str:
        return ' '.join(s.split( )[::-1])[::-1]


# 双指针：右指针移动，如果遇到空格则停下在左指针和右指针之间反转单词
# 在每个单词做同样的操作，如果到达末尾则停止
class Solution:
    def reverseWords(self, s: str) -> str:
        n = len(s)  # 字符串的长度（包含空格）
        chars = list(s) # 字符串转为list
        left, right = 0, 0  # 初始化左右指针
        while left < n and right < n:
            if chars[right] != ' ' and right != n-1:
                right += 1  # 右指针在没有到达列表末尾或者没有遇到空格，则一直移动
            else:
                tmp = right - 1 if chars[right] == ' ' else right
                mid = left + (tmp - left) // 2 # 设置中点
                # 如果左指针没有超过临时中点
                # 则循环替换字符串
                while left <= mid:
                    chars[left], chars[tmp] = chars[tmp], chars[left]
                    # 左指针右移
                    left += 1
                    # 临时右指针左移
                    tmp -= 1
                # 单词反转完毕后，更新左指针为下一个单词的开头
                left = right + 1
                # 将右指针也更新为下一个单词的开头
                right = left
        return ''.join(chars)