# 双指针

指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。

# 1. 两数之和输入有序数组

167. 两数之和 II - 输入有序数组 (opens new window)

题目：

给定一个已按照_升序排列_ 的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明：

返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

示例：

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2

1
2
3

题解：

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (numbers, target) {
  let len = numbers.length;
  if (len < 2) return []
  let left = 0
  let right = len - 1
  while (left < right) {
    if (numbers[left] + numbers[right] === target) {
      return [left + 1, right + 1]
    } else if (numbers[left] + numbers[right] < target) {
      left++
    } else {
      right--
    }
  }
  return []
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 2. 平方数之和

633. 平方数之和 (opens new window)

题目:

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。

说明:

无

示例 1：

输入：c = 5
输出：true
解释：1 * 1 + 2 * 2 = 5

1
2
3

示例 2：

输入：c = 3
输出：false

1
2

题解：

/*
 * @lc app=leetcode.cn id=633 lang=javascript
 *
 * [633] 平方数之和
 */

// @lc code=start
/**
 * @param {number} c
 * @return {boolean}
 */
var judgeSquareSum = function(c) {
  let left=0
  let right = Math.floor(Math.sqrt(c))
  while(left<=right){
    if(left**2+right**2===c){
      return true
    }else if(left**2+right**2<c){
      left++
    }else{
      right--
    }
  }
  return false
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# 3. 反转字符串中的元音字母

345. 反转字符串中的元音字母 (opens new window)

题目:

编写一个函数，以字符串作为输入，反转该字符串中的元音字母。

说明:

元音字母不包含字母 "y" 。
题目没准确说明谁和谁转换，实际上应该是每次的最左和最右转换

示例 1：

输入："hello"
输出："holle"

1
2

示例 2：

输入："leetcode"
输出："leotcede"

1
2

题解：

/*
 * @lc app=leetcode.cn id=345 lang=javascript
 *
 * [345] 反转字符串中的元音字母
 */

// @lc code=start
/**
 * @param {string} s
 * @return {string}
 */
var reverseVowels = function (s) {
  const arr = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'];
  let str = s.split('')
  let left = 0
  let right = str.length - 1

  while (left < right) {
    if (arr.includes(str[left])) {
      if (arr.includes(str[right])) {
        // 左右都找到了，替换后左右分别++ --
        [str[left], str[right]] = [str[right], str[left]]
        left++
      }
      // 右边不管找没找到，都需要--，所以不用放在 else 里
      right--
    } else {
      // 左边没找到 ++
      left++
    }
  }
  return str.join('')
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

# 4. 回文字符串⭐

680. 验证回文字符串 Ⅱ (opens new window)

题目:

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

说明:

字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。

示例 1:

输入: "aba"
输出: True

1
2

示例 2:

输入: "abca"
输出: True
解释: 你可以删除c字符。

1
2
3

题解：

/**
 * @param {string} s
 * @return {boolean}
 */
var validPalindrome = function (s) {
  let left = 0
  let right = s.length - 1

  while (left < right) {
    if (s[left] === s[right]) {// 左右相等 分别向中间靠近一位
      left++
      right--
    } else {// 左右不等，删除左边是回文或者删除右边是回文即为 true 否则为 false
      return isHW(s, left + 1, right) || isHW(s, left, right - 1)
    }
  }
  return true
};

// 验证删除后的字符串是否回文，不回文则整个算法结束false，回文则结束ture
function isHW(s, left, right) {
  while (left < right) {
    if (s[left] === s[right]) {
      left++
      right--
    } else {
      return false
    }
  }
  return true
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# 5. 合并两个有序数组⭐

88. 合并两个有序数组 (opens new window)

题目:

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中*，*使 nums1 成为一个有序数组。

说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
Do not return anything, modify nums1 in-place instead.

示例：

输入：
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

输出：[1,2,2,3,5,6]

1
2
3
4
5

题解：

纯 ES6 数组操作

/*
 * @lc app=leetcode.cn id=88 lang=javascript
 *
 * [88] 合并两个有序数组
 */

// @lc code=start
/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function (nums1, m, nums2, n) {
  let arr = [...nums1.slice(0, m), ...nums2.slice(0, n)].sort((a, b) => a > b ? 1 : -1)
  nums1.splice(0, nums1.length, ...arr)
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

双指针

/*
 * @lc app=leetcode.cn id=88 lang=javascript
 *
 * [88] 合并两个有序数组
 */

// @lc code=start
/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function (nums1, m, nums2, n) {
  let len1 = m - 1
  let len2 = n - 1
  let len = m + n - 1
  // 分别比较实际末位 m&n，取大的值填入 nums1 然后大值数组向前退位
  // 直到 nums2 剩下的值都比 nums1 小【因为大的值都扔进 nums1 了】
  // 都是先计算 再 -1
  while (len1 >= 0 && len2 >= 0) {
    if (nums1[len1] > nums2[len2]) {
      nums1[len--] = nums1[len1--]
    } else {
      nums1[len--] = nums2[len2--]
    }
  }
  // 将 nums2 剩余的小值从前面塞进 nums1
  // 不用担心覆盖 nums1 前面的值，因为那些值都在后面了
  nums1.splice(0, len2 + 1, ...nums2.slice(0, len2 + 1))
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

上述算法步骤解释：

输入:
[3,5,0,0,0] m = 2
[1,2,6]     n = 3

步骤[*代表当前指向]：
=> 
nums1: [3,*5,0,0,0]  len1 = 1
nums2: [1,2,*6]			 len2 = 2
=>
6 > 5,遵循“大值(6)塞后，向前退位”
nums1: [3,*5,0,0,6]  len1 = 1
nums2: [1,*2,6]			 len2 = 1
=>
2 < 5,遵循“大值(5)塞后，向前退位”
nums1: [*3,5,0,5,6]  len1 = 0
nums2: [1,*2,6]			 len2 = 1
=>
2 < 3,遵循“大值(3)塞后，向前退位”
nums1: [3,5,3,5,6]   len1 = -1  (len1 不符合 while 条件，循环结束)
nums2: [1,*2,6]			 len2 = 1
=>
此时 nums2，还剩有效(len2+1 即 2)位，将它覆盖塞入 num1 前部，nums1 的前部 2 位(即 [3,5])已经塞到 nums1 后面了
nums1: [1,2,3,5,6]   
nums2: [1,2,6]
=>
END.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# 6. 环形链表[快慢指针]⭐

141. 环形链表 (opens new window)

题目:

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

说明:

链表是 lc 后台代码生成的，传入的是已经生成好的链表对象
pos 是个概念，理解就行，不必深究
链表结构可以参考这里 (opens new window)

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

1
2
3

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

1
2
3

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

1
2
3

题解：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
  // 判断有两个节点以上，否则不能成环
  if (!head || !head.next) return false;

  let slow = head
  let fast = head.next
  // 如果是非环没有 fast.next 的时候即走到终点
  // fast 本身可能已经 undefined ，因为它是每次跨两步，在 fast.next?.next 的时候已经 undefined 了
  while (fast && fast.next) {
    if (slow === fast) {// 相遇
      return true
    } else {// 慢指针每次走一步，快指针每次走两步
      slow = slow.next
      fast = fast.next?.next
    }
  }
  return false
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

142. 环形链表 II (opens new window)

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点解释：链表中有一个环，其尾部连接到第二个节点。

题解

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function (head) {
    /**
        关键在于推倒过程
        判断双指针用快慢指针就行
        有一个规律: 指针相遇的时候 慢指针一定没有走完一圈

        判断推倒过程:
        链表起点环起点距离是x,起点到相交位置是y(y是环长度的一部分),环剩余长度是z
        由于快指针速度是慢指针的2倍,所以:
        2(x+y) = x+y+n(y+z) // y+z是环的长度 n是快指针走了n次环 [想象x很长的情况,快指针很早之前就到了环内]
    => x+y = n(y+z)
    => x = n(y+z)-y
    => x = (n-1)(y+z) +y+z-y
    => x = (n-1)(y+z) + z

    x是我们要的距离 这个式子中 n一定大于1 因为至少快指针走一圈才能碰到慢指针
    而 y+z 是环的长度 z是相交点到x的距离
    如果n=1 则x=z 说明此时起点到环开始点的距离 = 相交点到环开始的距离
    如果n>1 说明此时起点到环开始点的距离 = 相交点到环开始的距离 + n-1圈环
     */

    if (!head || !head.next) return null

    // 两个节点先走一次 不然while判断不好写
    let fast = head.next.next, slow = head.next

    // fast走了两次之后可能已经没值了
    while (fast && fast.next && fast !== slow) {
        fast = fast.next.next
        slow = slow.next
    }

    // // 没碰到但是走完了 不是环
    if (!fast || !fast.next) return null

    // 碰上了 开始一个从head走 一个从碰撞点走
    slow = head;
    while (fast !== slow) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

# 7. 通过删除字母匹配到字典里最长单词

524. 通过删除字母匹配到字典里最长单词 (opens new window)

题目:

给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。

说明:

所有输入的字符串只包含小写字母。
字典的大小不会超过 1000。
所有输入的字符串长度不会超过 1000。

示例 1:

输入:
s = "abpcplea", d = ["ale","apple","monkey","plea"]

输出: 
"apple"

1
2
3
4
5

示例 2:

输入:
s = "abpcplea", d = ["a","b","c"]

输出: 
"a"

1
2
3
4
5

题解：

变量 max 存当前最大长度，already 存储已经遇到过的字符串，不二次处理。

两个指针依次前推，和前面题目差不多

/*
 * @lc app=leetcode.cn id=524 lang=javascript
 *
 * [524] 通过删除字母匹配到字典里最长单词
 */

// @lc code=start
/**
 * @param {string} s
 * @param {string[]} d
 * @return {string}
 */
var findLongestWord = function (s, d) {
  let result = ""// 存储满足结果的值
  let max = 0
  let already = new Set()

  for (let dstr of d) {
    // 长度比之前的小 or 已经遇到过的，直接 pass
    if (dstr.length < max || already.has(dstr)) continue;
    
    let slen = s.length - 1
    let dlen = dstr.length - 1

    // 新值存入 Set
    already.add(dstr)
    // 按顺序比较 
    while (dlen >= 0 && slen >= 0) {
      if (s[slen] === dstr[dlen]) {// 匹配到了向前推进
        slen--
        dlen--
      } else { // 不匹配 s 向前推进
        slen--
      }
    }

    //匹配成功 => 长度更长 or 长度相等时，字典顺序最小
    if (dlen < 0
      && ((dstr.length > result.length) || (dstr.length == result.length && dstr < result))) {
      result = dstr
      max = result.length
    }
  }

  return result
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

# 8. 盛最多水的容器

11. 盛最多水的容器 (opens new window)

给你 n 个非负整数 a1，a2，...，a``n，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

**说明：**你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

1
2
3

示例 2：

输入：height = [1,1]
输出：1

1
2

示例 3：

输入：height = [4,3,2,1,4]
输出：16

1
2

示例 4：

输入：height = [1,2,1]
输出：2

1
2

提示：

n == height.length
2 <= n <= 105
0 <= height[i] <= 104

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height) {
  /**
   * 双指针左右收拢
   * 哪边短收哪边
   * 如果改变的那边比原来更短 直接跳过不算面积
   * 否则正常取max值
   */
  let [l, r] = [0, height.length - 1];
  let res = (r - l) * Math.min(height[l], height[r]);

  while (l < r) {
    if (height[l] < height[r]) {
      // 左边短
      l++;
      if (height[l] <= height[l - 1]) continue;
    } else {
      r--;
      if (height[r] <= height[r + 1]) continue;
    }

    res = Math.max(res, (r - l) * Math.min(height[l], height[r]));
  }

  return res
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

# 9. 三数之和 (opens new window)

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 *a，b，c ，*使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

**注意：**答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

1
2

示例 2：

输入：nums = []
输出：[]

1
2

示例 3：

输入：nums = [0]
输出：[]

1
2

提示：

0 <= nums.length <= 3000
-105 <= nums[i] <= 105

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  /**
   * 先排序 固定一个值i（从第一个开始
   * 如果这个值i比0大了 结束计算输出答案（因为这个值只会越来越大）
   * 两个指针指向他后面的数组的开始和结束
   * 三个数加起来 大于0 r-- 小于0 l++ 等于0 保存
   * 一轮循环结束后 i++ 如果和前面一个数一样 pass 因为结果一样（lr也要去重）
   */
  if (nums.length < 3) return [];
  nums = nums.sort((a,b)=>a-b);
  const res = [];
  let i = 0;
  while (i <= nums.length - 3 && nums[i] <= 0) {
    let [l, r] = [i + 1, nums.length - 1];
    while (l < r) {
      if (nums[i] + nums[l] + nums[r] > 0) {
        r--;
      } else if (nums[i] + nums[l] + nums[r] < 0) {
        l++;
      } else {
        res.push([nums[i], nums[l], nums[r]]);
        // 下面两个while针对 [-2,0,0,2,2] 这种情况去重
        while (l < r && nums[l] === nums[l + 1]) l++;
        while (l < r && nums[r] === nums[r - 1]) r--;
        r--;
        l++;
      }
    }
    // 去重
    while (i <= nums.length - 3 && nums[i] <= 0 && nums[i] === nums[i + 1]) i++;
    i++;
  }

  return res;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

# 18. 四数之和 (opens new window)

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按任意顺序返回答案。

示例1

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

1
2

题解

四数之和基本是N数之和的模板解答,和三数类似

用双指针寻值的前提是固定一个值,这里就是固定 nums[i]+nums[j] ,而三数之和就是用一层循环

循环的优化是剪枝,针对前一个值和当前值一样的情况下,可以直接跳过,否则会有重复答案,但是二层循环的j要注意必须是 j > i + 1 的情况下,避免case [2,2,2,2,2] 这种情况的错误

在查找到一个结果后对双指针进行收缩,为了避免重复答案,l和r必须收缩到和上一个值不同为止

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function (nums, target) {
    // 类似三数 只是两层for固定一个sum
    let res = []
    nums = nums.sort((a, b) => a - b)

    for (let i = 0; i < nums.length - 3; i++) {
        if (nums[i] === nums[i - 1]) continue;

        for (let j = i + 1; j < nums.length - 2; j++) {
            // 这里注意 条件j>i+1 ,如果不加 在case[2,2,2,2,2] => 8 的情况下就会直接结束循环
            if (j > i + 1 && nums[j] === nums[j - 1]) continue;

            let l = j + 1
            let r = nums.length - 1

            while (l < r) {
                const sum = nums[i] + nums[j] + nums[l] + nums[r]

                if (sum > target) {
                    r--
                } else if (sum < target) {
                    l++
                } else {
                    res.push([nums[i], nums[j], nums[l], nums[r]])

                    // 收口
                    while (l < r && nums[l] === nums[l + 1]) l++
                    while (l < r && nums[r] === nums[r + 1]) r--
                    l++
                    r--
                }
            }
        }
    }

    return res

};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

← 排序搜索 →

# 双指针

# 1. 两数之和 输入有序数组

# 2. 平方数之和

# 3. 反转字符串中的元音字母

# 4. 回文字符串⭐

# 5. 合并两个有序数组⭐

# 6. 环形链表[快慢指针]⭐

# 7. 通过删除字母匹配到字典里最长单词

# 8. 盛最多水的容器

# 9. 三数之和 (opens new window)

# 18. 四数之和 (opens new window)

# 1. 两数之和输入有序数组