目录
问题引入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真有人会这样想吧 *
过程：
初始化双指针 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/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/
总结
双指针：考虑两个指针处的状态，一般不考虑指针中间的区间
滑动窗口：维护窗口内的状态，更新指针位置、记录答案
好了，以上就是全部内容。大家喜欢的话可以关注博主，后续会持续更新滴
标签：right,nums,python,ans,领悟,数组,超高频,指针,left From： https://blog.csdn.net/2401_87245677/article/details/145194334