一、前言
学好算法的根基是：
刷题！刷题！刷题！
本文将深入探讨高频算法中的双指针、滑动窗口以及二叉树。题目均来源于https://leetcode.cn/。重点关注每种题目的解题思路和总结，通过详尽的解答，包括解答思路和每一步的代码实现，以帮助读者快速理解并掌握这些算法。
二、双指针
双指针解题总结：
- 数组+target题型，使用对撞指针
-> <- - 两个字符串、链表、数组之间的关系，使用快慢指针
-> ->
1、两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 ：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？
解题思路：
- 对原数组进行排序，这里使用
Array.from新建一个数组，为了不影响到原数组中数字的位置，为了之后的回溯查询准备。 - 指定两个指针left、right，这两个是碰撞指针，初始索引是数组最左和最右边的位置。
- 循环判断开始，当左指针在右指针的昨天时有效判断，根据左右指针的索引，找出数组中对应的数字，相间得到sum和，sum与target比较，如果相等，则返回左右索引对应的
原数组中的数字，注意这里是原数组，第一条时提到过了 - 如果不相等，
sum>target时，right–，右指针向左边移动一位，否则，left++，左指针向右边移动一位
注意：
// 3、回归原数组进行索引
return [nums.indexOf(a), nums.lastIndexOf(b)];
这里使用了indexOf和lastIndexOf，一个是从左到右，一个是从右到左
代码实现
let twoSum = (nums, target)=> {
// 1、排序
let sortNums = Array.from(nums).sort((a,b)=>a-b);
// 2、创建对撞指针
let left = 0,
right = nums.length-1;
while (left < right) {
let a = sortNums[left];
let b = sortNums[right];
let sum = a + b;
if (sum === target) {
// 3、回归原数组进行索引
return [nums.indexOf(a), nums.lastIndexOf(b)];
} else if (sum > target) {
right--
} else {
left++
}
}
}
2、最接近的三数之和
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
解题思路：
- 先对数组进行排序
- 设置最小值min为Infinity无限大，用来之后替换三数字和sum与target差，做比对用
- 循环判断开始，从左往右依次尝试定一个基础指针 右边至少再保留两位 否则无法凑成3个，
let i = 0; i <= nums.length - 3; i++ - 设置左右指针
let left = i + 1; // 左指针先从 i 右侧的第一位开始尝试 let right = n - 1 // 右指针先从数组最后一项开始尝试 - 循环内循环
while (left < right)判断，求三数字之和let sum = basic + nums[left] + nums[right] // 三数求和 - 更新最小差
// 更新最小差
let diff = Math.abs(sum - target)
if (diff < min) {
min = diff
res = sum
}
- 根据sum和target关系，左右移动左右指针
if (sum < target) {
// 求出的和如果小于目标值的话 可以尝试把左指针右移 扩大值
left++
} else if (sum > target) {
// 反之则右指针左移
right--
} else {
// 相等的话 差就为0 一定是答案
return sum
}
整体代码实现
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
let threeSumClosest = function (nums, target) {
let n = nums.length
if (n === 3) {
return getSum(nums)
}
// 先升序排序 此为解题的前置条件
nums.sort((a, b) => a - b)
let min = Infinity // 和 target 的最小差
let res
// 从左往右依次尝试定一个基础指针 右边至少再保留两位 否则无法凑成3个
for (let i = 0; i <= nums.length - 3; i++) {
let basic = nums[i]
let left = i + 1; // 左指针先从 i 右侧的第一位开始尝试
let right = n - 1 // 右指针先从数组最后一项开始尝试
while (left < right) {
let sum = basic + nums[left] + nums[right] // 三数求和
// 更新最小差
let diff = Math.abs(sum - target)
if (diff < min) {
min = diff
res = sum
}
if (sum < target) {
// 求出的和如果小于目标值的话 可以尝试把左指针右移 扩大值
left++
} else if (sum > target) {
// 反之则右指针左移
right--
} else {
// 相等的话 差就为0 一定是答案
return sum
}
}
}
return res
};
function getSum(nums) {
return nums.reduce((total, cur) => total + cur, 0)
}
3、判断子序列
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
示例 1:
s = "abc", t = "ahbgdc"
返回 true.
示例 2:
s = "axc", t = "ahbgdc"
返回 false.
解题思路：
- 判断字符串 s 是否是字符串 t 的子序列，我们可以建立一个 i 指针指向。之后开始遍历 t 字符串，每当在 t 中发现 i 指针指向的目标字符时，就可以把 i 往后前进一位。
- 一旦
i === t.length，就代表 t 中的字符串全部按顺序在 s 中找到了，返回 true。 - 当遍历 s 结束后，就返回 false，因为 i 此时并没有成功走 t 的最后一位。
代码实现
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
let isSubsequence = function (s, t) {
let sl = s.length
if (!sl) {
return true
}
let i = 0
for (let j = 0; j < t.length; j++) {
let target = s[i]
let cur = t[j]
if (cur === target) {
i++
if (i === sl) {
return true
}
}
}
return false
};
4、移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。必须在原数组上操作，不能拷贝额外的数组。尽量减少操作次数。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
解题思路：
- 慢指针 j 从 0 开始，当快指针 i 遍历到非 0 元素的时候，i 和 j 位置的元素交换,然后把 j + +。
- 也就是说，当遍历完后，非0数字都被替换到了前面
代码实现
var moveZeroes = function(nums) {
const n = nums.length;
let j = 0;
for (let i = 0; i < nums.length; i++) {
if (nums[i] !== 0) {
let temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
j++;
}
}
};
三、滑动窗口
滑动窗口也是双指针的一分支，由于比较有代表性，这里单独拿出来探讨。
1、滑动窗口的最大值
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
滑动窗口，每次左右各滑动一位，并且求窗口中的最大值记录即可，这题坑的地方在于边界情况比较多。
let maxSlidingWindow = function (nums, k) {
if (k === 0 || !nums.length) {
return []
}
let left = 0
let right = k - 1
let res = [findMax(nums, left, right)]
while (right < nums.length - 1) {
right++
left++
res.push(findMax(nums, left, right))
}
return res
}
function findMax(nums, left, right) {
let max = -Infinity
for (let i = left; i <= right; i++) {
max = Math.max(max, nums[i])
}
return max
}
四、二叉树
1、给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
class TreeNode {
constructor(val) {
this.val = val;
this.left = this.right = null;
}
}
function lowestCommonAncestor(root, p, q) {
// 如果当前节点为 null，直接返回 null
if (!root) return null;
// 如果当前节点等于 p 或 q，直接返回当前节点
if (root === p || root === q) return root;
// 递归在左子树中寻找 p 和 q 的最近公共祖先
const left = lowestCommonAncestor(root.left, p, q);
// 递归在右子树中寻找 p 和 q 的最近公共祖先
const right = lowestCommonAncestor(root.right, p, q);
// 如果左子树中没找到，说明最近公共祖先在右子树中
if (!left) return right;
// 如果右子树中没找到，说明最近公共祖先在左子树中
if (!right) return left;
// 如果左右子树都找到了，说明当前节点就是最近公共祖先
return root;
}
解题思路：
-
首先定义了一个二叉树节点的类
TreeNode，包含一个值val和左右子节点的引用left和right。 -
lowestCommonAncestor函数是用于寻找两个指定节点的最近公共祖先的主要函数。 -
首先检查当前节点
root是否为null，如果是，则直接返回null，因为空节点不可能是公共祖先。 -
接着检查当前节点
root是否等于p或q，如果是，则直接返回当前节点，因为如果当前节点就是其中一个指定节点，那么它自己就是最近公共祖先（在往上就没有更近的了）。 -
然后递归地在左子树中寻找
p和q的最近公共祖先，将结果保存在left变量中。 -
再递归地在右子树中寻找
p和q的最近公共祖先，将结果保存在right变量中。 -
如果
left为null，说明在左子树中没有找到p和q的公共祖先，那么最近公共祖先就在右子树中，所以返回right。 -
如果
right为null，说明在右子树中没有找到p和q的公共祖先，那么最近公共祖先就在左子树中，所以返回left。 -
如果
left和right都不为null，说明p和q分别在当前节点的左右子树中，那么当前节点就是它们的最近公共祖先，所以返回root。
以下是一个使用示例：
// 创建二叉树
const tree = new TreeNode(3);
tree.left = new TreeNode(5);
tree.right = new TreeNode(1);
tree.left.left = new TreeNode(6);
tree.left.right = new TreeNode(2);
tree.right.left = new TreeNode(0);
tree.right.right = new TreeNode(8);
tree.left.right.left = new TreeNode(7);
tree.left.right.right = new TreeNode(4);
// 定义节点 p 和 q
const p = tree.left;
const q = tree.left.right.right;
// 调用函数寻找最近公共祖先
const lca = lowestCommonAncestor(tree, p, q);
console.log(lca.val); // 5
在这个示例中，首先创建了一个二叉树，然后定义了两个节点 p 和 q，最后调用 lowestCommonAncestor 函数找到它们的最近公共祖先，并打印出该祖先节点的值。