双指针 DualPointer

1、基本概念

双指针算法是指在遍历对象时，使用两个或多个指针（索引、游标）不断进行单向移动来遍历及相应的操作的算法技巧。暴力算法往往可以优化为双指针算法。

双指针的三个关键点：

• 指针的起始位置的选取。可能在同一个序列，也可能在不同序列。
• 指针的移动方向。
• 指针的移动速度。

几种算法模型：

• 对撞指针
• 快慢指针
• 滑动窗口
• 归并排序

2、对撞指针

对撞指针：左右两个指针，向中间靠拢。

例1：二分查找 binarySearch

例2：搜索拼接数组

#一个数组是由两个递增数组首尾拼接的。
#请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
'''
数组从前到后和从后到前分别为两个有序数组，可以从两端同时查找。'''

例3：翻转列表

left, right = 0, len(s)-1
    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1; right -= 1

例4：三数之和

#给你一个整数数组 nums ，判断是否存在三元素和为0。
'''
三指针，滑动窗口和对撞指针的组合
对数组排序后，使用for循环i，同时left=i+1和right=len(n)-1分别向左和向右移动，
相遇时结束，即可遍历(i,left,right)'''

def threeSum(nums: List[int]):
    if len(nums) < 3: return []
    nums, res, n = sorted(nums), [], len(nums)
    for i in range(n - 2):
        l, r = i+1, n-1
        if nums[i] > 0: break #nums[i]<=nums[l]<=nums[r] --> nums[i]<0
        if res != [] and res[-1][0] == nums[i]: continue
        #if i >= 1 and nums[i] == nums[i - 1]: continue #和上一句等价
        while l < r:
            if nums[i] + nums[l] + nums[r] == 0:
                res.append([nums[i], nums[l], nums[r]])
                while l < r-1 and nums[l] == nums[l+1]: l += 1
                while r > l+1 and nums[r] == nums[r-1]: r -= 1
            if nums[i] + nums[l] + nums[r] > 0: r -= 1
            else: l += 1
    return res

3、快慢指针

快慢指针：左右两个指针，一块一慢。

例1：找出单链表中间节点（倒数第n个节点）。

例2：判断子序列。

#给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
#字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。
#（例如，"ace"是"abcde"的一个子序列，而"aec"不是）
'''
设置两个指针i,j；i从s的第一个字符开始，j从t的第一个字符开始，当相等时，i和j都右移，
不相等则仅j右移，最后如果i等于s的长度，那么说明完全匹配成功，s是t的子序列。'''

4、滑动窗口

滑动窗口：左右两个指针组成一个"窗口",右指针不断扩张，左指针按条件收缩。

例1：最大连续1的个数。

#给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。
#返回仅包含 1 的最长（连续）子数组的长度。
'''
本题求最大连续1的个数，就是在小于等于k个0的基础上求最长符合条件区间的长度。我们使用双指针l r，
代表窗口的两边，从最初开始遍历数组，如果值为1或者此时区间 [l, r] 中0的个数 <= k,
我们就向右移指针r扩大窗口，并更新0的个数，当0的个数大于k，我们就需要更新最大符合条件的区间长度。
然后右移l缩小窗口，更新0的个数，继续重复直至右指针超出数组下标界限，遍历结束，
此时记录最大区间长度的值即为所求。'''

例2：最大区间。

#给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
def longest(lst):
    m= i= j= 0; l=len(lst); d=set()  #集合和指针全局声明，新一轮可以参考上一轮遍历进度
    while i<l:
        if lst[i] in d: #如果新的不在上一轮集合里面，则长度不会超上一轮长度，跳过
            d=set(); j=i #重置集合和左指针
        else:
            d.add(lst[i])
            while j>=0:   #从上一轮最长长度处开始遍历。
                if lst[j] not in d:
                    d.add(lst[j]); j-=1
                else:
                    m=max(m,i-j)
                    break
        i += 1
    return m

5、归并排序

例： 合并两个有序数组。

def merge(nums1,nums2):
    sort = []
    p1 = p2 = 0 ; m,n = len(nums1),len(nums2)
    while p1 < m or p2 < n:
        if p1 == m:
            sort.append(nums2[p2])
            p2 += 1
        elif p2 == n:
            sort.append(nums1[p1])
            p1 += 1
        elif nums1[p1] < nums2[p2]:
            sort.append(nums1[p1])
            p1 += 1
        else:
            sort.append(nums2[p2])
            p2 += 1
    return sort