👉 1. 双指针概念:
从开发的角度来说,双指针
并非指的是一种具体的公式或者范式。而是一种运算思路,用于节省逻辑运算时间的逻辑思路
!双指针算法通常用于优化时间复杂度
!
双指针的时间复杂度为: O(n)
通常是指通过预设两个指针,限制两个指针不断按照指定逻辑进行单向移动,从而两个指针在移动过程中,通过指针运算出所需要得出的结果!
综上所述,双指针
只是一种思路。而针对某些应用场景,给大伙总结了一些通用范例。
左右指针
:创建两个指针(变量),一个指向开头,一个指向末尾,然后向中间遍历,直到满足条件或者两个指针相遇;快慢指针
:常见于链表查询中。创建两个指针,开始都指向开头,根据条件不同,快指针走得快,慢指针走的慢,直到满足条件或者快指针走到结尾;滑动窗口
:进行单调性的子串问题。创建两个指针,两个指针包裹的范围叫做窗口,然后通过移动指针,匹配窗口中的条件是否满足要求。
接下来,就以上三种范例,讲解案例!
👉 2. 左右指针
根据 左右指针
的概念,不难理解。小温曾经给大伙讲解的二分查找,也是涉及双指针这个概念的。二分查找中的二分,指的就是首尾两个指针,不断向中间靠拢,不断取二分之一
。以缩小查找范围,优化查找速度及时间复杂度!
忘记 二分查找 的小伙伴请 点击跳转回顾知识
> 案例一:二分查找
var search = function(nums, target) {
// 方法: 二分查找,代码
// 定义首尾两个指针
let left = 0, right = nums.length - 1
// 当指针并未重叠超出界限,则继续, 反之,中断!
while(left <= right) {
const mid = Math.floor((right + left) / 2) | Math.floor((right - left) / 2) + left
const curVal = nums[mid]
if(curVal === target) return mid
if(curVal > target) right = mid - 1 // 判断条件,移动指针
else left = mid + 1
}
return -1
};
> 案例二:双指针 - 移除元素
具体题目参考 leetCode 移除元素
var removeElement = function(nums, val) {
// 定义首尾双指针
let left = 0, right = nums.length
// 指针重叠即为结束
while(left < right) {
if(nums[left] === val) {
// 将以验证等于val值的坐标内容与未验证过的下标内容互换,基于题目要求,不需要理会k值后面的数据,相当于移除了符合条件的nums[left]值
nums[left] = nums[right - 1]
// 指针向前推移,逐步缩小查询范围
right--
} else {
// 反之,如不等于则首指标向后推移,前面即为已核实的唯一元素,记录left加一
left++
}
}
return left
};
👉 3. 快慢指针
快慢指针
常用于解决链表中的一些问题,定义两个指针,初始点一般为头/尾,分别为快慢指针。快指针先行,慢指针在后,用于判断指定条件情况下,才可移动慢指针。
> 案例一: 删除排序数组中的重复项
具体题目可前往 leetCode 查看 点击跳转
var removeDuplicates = function(nums) {
// 解法一: 双指针
if(!nums.length) return 0;
let i = 0, j = 0
for(let j = 0; j < nums.length; j++) {
if(nums[i] !== nums[j]) {
i++;
nums[i] = nums[j];
}
}
return i + 1
// 解法二: ES6,Set + splice
// let newArr = [...new Set(nums)]
// nums.splice(0, newArr.length, ...newArr)
// return newArr.length
};
通过快慢指针,不断判断将快指针下标指向的数据与慢指针下标中对应的数据交换。本质和左右指针差不多的原理,只不过实现的双指针走向不同而已。
👉 3. 滑动窗口
滑动窗口
,见名知意,就如同在前端网页中的可视窗口
的概念相似。
概念:通过两个指针指向的元素之间形成的一个窗口。然后我们滑动这个窗口进行数据比对,直到满足要求的数据为止。
而这个窗口分两种,一种是固定大小的窗口,另一种是大小动态变化的窗口。
> 应用场景:
- 一般给出的数据结构是数组或者字符串
- 求取某个子串或者子序列最长最短等最值问题或者求某个目标值时
- 该问题本身可以通过暴力求解
> 案例一: 删除有序数组中的重复项 II
具体题目可前往 leetCode 查看 点击跳转
var removeDuplicates = function(nums) {
const len = nums.length
if(len <= 2) return len
// 双指标
let slow = 2, fast = 2
while(fast < len) {
if(nums[slow - 2] !== nums[fast]) {
nums[slow] = nums[fast]
slow++
}
fast++
}
return slow
// 利用哈希原理,记录出现次数,暴力破解
// let objTime = nums.reduce((pre, cur) => {
// pre[cur] = pre[cur] ? pre[cur] + 1 : 1
// if(pre[cur] <= 2) {
// pre.newArr.push(cur)
// pre.sumTime += 1
// }
// return pre
// }, { sumTime: 0, newArr: [] })
// nums.splice(0, len, ...objTime.newArr)
// return objTime.sumTime
};
该题目为删除重复连续重复超出2个以上的内容,显而易见,这个滑动窗口的大小就为3。
且当在这个窗口中,首尾不相同的话,证明这个窗口中,并不存在超过2个以上相同的内容,故将slow指针前移。代码结束后,fast指针自行后移一位,始终保证窗口为固定大小
(3)
总结
通过上述的一系列理论配合案例,相信大伙对双指针概念应该也大概能理解! 双指针是一种基于定义两个指针,并且通过控制指针移动的逻辑,去运算出所需的内容的思路!希望大伙能学以致用,运用到实际项目中!