代码收藏家技术教程 2025-01-20

超高频算法——双指针思想的领悟 python

问题引入1

给你一个数组（按非递减顺序排列），假定为【2，4，5，6，7，9】
请你在数组中找到两个数满足：相加等于10，返回它们的值。

你是一个不知道双指针为何物的新手小白：哇！简单啊，我直接令2为第一个数不动，接着依次枚举剩下的数作为第二个数，然后check是否和为10，发现没有找到两个数和为10，那只好接着枚举4为第一个数······看起来编程根本难不倒我啊！

那有没有效率高的做法呢？我会告诉你：有的，兄弟有的。

解决方案

随便选择两个数，5和9，相加大于10，那我可以说5和9中间的数与9相加也大于10。
进一步想：我选2和9发现大于10，那么可以得出9和数组中任意数相加是大于10的。
那我不妨直接在数组中删去10，say goodbye with 10
现在是【2，4，5，6，7】，我又发现：2+7<10，即2与数组任意数相加都小于10
那我也在数组中删掉2······
为什么可以删呢？因为数组是排好序的。（tips：有序就要往二分双指针上面去想）

Talk is cheap. Show me the code.

a = [2, 4, 5, 6, 7, 9]
left, right = 0, len(a) - 1
while left < right:
    sum = a[left] + a[right]
    if sum < 10:
        left += 1
    elif sum > 10:
        right -= 1
    else:
        print(a[left], a[right])
        break

# 结果是 4 6

暴力做法：找两个数相加与10比较，时间复杂度是O(n^2)
优化做法：找最小的数和最大的数相加与10比较，时间复杂度是O(n)
This is called 双指针。
双指针（Two Pointers）是一种算法技巧，常用于解决数组或链表相关的编程问题。这种方法的基本思想是使用两个指针变量遍历数据结构的不同部分，从而达到优化性能的目的。

那数组是无序的呢？还用说啊，sort一下不就行了，反正要输出的是数组中的元素值，不是对应的下标，时间复杂度O(nlogn)

牛刀小试

那三数之和怎么办？什么，还有高手？

三数之和 https://leetcode.cn/problems/3sum/description/

经过前面的学习，O(n^3)肯定不会写出来了吧。
正解：先排序后外层循环枚举第一个数这样问题是不是就和刚才一样了呢再使用双指针

This is code

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        ans = []
        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            left, right = i + 1, len(nums) - 1
            while left < right:
                sum = nums[i] + nums[left] + nums[right]
                if sum < 0:
                    left += 1
                elif sum > 0:
                    right -= 1
                else:
                    ans.append([nums[i], nums[left], nums[right]])
                    left += 1
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    right -= 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1
        return ans

问题引入2

给定一个数组a=[1,5,4,3,2,6,7,8,9,2]，将其调整成：奇数在奇数位，偶数在偶数位
只能在原数组上修改，~~你这题目，真令我欢喜~~

解决方案

思路：设置两个指针，分别表示奇数位指针和偶数位指针。
接着只看数组最后一个元素，若为奇数，则与奇数位指针所指的元素交换；
若为偶数，则与偶数位指针所指的元素交换。同时奇数位指针去往下一个位置或者偶数位指针去往下一个位置。
可以想象数组最后一个元素为邮政公司，分别往奇数和偶数家庭发邮件。

code如下（示例）：

a = [1, 5, 4, 3, 2, 6, 7, 8, 9, 2]
even = 0
odd = 1
while even < len(a) and odd < len(a):
    if a[-1] % 2 == 0:
        a[even], a[-1] = a[-1], a[even]
        even += 2
    else:
        a[odd], a[-1] = a[-1], a[odd]
        odd += 2
print(a) # [2, 1, 6, 5, 4, 3, 2, 7, 8, 9]

举一反三

是到大展身手的时候了吗？直接来吧

