精华内容
下载资源
问答
  • 对撞指针

    2021-05-11 16:15:28
    对撞指针 对撞指针是双指针的一种。对撞指针是指在有序数组中,将指向最左侧的索引定义为左指针(left),最右侧的定义为右指针(right),然后从两头向中间进行数组遍历。对撞数组适用于有序数组,也就是说当你遇到题目...

    对撞指针
    对撞指针是双指针的一种。对撞指针是指在有序数组中,将指向最左侧的索引定义为左指针(left),最右侧的定义为右指针(right),然后从两头向中间进行数组遍历。对撞数组适用于有序数组,也就是说当你遇到题目给定有序数组时,应该第一时间想到用对撞指针解题。

    给定一个已按照 升序排列 的整数数组 numbers ,请你从数组中找出两个数满足相加之和等于目标数 target 。
    函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ,所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。
    你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。

    class Solution {
        public int[] twoSum(int[] numbers, int target) {
            int low = 0, high = numbers.length - 1;
            while (low < high) {
                int sum = numbers[low] + numbers[high];
                if (sum == target) {
                    return new int[]{low + 1, high + 1};
                } else if (sum < target) {
                    ++low;
                } else {
                    --high;
                }
            }
            return new int[]{-1, -1};
        }
    }
    
    展开全文
  • 什么是对撞指针? 初识 算法图 对撞过程图 JavaScript中的Array与对撞指针 在js中,如何定义对撞指针? 实现一个最简对撞指针 leetcode 对撞指针 解法题目 7.整数反转(easy) 9.回文数(easy) 27.移除元素...

    在这里插入图片描述

    • 什么是对撞指针?
      • 初识
      • 算法图
      • 对撞过程图
    • JavaScript中的Array与对撞指针
      • 在js中,如何定义对撞指针?
      • 实现一个最简对撞指针
    • leetcode 对撞指针 解法题目
      • 7.整数反转(easy)
      • 9.回文数(easy)
      • 27.移除元素(easy)
      • 125.验证回文串(easy)
      • 167.两数之II-输入有序数组(easy)
      • 190.颠倒二进制位(easy)
      • 344.反转字符串(easy)
      • 345.反转字符串中的元音字母(easy)
      • 11.盛水最多的容器(medium)

    什么是对撞指针?

    初识

    • 对撞指针是双指针算法之一。
    • 对撞指针从两端向中间迭代数组。一个指针从始端开始,另一个从末端开始。
    • 对撞指针的终止条件是两个指针相遇。
    • 对撞指针常用于排序数组。

    算法图

    image

    对撞过程图

    167.两数之II-输入有序数组(easy)的对撞过程图。
    蓝色指针:头指针 红色指针:尾指针 终止条件:头尾指针对撞

    JavaScript中的Array与对撞指针

    在js中,如何定义对撞指针?

    命名

    头尾指针的命名可以为:

    • i, j
    • head, tail
    • start, end
    初始值
    • 头指针:0
    • 尾指针:数组长度减一
    let arr = [1, 7, 5, 2];
    let head = 0;
    let tail = arr.length -1;
    

    实现一个最简对撞指针

    image

    var arr = new Array(10).fill(0).map((num,i)=>num+i);
    var i =0;
    var j = arr.length - 1;
    while(i<j){
      i++;
      j--;
    }
    var collision = [i - 1, j + 1]
    var tip = `Array's head and tail had a collision between ${collision[0]} and ${collision[1]}`;
    console.log(tip); // Array's head and tail had a collision between 4 and 5
    

    leetcode 对撞指针 解法题目

    • 7.整数反转(easy)
    • 9.回文数(easy)
    • 27.移除元素(easy)
    • 125.验证回文串(easy)
    • 167.两数之II-输入有序数组(easy)
    • 190.颠倒二进制位(easy)
    • 344.反转字符串(easy)
    • 345.反转字符串中的元音字母(easy)
    • 11.盛水最多的容器(medium)

    7.整数反转(easy)

    题目:https://leetcode-cn.com/problems/reverse-integer/
    题解:https://github.com/FrankKai/leetcode-js/blob/master/7.Reverse_Integer.js

    var reverse = function (x) {
      /**
       * 解法2.指针对撞法
       * 性能:96 ms 35.38% 35.9 MB 77.35%
       */
      var sign = Math.sign(x);
      var arr = x.toString().split("");
      //
      if (sign === -1) {
        arr.shift();
      }
      // 指针对撞开始
      var i = 0;
      var j = arr.length - 1;
      while (i < j) {
        swap(arr, i, j);
        i++;
        j--;
      }
      function swap(arr, i, j) {
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
      // 指针对撞结束
      var rX = parseInt(arr.join(""));
      var result = sign * rX;
      var min = -Math.pow(2, 31);
      var max = Math.pow(2, 31) - 1;
      if (rX < min || rX > max) return 0;
      return result;
    };
    

    9.回文数(easy)

    题目:https://leetcode-cn.com/problems/palindrome-number/
    题解:https://github.com/FrankKai/leetcode-js/blob/master/9.Palindrome_Number.js

    var isPalindrome = function (x) {
      /**
       * 解法3:对撞指针法
       * 性能:244ms 45.5MB
       */
      var strArr = `${x}`.split("");
      var i = 0;
      var j = strArr.length - 1;
      while (i < j) {
        if (strArr[i] !== strArr[j]) {
          return false;
        }
        i++;
        j--;
      }
      return true;
    };
    

    27.移除元素(easy)

    题目:https://leetcode-cn.com/problems/remove-element/
    题解:https://github.com/FrankKai/leetcode-js/blob/master/27.Remove_Element.js

    var removeElement = function (nums, val) {
      /**
       * 解法2:对撞指针
       * 性能:64ms 33.9MB
       */
      var i = 0;
      var j = nums.length - 1;
      while (i <= j) {
        if (nums[i] === val) {
          nums.splice(i, 1);
          j--;
        } else if (nums[j] === val) {
          nums.splice(j, 1);
          j--;
        } else {
          i++;
        }
      }
      return nums.length;
    };
    

    125.验证回文串(easy)

    题目:https://leetcode-cn.com/problems/valid-palindrome/
    题解:https://github.com/FrankKai/leetcode-js/blob/master/125.Valid_Palindrome.js

    var isPalindrome = function (s) {
      /**
       * 解法1:正则 + 对撞指针
       * 性能:76ms 89.76% 37.5MB 70.83%
       */
      var parlinDrome = s.replace(/[^\w]/g, "").replace(/_/g, "").toLowerCase();
      var strArr = parlinDrome.split("");
      var i = 0;
      var j = strArr.length - 1;
      while (i < j) {
        if (strArr[i] !== strArr[j]) {
          return false;
        }
        i++;
        j--;
      }
      return true;
    };
    

    167.两数之II-输入有序数组(easy)

    题目:https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
    题解:https://github.com/FrankKai/leetcode-js/blob/master/167.Two_Sum_II-Input_array_is_sorted.js

    var twoSum = function (numbers, target) {
      /**
       * 解法2:对撞指针
       * 性能:68ms 71.18% 35.2MB 76.60%
       * 时间复杂度:O(n^2)
       */
      var left = 0;
      var right = numbers.length - 1;
      while (left < right) {
        if (numbers[left] + numbers[right] === target) {
          return [left + 1, right + 1];
        } else if (numbers[left] + numbers[right] > target) {
          right--;
        } else {
          left++;
        }
      }
    };
    

    190.颠倒二进制位(easy)

    题目:https://leetcode-cn.com/problems/reverse-bits/
    题解:https://github.com/FrankKai/leetcode-js/blob/master/190.Reverse_Bits.js

    /**
     * @param {number} n - a positive integer
     * @return {number} - a positive integer
     */
    var reverseBits = function (n) {
      /**
       * 解法1:转数组后对撞交换位置
       * 性能:76ms 35.8MB
       * 思路:
       * 十进制转二进制:toString(2)
       * 32位空位补0:padStart(32,0)
       * 反转算法:对撞指针法
       * 二进制转十进制:parseInt(,2)
       */
      let arr = n.toString(2).padStart(32, 0).split("");
      let head = 0;
      let tail = arr.length - 1;
      while (head < tail) {
        swap(arr, head, tail);
        head++;
        tail--;
      }
      function swap(arr, i, j) {
        let temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
      let result = parseInt(arr.join(""), 2);
      return result;
    };
    

    344.反转字符串(easy)

    题目:https://leetcode-cn.com/problems/reverse-string/
    题解:https://github.com/FrankKai/leetcode-js/blob/master/344.Reverse_String.js

    var reverseString = function (s) {
      /**
       * 解法2:对撞指针
       */
      var headIdx = 0;
      var tailIdx = s.length - 1;
      while (headIdx < tailIdx) {
        swap(s, headIdx, tailIdx);
        headIdx++;
        tailIdx--;
      }
      function swap(arr, i, j) {
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
      return s;
    };
    

    345.反转字符串中的元音字母(easy)

    题目:https://leetcode-cn.com/problems/reverse-vowels-of-a-string/
    题解:https://github.com/FrankKai/leetcode-js/blob/master/345.Reverse_Vowels_of_a_String.js

    /**
     * @param {string} s
     * @return {string}
     */
    var reverseVowels = function (s) {
      /**
       * 解法1:对撞指针
       * 性能:108 ms 31.59% 38.4 MB 66.67%
       */
      var univocalic = ["a", "e", "i", "o", "u", "A", "E", "I", "O", "U"];
      var sArr = s.split("");
      var head = 0;
      var tail = sArr.length - 1;
      while (head < tail) {
        if (univocalic.includes(sArr[head]) && univocalic.includes(sArr[tail])) {
          swap(sArr, head, tail);
          head++;
          tail--;
        } else if (!univocalic.includes(sArr[head])) {
          head++;
        } else if (!univocalic.includes(sArr[tail])) {
          tail--;
        }
      }
      function swap(arr, i, j) {
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
      return sArr.join("");
    };
    

    11.盛水最多的容器(medium)

    题目:https://leetcode-cn.com/problems/container-with-most-water/
    题解:https://github.com/FrankKai/leetcode-js/blob/master/11.Container_With_Most_Water.js

    var maxArea = function (height) {
      /**
       * 解法1:对撞指针法
       * 性能:64ms 35.6MB
       * */
      var head = 0;
      var tail = height.length - 1;
      var maxCapacity = 0;
      while (head < tail) {
          maxCapacity = Math.max(Math.min(height[head], height[tail]) * (tail - head), maxCapacity)
          if (height[head] < height[tail]) {
              head++
          } else {
              tail--;
          }
      }
      return maxCapacity;
    };
    

    期待和大家交流,共同进步,欢迎大家加入我创建的与前端开发密切相关的技术讨论小组:

    努力成为优秀前端工程师!

    展开全文
  • 双指针算法引言1、对撞指针2、快慢指针3、滑动窗口 引言 什么是双指针? \quad \quad严格的来说,双指针只能说是是算法中的一种技巧。双指针指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两...

    引言

    什么是双指针

    \quad \quad 严格的来说,双指针只能说是是算法中的一种技巧。双指针指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两个相同方向(快慢指针)或者相反方向(对撞指针)的指针进行扫描,从而达到相应的目的。

    \quad \quad 双指针算法在一些数组题中很常用,双指针算法有两种形式,一种被称为对撞指针,两个指针从两端向中间靠拢;另一种是快慢指针,两个指针向统一方向运动,滑动窗口方法就是一种常用的快慢指针方法。

    • 快慢指针:主要是成环问题
    • 对撞指针:数组和字符串问题
    • 滑动窗口:主要是子串问题

    双指针问题套路

    \quad \quad 通俗的说,就是在数组遍历中,我们使用两个指针进行操作。所以双指针问题基本有以下几个细节:

    1、双指针的初始位置。

    2、双指针的移动方法。

    3、遍历的结束条件。

    1、对撞指针

    见解

    \quad \quad 对撞指针是双指针的一种。对撞指针是指在有序数组中,将指向最左侧的索引定义为左指针(left),最右侧的定义为右指针(right),然后从两头向中间进行数组遍历。对撞数组适用于有序数组,也就是说当你遇到题目给定有序数组时,应该第一时间想到用对撞指针解题。

    可解决问题类型

    \quad \quad 对撞指针算法,可以用来解决有序数组中的数字之和,反转数组等之类的具有可以两边开工的一些问题。

    求解的步骤与模板

    \quad \quad 我们假设数组名字为 nums,数组长度为 n,数组首元素对应的位置为 0。

    代码细节
    (1)指针初始位置

    • 左指针(left)一般指向数组的第一个元素。即 left = 0。

    • 右指针(right)一般指向数组的最后一个元素。即 right = len-1。

    (2)指针移动方法

    • 左指针(left)向右边👉移动,一般每次移动一个位置,即 left++。

    • 右指针(right)向左边👈移动,一般每次移动一个位置,即 right–。

    (3)结束条件

    • 左指针(left)位置和右指针(right)位置逆序即right < left。

    例题

    2、快慢指针

    见解

    \quad \quad 快慢指针是两个指针从同一侧开始遍历数组,将这两个指针分别定义为快指针(fast)和慢指针(slow),两个指针以不同的策略移动,直到两个指针的值相等(或其他特殊条件)为止,如快指针(fast)每次增长两个,慢指针(slow)每次增长一个。

    • 这种算法的两个指针的在数组上(或是链表上,序列上)的移动速度不一样。
    • 通过控制指针不同的移动速度(比如在环形链表上),这种算法证明了他们肯定会相遇的。快的一个指针肯定会追上慢的一个。
      在这里插入图片描述

    可解决问题类型

    • 移除元素,删除元素之类的。
    • 判定链表中是否含有环
    • 已知链表中含有环,返回这个环的起始位置
    • 寻找链表的中点
    • 寻找链表的倒数第 k 个元素

    求解的步骤与模板

    (1)指针初始位置

    • 慢指针(slow)一般指向数组的第一个元素。即 slow = 0。

    • 快指针(fast)一般指向数组的第一个元素。即 fast = 1。

    (2)指针移动方法

    • 慢指针(slow)向右边👉移动,一般每次移动一个位置,即 slow++。(移动步长根据具体题目具体分析)

    • 快指针(fast)向右边👉移动,一般每次移动两个个位置,即 fast += 2。

    (3)结束条件

    • 慢指针(slow)位置和快指针(fast)位置重合;或快指针(fast)达到数组的最后一个元素。

    例题

    3、滑动窗口

    见解

    \quad \quad 滑动窗口算法的本质是双指针法中的快慢指针法,滑动窗口算法是双指针法中的快慢指针法更为形象的一种表达方式。它可以将嵌套的循环问题,更高效的解决。是一种优化算法。

    • 滑动窗口是数组/字符串/链表问题(输入是一些线性结构)中常用的抽象概念。
    • 窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合,即 [i, j](左闭,右闭)。
    • 滑动窗口是可以将两个边界向某一方向“滑动”的窗口。

    在这里插入图片描述
    例如,我们将 [i, j]向右滑动 1个元素,则它将变为 [i+1, j+1]。

    基本思想与原理

    \quad \quad 滑动窗口算法,可以将双层嵌套的循环问题,转换为单层遍历的循环问题。使用两个指针一左一右构成一个窗口,就可以将二维循环的问题转化成一维循环一次遍历,相当于通过旧有的计算结果对搜索空间进行剪枝,使时间复杂度从 O ( n 2 ) O(n^2) O(n2)降低至 O ( n ) O(n) O(n)

    可解决问题类型

    \quad \quad 滑动窗口算法可以用以解决数组字符串的子元素、字串问题。比如可以用来解决一些查找满足一定条件的连续区间的性质(长度、区间和等)的问题。往往类似于“请找到满足xx的最x的区间(子串、子数组等)的xx”这类问题都可以使用该方法进行解决。

    求解的步骤与模板

    \quad \quad 滑动窗口算法的解题步骤是这样(以在字符串S中,找最小的子元素使之包含字符串T为例):

    (1)指针初始位置即初始化窗口

    • 初始化 left =0, right = -1,把索引闭区间 [left, right] 称为一个「窗口」。

    (2)指针移动方法——寻找可行解并优化可行解:

    • 我们先不断地增加 right 指针扩张窗口 [left, right],直到窗口中的字符串符合要求(包含了 T 中的所有字符),找到可行解。
    • 此时,我们停止增加 right,转而不断增加 left 指针缩小窗口 [left, right],直到窗口中的字符串不再符合要求(不包含 T 中的所有字符了)。同时,每次增加 left,我们都要更新一轮结果。

    (3)滑动窗口,直至一次遍历结束:

    • 重复第 2 3 步,直到 right 到达字符串 S 的尽头。

    这个思路其实也不难理解,第 2 步中的第一扩张窗口相当于在寻找一个「可行解」,找到了就不再扩张;然后第二收缩窗口在优化这个「可行解」,直到条件被破坏,最终找到最优解。左右指针轮流前进,窗口大小增增减减,窗口不断向右滑动。

    也就是说主要有以下三步:

    • 扩张窗口:为了找到一个可行解,
    • 收缩窗口:在长度上优化该可行解,直到条件被破坏
    • 寻找下一个可行解,然后再优化到不能优化……

    以上思路是比较形象的滑动窗口问题的解题步骤,这类题通常要寻找比较具体的窗口。因为滑动窗口算法是双指针法中的快慢指针法更为形象的一种表达方式,因此有的双指针法中的快慢指针法问题所求解比较抽象,没有具体的窗口,这就要求我们结合实际题目做出分析。

    例题

    展开全文
  • 双指针问题概念双指针问题对撞指针快慢指针滑动窗口 概念 双指针是在遍历的过程中,使用两个方向相同或相反的指针进行扫描,从而达到相应目的的算法。 双指针充分使用了数组有序的特征,在特定情况下简化运算。 双...

    双指针问题(一) 对撞指针和快慢指针

    概念

    双指针是在遍历的过程中,使用两个方向相同或相反的指针进行扫描,从而达到相应目的的算法。

    广义上来说,双指针是指用两个变量在线性结构上遍历而解决的问题。

    狭义上说:

    • 对于数组,指两个变量在数组上相向移动解决的问题;
    • 对于链表,指两个变量在链表上同向移动解决的问题,也称为「快慢指针」问题。

    双指针问题

    对撞指针

    对撞指针将最左侧的索引定义为左指针(left),最右侧的定义为右指针(right),从两头向中间进行数组遍历

    对撞指针适用于有序的数组和字符串

    对撞指针的时间复杂度为 O ( n ) O(n) O(n)

    剑指 Offer 21

    此题要求分奇偶调整数组的顺序,我们可以用左指针寻找奇数,右指针寻找偶数,当左指针找到偶数且右指针找到奇数时,对调两数。代码如下

    vector<int> exchange(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            while(l < r && nums[l] % 2 == 1) l++;
            while(l < r && nums[r] % 2 == 0) r--;
            swap(nums[l], nums[r]);
        }
        return nums;
    }
    

    剑指 Offer 57

    此题要求寻找和为 t a r g e t target target数对,由于此题数组已经做好排序,我们可以确定

    若数对 ( n u m s [ i + 1 ] , n u m s [ j ] ) < t a r g e t (nums[i+1],nums[j])<target (nums[i+1],nums[j])<target

    则必有 ( n u m s [ i ] , n u m s [ j ] ) < t a r g e t (nums[i],nums[j])<target (nums[i],nums[j])<target

    同理,若数对 ( n u m s [ i ] , n u m s [ j ] ) > t a r g e t (nums[i],nums[j])>target (nums[i],nums[j])>target

    ( n u m s [ i + 1 ] , n u m s [ j ] ) > t a r g e t (nums[i+1],nums[j])>target (nums[i+1],nums[j])>target

    因此这道题也可以用对撞指针求解,当 n u m s [ l ] + n u m s [ r ] < t a r g e t nums[l]+nums[r]<target nums[l]+nums[r]<target时, l l l向右移动,反之, n u m s [ l ] + n u m s [ r ] > t a r g e t nums[l]+nums[r]>target nums[l]+nums[r]>target时,r向左移动,代码如下

    vector<int> twoSum(vector<int>& nums, int target) {
        int l=0, r = nums.size()-1;
        vector<int> ans;
        while(l<r) {
            while(l<r&&nums[l]+nums[r]<target) l++;
            while(l<r&&nums[l]+nums[r]>target) r--;
            if(nums[l]+nums[r]==target){
                ans.push_back(nums[l]);
                ans.push_back(nums[r]);
                return ans;
            }
        }
        return ans;
    }
    

    快慢指针

    快慢指针在序列中定义了一对不同速度的指针,以进行单向序列问题的求解。

    快慢指针的时间复杂度为 O ( n ) O(n) O(n),空间复杂度为 O ( 1 ) O(1) O(1)

    141. 环形链表

    此题要判断链表是否有环,可以定义一个快指针和一个慢指针,随后进行移动,若快指针可以追上慢指针,则表示链表一定有环,代码如下

    bool hasCycle(ListNode *head) {
        ListNode *p1 = head, *p2 = head;
        do {
            if (p1 && p2 && p2->next) {
                p1 = p1->next;
                p2 = p2->next->next;
            }
            else return false;
        } while(p1 != p2);
        return true;
    }
    

    142. 环形链表 II

    此题需要在求出是否成环的同时找到入环的第一个节点,我们可以根据快指针速度始终是慢指针的两倍这一条件进行推理

    在这里插入图片描述
    假设快慢指针在 b c bc bc交点相遇,此时慢指针走的距离应该是 a + b a+b a+b,而快指针已经走了 a + b + k ( b + c ) a+b+k(b+c) a+b+k(b+c)
    又有快指针的速度是慢指针的两倍,因此

    a + b + k ( b + c ) = 2 ( a + b ) a+b+k(b+c)=2(a+b) a+b+k(b+c)=2(a+b)

    a = k ( b + c ) − b = ( k − 1 ) ( b + c ) + c a=k(b+c)-b=(k-1)(b+c)+c a=k(b+c)b=(k1)(b+c)+c

    因此,当快慢指针相遇时,相遇点距离入环节点的距离总是 a a a,因此我们可以再用一个指针 c u r cur cur寻找入环节点,同时更新 c u r cur cur和慢指针,当二者相遇时,相遇节点即入环节点。代码如下

    ListNode *detectCycle(ListNode *head) {
        ListNode *p1 = head, *p2 = head;
        do {
            if (p1 && p2 && p2->next) {
                p1 = p1->next;
                p2 = p2->next->next;
            } else return NULL;
        } while (p1 != p2);
        ListNode *cur = head;
        while (cur != p1) {
            cur = cur->next;
            p1 = p1->next;
        }
        return cur;
    }
    
    展开全文
  • Leetcode 对撞指针

    2020-10-12 19:51:15
    Leetcode 对撞指针思路Leetecode 167新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右...
  • 浅谈“对撞指针法”这种通用解法以及应用于leetcode 125. Valid Palindrome 344.Reverse String,167. Two Sum II - Input array is sorted三道题。
  • 对撞指针:一左一右向中间逼近。 滑动窗口:类似计算机网络中的滑动窗口,例如, 快慢指针 是否有环 对撞指针 滑动窗口 滑动窗口:有左右端点和长度,根据题目调整左右端点的位置进行滑动。也是一种特殊的双...
  • 数组--对撞指针

    2020-03-19 14:07:26
    例题:两数之和 给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。 函数应该返回这两个下标值 index1 和 index2,其中 ...思路:由于数组是升序排列的,所以利用对撞指针,i从左向右,...
  • 第一次刷leetcode,结果的执行时间用同样的程序运行出来起伏都很大,我不太懂是为什么。 目录167. 两数之和 II - 输入有序数组题目我的答案V1出错的地方V2V3V4小结总结 167. 两数之和 II - 输入有序数组 ...
  • 欢迎来到算法小课堂,今天分享的内容是对撞指针在数组中的应用。分享的题目是LeetCode中的:167.两数之和||-输入有序数组125.验证回文串11.盛最多水的容器接下来,逐一看下如何...
  • 对撞指针 核心思想 维护两个索引 一个指针开始时为 l = 0 ,并且执行的操作为 l ++ 一个指针开始时为 r = arr.length - 1,并且执行的操作为 r --; 终止条件是 while( l < r ) 跳出循环的结果会是 l = r ...
  • 查找-- 对撞指针

    2020-08-28 20:03:32
    查找–对撞指针 给出一个整型数组nums,返回这个数组中两个数字的索引值i和j,使得nums[i] + nums[j]等于一个给定的target值,两个索引不能相等。 如:nums= [2,7,11,15],target=9 返回[0,1] 思路: 开始数组是否...
  • 125Input: "A man, a plan, a canal: Panama"Output: true判断一个字符串是不是回文串class Solution { public: bool isPalindrome(string s) { if ( s.length() == 0 || s.length() == 1) ...
  • 209-Minimum Size Subarray Sum (对于滑动窗口和对撞指针的相似之处的理解) 3-Longest Substring Without Repeating Characters 340-Longest Substring with At Most K Distinct Characters 对撞指针 1-Two Sum 167-...
  • Leetcode对撞指针

    2019-10-01 18:58:48
    先从一个简单的例子开始,给定一个排序...最开始学习对撞指针非常疑惑的地方就在于,除了-2 + 3 = 1,还有0 + 1 = 1。因为对撞指针解决的往往并不是唯一解问题。 假设l = 0, r = n - 1 = 3,nums[l] + nums[r] == ...
  • 本次查找2的主题是对撞指针,即双指针。以LeetCode的1.两数之和和15.三数之和为例。 2.例子 2.1 两数之和 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的...
  • 6.更新两指针j,k if(target (nums[i]+nums[j]+nums[k])) k--;else j++; 7.更新返回值: if(abs(target-ret) > abs(target-nums[i]-nums[j]-nums[k])) ret = nums[i]+nums[j]+nums[k]; 代码: int ...
  • 题目来源:链接 题目描述: 难度简单21输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出任意一对即可。 ...输入:nums = [2,7,11,15], target = 9 ...
  • LeetCode对撞指针汇总

    2019-05-05 23:09:00
    题目来源: leetCode 344,345,11 自我感觉难度/真实难度: 写题...都是使用对撞指针的技术 自己的代码: 代码效率/结果: 优秀代码: 11题 class Solution(object): def maxArea(self, a): """ :ty...
  • LeetCode 第 11 125 167 344 345 属于一类问题---数组相关的 “对撞指针”。 一、_11_ContainerWithMostWater 二、 _125_ValidPalindrome 三、_167_TwoSumIIInputArrayisSorted 四、_344_ReverseString ...
  • 在移动任意一个指针时,需要不断地向另一指针的方向移动,直到遇到一个字母或数字字符,或者两指针重合为止。也就是说,我们每次将指针移到下一个字母字符或数字字符,再判断这两个指针指向的字符是否相同。 ...
  • 学习对撞指针的应用 题目描述 初始时两个指针分别指向第一个元素位置和最后一个元素的位置。每次计算两个指针指向的两个元素之和,并和目标值比较。如果两个元素之和等于目标值,则发现了唯一解。如果两个元素之和...
  • 对撞指针常用作有序数组的元素查找,使用两个指针分别从头尾往中间进行迭代,相遇时终止。 刚接触对撞指针时,笔者对其算法原理有些怀疑:由于这两个指针不能“后退”,如何确保在迭代时,不错过有效值呢?下面尝试...
  • 一个对撞指针问题

    2019-04-14 16:34:09
    什么是对撞指针:我的理解就是两个指针分别从两端向中间靠拢 题目是这样的: 代码实现如下: 思路: 设置两个指针,分别指向这个数组最大right和最小下标left, 然后元素相加,如果相加结果等于target直接输出下标...
  • 和为 s 的两个数字(对撞指针) 个人博客 输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出任意一对即可。 输入:nums = [2,7,11,15], target = ...
  • 查找2 对撞指针 1. 两数之和 15. 三数之和 18. 四数之和 16. 最接近的三数之和 其他 454. 四数相加 II(查找表) 49. 字母异位词分组(字典) 447. 回旋镖的数量(查找表) 149. 直线上最多的点数(查找表) 滑动...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,264
精华内容 505
关键字:

对撞指针