< 每日算法:一文带你认识 “ 双指针算法 ” >

简介: `双指针`并非指的是一种具体的公式或者范式。而是一种运算思路,用于节省逻辑运算时间的`逻辑思路`!双指针算法通常用于`优化时间复杂度`!

image.png

👉 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
};

image.png

通过快慢指针,不断判断将快指针下标指向的数据与慢指针下标中对应的数据交换。本质和左右指针差不多的原理,只不过实现的双指针走向不同而已。

👉 3. 滑动窗口

滑动窗口 ,见名知意,就如同在前端网页中的可视窗口的概念相似。

概念:通过两个指针指向的元素之间形成的一个窗口。然后我们滑动这个窗口进行数据比对,直到满足要求的数据为止。

而这个窗口分两种,一种是固定大小的窗口,另一种是大小动态变化的窗口。

> 应用场景:

  1. 一般给出的数据结构是数组或者字符串
  2. 求取某个子串或者子序列最长最短等最值问题或者求某个目标值时
  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)

总结

通过上述的一系列理论配合案例,相信大伙对双指针概念应该也大概能理解! 双指针是一种基于定义两个指针,并且通过控制指针移动的逻辑,去运算出所需的内容的思路!希望大伙能学以致用,运用到实际项目中!


往期内容 💨

🔥 < CSS小技巧:filter滤镜妙用>

🔥 < JavaScript技术分享: 大文件切片上传 及 断点续传思路 >

🔥 < 每日技巧: JavaScript代码优化 >

🔥 < 每日知识点:关于Javascript 精进小妙招 ( Js技巧 ) >

相关文章
|
5月前
|
算法
双指针算法
双指针算法
31 2
|
2月前
|
算法 索引 容器
双指针算法详解
本文介绍了双指针算法及其应用。双指针算法是在数组或字符串中常用的高效技术,通过维护两个指针遍历数据结构以解决特定问题。根据指针移动方向,可分为同向双指针、相向双指针和快慢指针。同向双指针如移动零和复写零问题;快慢指针如快乐数问题;相向双指针如盛水最多的容器、有效三角形数量及多数之和等问题。通过合理运用双指针技巧,可简化代码并提高效率。
60 4
双指针算法详解
|
5月前
|
机器学习/深度学习 搜索推荐 算法
【再识C进阶2(下)】详细介绍指针的进阶——利用冒泡排序算法模拟实现qsort函数,以及一下习题和指针笔试题
【再识C进阶2(下)】详细介绍指针的进阶——利用冒泡排序算法模拟实现qsort函数,以及一下习题和指针笔试题
|
1月前
|
算法 C++
【算法】双指针+二分(C/C++
【算法】双指针+二分(C/C++
|
3月前
|
算法 容器
【算法】双指针
【算法】双指针
|
3月前
|
算法 C++ 容器
【C++算法】双指针
【C++算法】双指针
|
6月前
|
算法
【优选算法】——双指针——15. 三数之和
【优选算法】——双指针——15. 三数之和
【优选算法】——双指针——15. 三数之和
|
6月前
|
存储 人工智能 算法
c++算法学习笔记 (9) 双指针
c++算法学习笔记 (9) 双指针
|
6月前
|
算法
[优选算法]——双指针——Leetcode——1089. 复写零
[优选算法]——双指针——Leetcode——1089. 复写零