前端算法之双指针

2023-12-30 05:16:14

双指针

双指针是一种编程技术,通常用于解决数组或链表的问题。

双指针法使用两个指针(通常称为快指针和慢指针)来遍历数据结构,以解决一些需要找到特定元素或进行其他复杂操作的问题。

双指针法的主要优点是它可以在一次遍历中解决问题,而不需要反向遍历或使用其他额外的数据结构。

这使得它在解决一些问题时效率更高。

例如: 在一个数组中查找两个数之和等于一个特定值,我们可以使用双指针法。

  • 首先,我们可以将一个指针放在数组的开头,另一个指针放在数组的末尾。

  • 然后,我们可以将两个指针向中间移动,比较它们所指向的元素之和与目标值的大小关系。

    • 如果和大于目标值,我们将慢指针向内移动;
    • 如果和小于目标值,我们将快指针向外移动;
    • 如果和等于目标值,我们就找到了这两个元素。

请注意,双指针法并不总是适用于所有问题,它的使用取决于问题的具体性质和要求。

在使用双指针法时,确保理解清楚问题的要求以及指针移动的条件,以避免错误的结果或出现死循环。

分类

快慢指针(同向)

–> --> 快慢指针

a -> b -> c -> d -> a 如何判断是一个环

对向、背向指针

更多详细内容,请微信搜索“前端爱好者戳我 查看

例子:最接近的三数之和

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数,使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例 1:

输入:nums = [-1,2,1,-4], target = 1
输出:2
解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

示例 2:

输入:nums = [0,0,0], target = 1
输出:0

地址:https://leetcode.cn/problems/3sum-closest/

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function(nums, target) {
  // 1. 先排序
  // target - for 循环的数
  // -> <-
  let length = nums.length
  let res = Number.MAX_SAFE_INTEGER // 取无穷大数
  nums.sort((a,b) => a -b)

  for(let i = 0; i < length; i ++ ){ // 复杂度:n+1
    // 依次获取其中元素
    // nums [i] + nums [a] + nums [b] = target  其中 nums [i] 确定;nums [a] + nums [b] 不确定
    // nums [i] + nums [i + 1] + nums [length - 1] = target

    let left = i + 1 // 复杂度:n
    let right = length - 1 // 复杂度:n

    // 两数之和判断

    while(left < right) { // 复杂度:n
      let sum = nums[i] + nums[left] + nums[right]

      if(Math.abs(sum - target) < Math.abs(res - target)){
        res = sum
      }

      if(sum < target){
        left ++ 
      } else if(sum > target){
        right --
      } else {
        return sum
      }
    }
  }

  return res 
};

例子:通过删除字母匹配到字典里最长单词

给你一个字符串 s 和一个字符串数组 dictionary ,找出并返回 dictionary 中最长的字符串,该字符串可以通过删除 s 中的某些字符得到。

如果答案不止一个,返回长度最长且字母序最小的字符串。如果答案不存在,则返回空字符串。

示例 1:

输入:s = “abpcplea”, dictionary = [“ale”,“apple”,“monkey”,“plea”]
输出:“apple”

示例 2:

输入:s = “abpcplea”, dictionary = [“a”,“b”,“c”]

输出:“a”

提示:

  • 1 <= s.length <= 1000
  • 1 <= dictionary.length <= 1000
  • 1 <= dictionary[i].length <= 1000
  • s 和 dictionary[i] 仅由小写英文字母组成
/**
 * @param {string} s
 * @param {string[]} dictionary
 * @return {string}
 */
var findLongestWord = function(s, dictionary) {
    let left = 0
    let right = 0
    let str = ''

    for(let i = 0; i < dictionary.length ; i ++ ){
        left = 0
        right = 0

        while(left < s.length && right < dictionary[i].length){
            if(s.charAt(left) === dictionary[i].charAt(right)){
                right ++
            }
            // 当此时长度一样
            if(right === dictionary[i].length){
                // 拿着dictionary[i]的长度 跟已有的之前的str的结果长度比较
                if(dictionary[i].length > str.length || (dictionary[i].length === str.length && dictionary[i] < str)){
                    str = dictionary[i]
                }
            }

            left ++;
        } 
    }

    return str
};

文章来源:https://blog.csdn.net/BradenHan/article/details/135258442
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。