给定一个整数数组a=[1,8,6,2,5,4,8,3,7] ，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：不能倾斜容器 *~~这是个奇奇怪怪的说明，bushi真有人会这样想吧~~ *

来源：力扣（LeetCode）

过程：
初始化双指针 left，right 分列水槽左右两端；
循环收缩直至双指针相遇时跳出；
更新面积最大值 ans ；
选择两板中的短板，向中间收一格；
返回面积最大值 ans

关键：
可容纳水的高度由两板中的短板决定
要矩阵面积越大，两条垂直线的距离越远，两条垂直线的最短长度也要越长。
指针每一次移动，都可以排除一个柱子

~~忆！悟！~~

亲自动手试试吧纸上得来终觉浅，绝知此事要躬行
盛最多水的容器https://leetcode.cn/problems/container-with-most-water/description/

题解：

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        ans = 0
        while left < right:
            area = (right - left) * min(height[left], height[right])
            ans = max(ans, area)
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return ans

没有悟的小伙伴可以去看力扣官方题解哦https://leetcode.cn/problems/container-with-most-water/solutions/207215/sheng-zui-duo-shui-de-rong-qi-by-leetcode-solution/

实战演练（双指针）

最接近的三数之和 https://leetcode.cn/problems/3sum-closest/
四数之和 https://leetcode.cn/problems/4sum/
接雨水 https://leetcode.cn/problems/trapping-rain-water/description/

问题引入3

给定一个正整数数组a=[2,3,1,2,4,3]，找出总和大于等于7的长度最小的子数组
返回其长度，如果不存在返回 0 。

暴力：使用两个 for 循环，一个 for 循环固定一个数字，另一个 for 循环从下一个元素开始累加，当和大于等于 7的时候终止内层循环，记录下最小长度。时间复杂度O(n^2)

思考一下：选定2，3，1，2四个数，发现sum大于7。假如再把4加进去，已知四个数和大于7，那五个数肯定和大于7——选择缩小左端点，变成3，1，2，4。发现大于7，继续缩小左端点，变成1，2，4，停止，更新答案。
接着把3加进去，发现大于7，缩小左端点，判断是否符合······
总结：
1.维护一个有条件的不定长滑动窗口；
2.右端点右移，导致窗口扩大，不满足条件；
3.左端点右移，为了缩小窗口，重新满足条件

示例code：

a = [2, 3, 1, 2, 4, 3]
n = len(a) 
left = sum = 0
ans = n  # 初始化为inf也行
for right in range(n):
    sum += a[right]
    while sum >= 7:
        ans = min(ans, right - left + 1)  # +1怎么理解，假设left和right指向同一个位置，长度应该为1
        sum -= a[left]
        left += 1
print(ans)  # 2

来试试吧！

长度最小的子数组 https://leetcode.cn/problems/minimum-size-subarray-sum/description/

题解：

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        ans = inf
        left, sum = 0, 0
        for right in range(len(nums)):
            x = nums[right]
            sum += x
            while sum >= target:
                ans = min(ans, right - left + 1)
                sum -= nums[left]
                left += 1
        if ans <= len(nums):
            return ans
        else:
            return 0

What is 滑动窗口

滑动窗口技术（Sliding Window Technique）是一种用于解决数组或字符串中子数组或子串问题的算法设计方法。通过维护一个动态窗口来遍历整个数据结构，从而高效地找到满足特定条件的子数组或子串。

关键要素

核心思想是使用两个指针（通常称为左右边界或起点终点），形成一个窗口，然后根据问题需求调整窗口的大小和位置

实战演练（滑动窗口）

【easy】每个字符最多出现两次的最长子字符串 https://leetcode.cn/problems/maximum-length-substring-with-two-occurrences/description/
【medium】删除最短的子数组使剩余数组有序 https://leetcode.cn/problems/shortest-subarray-to-be-removed-to-make-array-sorted/description/
【hard】找出唯一性数组的中位数 https://leetcode.cn/problems/find-the-median-of-the-uniqueness-array/description/