双指针：对撞/快慢/分离/滑动窗口的案例(数组/回文/求和等)
Author：zhoulujun Date：
回顾《数组二分查找到二分法的感悟笔记》,其实二分查找就是双指针。对于双指针，特别推荐：
双指针的种类
对撞指针（Collision）
指的是两个指针left、right 分别指向序列第一个元素和最后一个元素，然后left 指针不断递增，right 不断递减，直到两个指针的值相撞（即left==right），或者满足其他要求的特殊条件为止。
适用场景
对撞指针一般用来解决有序数组或者字符串问题：
查找有序数组中满足某些约束条件的一组元素问题：比如二分查找、数字之和等问题。
字符串反转问题：反转字符串、回文数、颠倒二进制等问题。
快慢指针（Forward）
两个指针方向相同。适合解决数组中的移动、删除元素问题，或者链表中的判断是否有环、长度问题。
使用两个指针slow、fast。slow 一般指向序列第一个元素，即：slow=0，fast 一般指向序列第二个元素，即：fast=1。
在循环体中将左右指针向右移动。当满足一定条件时，将慢指针右移，即slow+=1。当满足另外一定条件时（也可能不需要满足条件），将快指针右移，即fast+=1。
到快指针移动到数组尾端（即fast==len(nums)−1），或者两指针相交，或者满足其他特殊条件时跳出循环体。
适用场景
解决链表中的问题，如检测链表中是否存在环、找到链表的中点等。
解决数组中的问题，如移除数组中的重复元素等。
分离双指针（Parallel）
两个指针分别属于不同的数组，两个指针分别在两个数组中移动。
适用场景
查找两个数组的交集：找到两个数组中共同包含的元素。
查找两个数组的并集：找到两个数组中所有不同的元素。
比较两个数组的差异：比较两个数组并找出它们的差异。
滑动窗口（Sliding Window）
滑动窗口通过维护一个窗口，从左到右移动窗口，以找到满足特定条件的子数组或子串。
滑动窗口的思想非常简单，它将子数组（子字符串）理解成一个滑动的窗口，然后将这个窗口在数组上滑动，在窗口滑动的过程中，左边会出一个元素，右边会进一个元素，然后只需要计算当前窗口内的元素值即可。
算法思路
使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个「窗口」。
先不断地增加 right 指针扩大窗口 [left, right]，直到窗口符合要求
停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的字符串不再符合要求。同时，每次增加 left，我们都要更新一轮结果。
重复第 2 和第 3 步，直到 right 到达尽头。
第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解。 左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动。
适用场景
滑动窗口算法思想是非常重要的一种思想，可以用来解决数组，字符串的子元素问题。它可以将嵌套循环的问题，转换为单层循环问题，降低时间复杂度，提高效率。
适用于解决数组或字符串中子串问题，如找到最小覆盖子串、找到最长无重复字符子串、如找到数组中的最长连续子数组等。
双指针的题包括
两数之和（Two Sum）：在数组中找到两个数，使它们的和等于目标值。
三数之和（3Sum）：在数组中找到所有不重复的三元组，使得三个数的和等于零。
四数之和（4Sum）：在数组中找到四个数，使它们的和等于目标值。
两数之和 II - 输入有序数组（Two Sum II - Input array is sorted）：在有序数组中找到两个数，使它们的和等于目标值。
盛最多水的容器(container-with-most-water)：找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
移动零（Move Zeroes）：给定一个数组，将数组中的零移到数组的末尾，同时保持非零元素的相对顺序。
反转字符串中的元音字母（Reverse Vowels of a String）：给定一个字符串，反转字符串中的所有元音字母。
最长连续递增序列（Longest Continuous Increasing Subsequence）：给定一个未排序的整数数组，找出最长连续递增序列的长度。
最长连续递减序列（Longest Continuous Decreasing Subsequence）：给定一个未排序的整数数组，找出最长连续递减序列的长度。
合并区间（Merge Intervals）：给定一个区间的集合，合并所有重叠的区间。
合并两个有序数组（Merge Sorted Array）：给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
两个数组的交点（Intersection of Two Arrays）：给定两个数组，编写一个函数来计算它们的交集。
两个数组的交点 II（Intersection of Two Arrays II）：给定两个数组，编写一个函数来计算它们的交集，且结果可以是非递减顺序。
最小覆盖子串（Minimum Window Substring）：给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串。
最长重复子数组（Maximum Length of Repeated Subarray）：给定两个整数数组 A 和 B，找到两个数组中公共的、长度最长的子数组的长度。
最长和谐子序列（Longest Harmonious Subsequence）：给定一个整数数组，找出数组中最长的和谐子序列的长度。
有效的括号（Valid Parentheses）：给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串，判断字符串是否有效。
合并K个排序链表（Merge k Sorted Lists）：合并 k 个排序链表，返回合并后的排序链表。
删除排序数组中的重复项（Remove Duplicates from Sorted Array）：给定一个排序数组，需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
大哥分类好的：
https://algo.itcharge.cn/01.Array/04.Array-Two-Pointers/02.Array-Two-Pointers-List/
https://github.com/labuladong/fucking-algorithm/blob/master/算法思维系列/双指针技巧.md
对撞双指针
太多了，下面挑一些典型案例来记：
两数之和
function test(nums,target){
let left = 0,right = nums.length-1;
while (left<right){
const sum = nums[left]+nums[right];
if(sum===target){
return [left,right]
}if(sum>target){
right--
}else {
left --
}
}
return [-1,-1];
}两数之和其实就是二分查找
三数之和
https://programmercarl.com/0015.三数之和.html
这个解释：https://cloud.tencent.com/developer/article/2262666
function threeSum(arr, target) {
if (arr.length < 3) return []; // 如果数组长度小于3，直接返回空数组
arr.sort((a, b) => a - b); // 对数组进行排序
const result = []; // 初始化结果数组
// 遍历数组，使用双指针法寻找三数之和
for (let i = 0; i < arr.length - 2; i++) {// 记得是 arr.length - 2
if (i > 0 && arr[i] === arr[i - 1]) continue; // 跳过重复的元素，避免重复解
/**
*不可以改为：if (arr[i] === arr[i - 1]) i++;会导致在某些情况下跳过有效解。例如，对于数组 [0, 0, 0] 和目标值 0，
正确的解应该是 [[0, 0, 0]]，但使用 if (arr[i] === arr[i - 1]) i++ ; 会导致跳过所有的 0，从而得到空解。
*/
let left = i + 1; // 初始化左指针
let right = arr.length - 1; // 初始化右指针
while (left< right) { // 当左指针小于右指针时，继续寻找三数之和
const sum = arr[i] + arr[left] + arr[right]; // 计算当前三数之和
if (sum === target) { // 如果三数之和等于目标值，将结果添加到结果数组中，并移动左右指针
result.push([arr[i], arr[left], arr[right]]);
left++;
right--;
// 跳过重复的元素，避免重复解
while (left< right && arr[left] === arr[left + 1]) left++;
while (left< right && arr[right] === arr[right - 1]) right--;
} else if (sum< target) {// 如果三数之和小于目标值，移动左指针
left++;
}else {// 如果三数之和大于目标值，移动右指针
right--;
}
}
}
return result; // 返回结果数组
}四数之和
https://leetcode.cn/problems/4sum/description/
var fourSum = function (nums, target) {
const length = nums.length;
if (length < 4) {
return [];
}
const result = [];
// 首先排序,然后
nums.sort((a, b) => a - b);
for (let i = 0; i < length - 3; i++) {// 外层循环，遍历数组中的每个元素
if (i > 0 && nums[i - 1] === nums[i]) {// 跳过重复的元素
continue;
}
// 因为升序，如果前四个就大于target，再往后取只会更大，直接跳出循环
if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
break;
}
//num[i] 和最大3个数相加都小与target，那么和其他数相加只会更下，所以只有加大当前值（前移)
if (nums[i] + nums[length - 1] + nums[length - 2] + nums[length - 3] < target) {
continue; //前元素 nums[i]与数组中最大的3个数（最后三个数）相加还是小于target，则num[i]不可能找到一个和为 target 的四元组。
}
for (let j = i + 1; j < nums.length - 2; j++) {// 内层循环，遍历数组中的每个元素
if (j > i + 1 && nums[j] === nums[j - 1]) {
continue;
}
let left = j + 1, right = nums.length - 1;// 初始化左右指针
while (left < right) {
const sum = nums[i] + nums[j] + nums[left] + nums[right];
if (sum > target) { // 如果和大于目标值，将右指针向左移动
right--;
} else if (sum < target) {
left++;
} else {
result.push([nums[i], nums[j], nums[left], nums[right]]);
while (left < right && nums[left] === nums[left + 1]) {// 跳过重复的元素
left++;
}
left++;
while (left < right && nums[right] === nums[right - 1]) {
right--;
}
right--;
}
}
}
}
return result;
};解法是一样的。
有序数组的平方
https://leetcode.cn/problems/squares-of-a-sorted-array/
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：输入：nums = [-4,-1,0,3,10] 输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100] 排序后，数组变为 [0,1,9,16,100]
这个题有三种解法：
直接平方，然后再对结果排序。
利用类似归并排序算法，即依次比较原负数部分平方和正数部分平方，使用两个指针分别指向位置 neg 和neg+1，每次比较两个指针对应的数，选择较小的那个放入答案并移动指针。当某一指针移至边界时，将另一指针还未遍历到的数依次放入答案。
双指针-直接比较、逆序放入（每次直接比较两个指针对应的数的平方值，选择较大的那个逆序放入答案并移动指针）
推荐第三种方案，详细推荐阅读：https://programmercarl.com/0977.有序数组的平方.html
function sortedSquares (nums) {
// 因为数组是有序数组，如果数组全部为正数，直接返回即可。
if(nums.length<2||num[0]>0){
return nums.map(num=>num*num)
}
let l = nums.length;
let result = new Array(l).fill(0);
// 定义三个指针：i指向数组起始位置，j指向数组末尾位置，k指向结果数组末尾位置
let leftKey = 0, rightKey = l - 1, resultRightKey = l - 1;
// 使用双指针从数组两端向中间遍历
while (leftKey <= rightKey) {
let left = nums[leftKey] * nums[leftKey];
let right = nums[rightKey] * nums[rightKey];
// 比较左右指针对应的平方值，将较大的值放入结果数组的末尾
if (left < right) {
// 如果右指针的平方值较大，则将该值存入结果数组末尾，并将右指针向左移动
result[resultRightKey--] = right;//先将 right 的值赋给 result[resultRightKey]，然后再将其减1。
rightKey--;
} else {
// 如果左指针的平方值较大或相等，则将该值存入结果数组末尾，并将左指针向右移动
result[resultRightKey--] = left;
leftKey++;
}
}
// 返回最终的结果数组
return result;
};凡是有序的数组操作，都可以考虑下双指针：
一个指针指向数组的开始，另一个指针指向数组的结束。
比较两个指针所指向的元素的平方，将较大的平方放入结果数组的末尾，并将对应的指针向中间移动。
重复步骤2，直到两个指针相遇。
二维数组中的查找
https://github.com/CyC2018/CS-Notes/blob/master/notes/4.%20二维数组中的查找.md
给定一个二维数组，其每一行从左到右递增排序，从上到下也是递增排序。给定一个数，判断这个数是否在该二维数组中。
Consider the following matrix:
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
Given target = 5, return true. Given target = 20, return false.
要求时间复杂度 O(M + N)，空间复杂度 O(1)。其中 M 为行数，N 为 列数。
这个问题可以使用一种类似于双指针的方法解决，具体步骤如下：
从矩阵的右上角开始，即第一行的最后一个元素。
如果当前元素等于目标值，则返回 true。
如果当前元素大于目标值，则可以排除当前元素所在的列，将列索引向左移动。
如果当前元素小于目标值，则可以排除当前元素所在的行，将行索引向下移动。
重复步骤 2-4，直到找到目标值或者行索引或列索引超出矩阵范围。
这种方法的时间复杂度为 O(M + N)，其中 M 是行数，N 是列数，因为每次移动都可以排除一行或一列。
function find(target, matrix) {
let rows = matrix.length;
let cols = matrix[0].length;
let r = 0;
let c = cols - 1; // 从右上角开始
while (r <= rows - 1 && c >= 0) {
if (target === matrix[r][c]) {
return true;
} else if (target > matrix[r][c]) {//如果 target 大于 matrix[r][c]，则向下移动 r。
r++;
} else {//如果 target 小于 matrix[r][c]，则向左移动 c。
c--;
}
}
return false;
}快慢指针
移除数组中的指定元素
https://leetcode.cn/problems/remove-element/description/
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
示例 1：输入：nums = [3,2,2,3], val = 3 输出：2, nums = [2,2,_,_]
示例 2：输入：nums = [0,1,2,2,3,0,4,2], val = 2 输出：5, nums = [0,1,4,0,3,_,_,_]
解释： https://programmercarl.com/0027.移除元素.html
function removeElement(nums, val) {
let slow = 0,fast = 0,result = []
while (fast<nums.length){//跑得快的那个先去寻找共同目标
if(nums[fast] != val){
result[slow++] = nums[fast]; //如果找到了，就送给跑得慢的那个
}
fast++;//但是不管是否找得到，跑得快的那方都一直奔跑到生命的尽头
}
return [slow,result];
};
删除有序数组中的重复项
https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/
给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
示例 1：输入：nums = [1,1,2] 输出：2, nums = [1,2,_]
示例 2：输入：nums = [0,0,1,1,1,2,2,3,3,4] 输出：5, nums = [0,1,2,3,4]
请留意题目中的：非严格递增排列
function removeDuplicates (nums) {
let fast = 1, slow = 1;
while (fast < nums.length) {
if (nums[fast] !== nums[fast - 1]) {
nums[slow++] = nums[fast];
}
fast++;
}
return slow;
};分离双指针
两个数组的交集
https://leetcode.cn/problems/intersection-of-two-arrays/description/
给定两个数组 nums1 和 nums2 ，返回 它们的 交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
示例 1：输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4] 备注： [4,9] 也是可通过的
这是用hash做校验肯定是最快的O(mn)，但是我们也可以用排序 + 双指针来做（O(m㏒m+n㏒n)）。
function getIntersection(nums1, nums2) {
// 首先，对两个输入数组进行排序。排序是为了确保我们可以方便地比较两个数组中的元素。
nums1.sort((x, y) => x - y);
nums2.sort((x, y) => x - y);
const length1 = nums1.length, length2 = nums2.length;
// 使用两个指针分别指向两个数组的开头，然后逐步向后移动，根据元素大小关系决定哪个指针向前移动。
let index1 = 0, index2 = 0;
const intersection = [];
while (index1 < length1 && index2 < length2) {
const num1 = nums1[index1], num2 = nums2[index2];
if (num1 === num2) { // 说明找到了一个交集元素，将该元素添加到结果集,并同时递增 index1 、index2
// 保证加入元素的唯一性
if (!intersection.length || num1 !== intersection[intersection.length - 1]) {
intersection.push(num1);
}
index1++;
index2++;
} else if (num1 < num2) {//因为我们希望找到更大的元素。所以当num1 < num2，递增index1
index1++;
} else {
index2++;
}
}
return intersection;
}滑动窗口
滑动窗口和快慢指针都是在解决数组（或字符串）相关问题时常用的技巧，但它们的应用方式和解决问题的思路有一些不同。
滑动窗口（Sliding Window）：
定义：滑动窗口是指通过维护一个窗口（一般是数组或字符串的子区间），在这个窗口上通过移动左右边界来求解问题。
应用场景：通常用来解决需要找出数组或字符串中某种子串的最小值、最大值、符合条件的长度最短或最长等问题。
特点：滑动窗口的核心思想是利用双指针或者队列，通过滑动窗口的左右边界来扩展或收缩窗口，从而在窗口内查找符合条件的解。
快慢指针（Two Pointers - Fast and Slow）：
定义：快慢指针是指在解决链表或数组中某些问题时，使用两个指针以不同的步长移动，从而解决问题的一种方法。
应用场景：主要用来解决链表中的环路检测、寻找中间节点、判断链表是否相交等问题。
特点：快慢指针一般是在单链表中使用，快指针每次移动两步，慢指针每次移动一步，通过这种方式可以判断是否存在环路，或者找到链表的中间节点等。
区别：
问题类型：
滑动窗口主要用于数组或字符串相关问题
快慢指针更多地应用于链表相关问题。
移动方式：
滑动窗口通过移动窗口的左右边界来扩展或收缩窗口，
快慢指针则通过两个指针以不同的速度遍历链表来解决问题。
解决问题的思路：
滑动窗口通常用于解决子数组或子字符串相关的问题
快慢指针则更适合解决链表中的指针遍历问题。
滑动窗口的题目：
可获得的最大点数（1432）
别人总结好的：
可获得的最大点数
https://leetcode.cn/problems/maximum-points-you-can-obtain-from-cards/description/
几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。你的点数就是你拿到手中的所有卡牌的点数之和。给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。
示例 1：输入：cardPoints = [1,2,3,4,5,6,1], k = 3 输出：12
示例 2：输入：cardPoints = [2,2,2], k = 2 输出：4
不管怎么取，都是取头尾。比如我们可以假设一开始就是最左边的k个数字的和最大，之后滑动窗口，让窗口不停左滑动（每次滑动一个数字），并比较当前k个数字的和与上次的和谁更大。
直接暴力解法：
function maxScore(nums, k) {
// 因为不管怎么样，都是从首尾开始取，那么就是掐头去尾
let sum = 0;
const n = nums.length;
let selectFirst = k;
while (selectFirst >= 0) {
let temp = 0;
for (let i = 0; i < selectFirst; i++) {//首先取头部的k个，然后尝试头头部取的个数从尾部不足
temp += nums[i];
}
let selectLast = k - selectFirst;
while (selectLast > 0) {
temp += nums[n - selectLast];
selectLast--;
}
sum = Math.max(sum, temp);
selectFirst--;
}
return sum;
}
let cardPoints = [1, 2, 3, 4, 5, 6, 1], k = 3;
console.log(maxScore(cardPoints, 3));这样写，学滑动窗口还干啥子？
var maxScore = function (cardPoints, k) {
let windowSum = 0;
for (let i = 0; i < k; i++) {
windowSum += cardPoints[i];
};
let n = cardPoints.length - 1;
// sum等会要不断减少，会变化，所以要有个比较和大小的参照，我们也假设sum此时就是最大
let sum = windowSum;
while (k > 0) {
windowSum = windowSum - cardPoints[k - 1] + cardPoints[n];
sum = Math.max(windowSum, sum);
k--;
n--;
}
return sum;
};
原问题等价为：从 cardPoints 中找长度为 n - k 的连续段，使其总和最小。
var maxScore = function (cardPoints, k) {
const total = cardPoints.reduce((a, b) => a + b);
// 滑动窗口大小为 length - k
let windowSize = cardPoints.length - k, windowSum = 0;
// 选前 n-k 个作为初始值
for (let i = 0; i < windowSize; i++) {
windowSum += cardPoints[i];
}
let minSum = windowSum;
for (let i = windowSize; i < cardPoints.length; i++) {
// 滑动窗口每向右移动一格，增加从右侧进入窗口的元素值，并减少从左侧离开窗口的元素值
windowSum = windowSum + cardPoints[i] - cardPoints[i - windowSize];
minSum = Math.min(windowSum, minSum);
}
return total - minSum;
};上面是官方解法，但是还不如最上面的解法。这个是n+k。最上面的是2k
长度最小的子数组
https://leetcode.cn/problems/minimum-size-subarray-sum/description/
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：输入：target = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：输入：target = 4, nums = [1,4,4] 输出：1
示例 3：输入：target = 11, nums = [1,1,1,1,1,1,1,1] 输出：0
https://programmercarl.com/0209.长度最小的子数组.html
var minSubArrayLen = function (target, nums) {
let start = 0, end = 0;
let windowSum = 0, minLength = Infinity;
while (end < nums.length) {
windowSum = windowSum + nums[end];//窗口扩张：向右移动右指针，将新元素纳入窗口
while (windowSum >= target) {// 检查当前窗口是否满足条件
minLength = Math.min(minLength, end - start + 1);
windowSum = windowSum - nums[start];//窗口收缩：尝试缩短窗口，移除左侧元素，更新窗口和
start++;
// 若左侧指针已经越过右侧指针，跳出内层循环
if (start > end) {
break;
}
}
end++;
}
return Number.isFinite(minLength) ? minLength : 0;
};最长重复子数组
https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
示例 1：输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7] 输出：3 解释：长度最长的公共子数组是 [3,2,1] 。
示例 2：输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0] 输出：5
动态规划
动态规划是一种将复杂问题分解为若干个子问题，并存储子问题的解以避免重复计算的优化策略。对于“最长重复子数组”问题，
如果没有整明白，可以看这个：
function findLength(nums1, nums2) {
const [m, n] = [nums1.length, nums2.length];
let maxLen = 0;
const gird = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0)); // dp数组初始化，都初始化为0
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (nums1[i - 1] === nums2[j - 1]) { // 当前元素相等
gird[i][j] = gird[i - 1][j - 1] + 1; // 根据状态转移方程更新 dp 值
maxLen = Math.max(maxLen, gird[i][j]); // 更新最长子数组长度
}
}
}
return maxLen;
}以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。我就定义dp[i][j]为 以下标i为结尾的A，和以下标j 为结尾的B，最长重复子数组长度。不行么？当然可以，就是实现起来麻烦一些。
滚动数组
dp[i][j]都是由dp[i - 1][j - 1]推出。那么压缩为一维数组，也就是dp[j]都是由dp[j - 1]推出。也就是相当于可以把上一层dp[i - 1][j]拷贝到下一层dp[i][j]来继续用。此时遍历B数组的时候，就要从后向前遍历，这样避免重复覆盖。
const findLength = (nums1, nums2) => {
let len1 = nums1.length, len2 = nums2.length;
// dp[i][j]: 以nums1[i-1]、nums2[j-1]为结尾的最长公共子数组的长度
let dp = new Array(len2 + 1).fill(0);
let res = 0;
for (let i = 1; i <= len1; i++) {
for (let j = len2; j > 0; j--) {
if (nums1[i - 1] === nums2[j - 1]) {
dp[j] = dp[j - 1] + 1;
} else {
dp[j] = 0;
}
res = Math.max(res, dp[j]);
}
}
return res;
};这个在捋一下，用滑动窗口也是可以解的。
滑动窗口
这个滑动窗口的写法跟一般滑动窗口写法不太一样，一般滑动窗口只要移动指针就完事了，这个滑动窗口其实不应该看成滑动窗口，而应该去找规律。leetcode题解里面对这题虽然动图意思对的，但是顺序以及注意点都有强烈误导性，导致正常人看了动图压根写不出这种循环。所以我拿别人图将顺序和过程以及注意点改造了下：
var findLength = function (nums1, nums2) {
let result = 0;
const len1 = nums1.length, len2 = nums2.length;
const total = len1 + len2;
for (let i = 0; i < total; i++) {
let start1 = 0, start2 = 0, winowSize = 0;
if (i < len1) {
start1 = len1 - i - 1;// 其实就是先固定num1，所以先取num1从后往前取
start2 = 0;// 那么num2就是从前往后取
winowSize = i + 1;
} else {// 与上面相反
start1 = 0;
start2 = i - len1;
winowSize = Math.min(len2 - start2, len1);
}
const res = maxLength(nums1, nums2, start1, start2, winowSize);
result = Math.max(result, res);
}
return result;
};
function maxLength(num1, num2, start1, start2, windowSize) {
let count = 0, max = 0;
for (let i = 0; i < windowSize; i++) {
if (num1[start1 + i] === num2[start2 + i]) {
count++;
max = Math.max(count, max);
} else {
count = 0;
}
}
return max;
}其实这个写法看起来挺晕的，还不如官方代码简洁：
function findLength(num1, num2) {
let result = 0;
const len1 = num1.length;
const len2 = num2.length;
for (let start1 = 0; start1 < len1; start1++) {// 固定数组1
const windowSize = Math.min(len1 - start1, len2);
const res = maxLength(num1, num2, start1, 0, windowSize);
result = Math.max(result, res);
}
for (let start2 = 0; start2 < len2; start2++) { // 固定数组2
const windowSize = Math.min(len1, len2 - start2);
const res = maxLength(num1, num2, 0, start2, windowSize);
result = Math.max(result, res);
}
return result;
}
function maxLength(num1, num2, start1, start2, windowSize) {
let max = 0;
let count = 0;
for (let i = 0; i < windowSize; i++) {
if (num1[start1 + i] === num2[start2 + i]) {
count++;
max = Math.max(count, max);
} else {
count = 0;
}
}
return max;
}
字符串系列
回文字符串 题目很多，比如：
反转字符串（LeetCode 344）：给定一个字符串，判断其是否可以通过调整字符顺序来形成回文串。
最长回文子串（LeetCode 5）：给定一个字符串，找到其中最长的回文子串。
回文子串计数（LeetCode 647）：给定一个字符串，统计其中回文子串的数量。
分割回文串（LeetCode 131）：给定一个字符串，将其分割成若干个回文子串，返回所有可能的分割方案。
我们看最长回文字符串与 回文子串计数 都可以 分离双指针。
中心扩展法（分离双指针）
最长回文子串/回文子串计数
https://leetcode.cn/problems/longest-palindromic-substring/description/
其实就是分离双指针：遍历每一个字符，向两边扩展找到以其为中心的最长回文子串， 所有找到的回文子串的最大长度即所求 。
不过，以当前字符为中心的回文串的长度可能是奇数，也可能是偶数，两种情况都需要考察：
var longestPalindrome = function (s) {
if (typeof s !== 'string' || s.length < 1) return s;
let start = 0, end = 0;
for (let i = 0; i < s.length; i++) {
//奇数长： 以当前字符为中心向两边扩展,
const { left: left1, right: right1 } = expandAroundCenter(s, i, i);
//偶数长： 以当前字符和下一个字符的间隔为中心向两边扩展
const { left: left2, right: right2 } = expandAroundCenter(s, i, i + 1);
const len1 = right1 - left1 + 1;
const len2 = right2 - left2 + 1;
if (len1 > len2) {
if (end - start < len1) {
start = left1;
end = right1;
}
} else {
if (end - start < len2) {
start = left2;
end = right2;
}
}
}
// JavaScript 的 substring 函数截取子串，end + 1 是因为 substring 函数截取的结束位置是开区间
return s.substring(start, end + 1);
};
function expandAroundCenter(s, left, right) {// 找到以 left 和 right 为中心向两边扩展的最长回文子串长度
while (left >= 0 && right < s.length && s[left] === s[right]) {// 循环直到边界或不是回文串为止
left--;
right++;
}
return { left: left + 1, right: right - 1 };
}特别说明下：
const len1 = expandAroundCenter(s, i, i);：这里我们将当前字符s[i] 作为回文字符串的中心，即左右边界都是 i。这种情况下，回文字符串的长度为奇数。例如，对于字符串 "babad"，当 i = 2 时，s[i] 是字符 'a'，以 'a' 为中心的回文字符串有 "bab" 和 "aba"，其中最长的是 "bab"，长度为 3。
const len2 = expandAroundCenter(s, i, i + 1);：这里我们将当前字符 s[i] 和下一个字符 s[i + 1] 作为回文字符串的中心，即左边界是 i，右边界是 i + 1。这种情况下，回文字符串的长度为偶数。例如，对于字符串 "babad"，当 i = 1 时，s[i] 和 s[i + 1] 分别是字符 'a' 和 'b'，以 'a' 和 'b' 为中心的回文字符串有 "aba"，长度为 3。
也可以用动态规划来做……
分割回文字符串，必须得用回溯+动态规划，或者 回溯 + 记忆化搜索
回文字符串动态规划解法
可以参看《DP笔记(3)：二维线性DP问题：最长公共子序列/最长重复子数组》
转载本站文章《双指针：对撞/快慢/分离/滑动窗口的案例(数组/回文/求和等)》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/leetcode/9093.html