双指针技巧.md 24.8 KB
Newer Older
L
labuladong 已提交
1 2
# 数组双指针技巧汇总

L
labuladong 已提交
3 4 5 6 7 8






L
labuladong 已提交
9 10


11 12
<p align='center'>
<a href="https://github.com/labuladong/fucking-algorithm" target="view_window"><img alt="GitHub" src="https://img.shields.io/github/stars/labuladong/fucking-algorithm?label=Stars&style=flat-square&logo=GitHub"></a>
L
labuladong 已提交
13
<a href="https://appktavsiei5995.pc.xiaoe-tech.com/index" target="_blank"><img class="my_header_icon" src="https://img.shields.io/static/v1?label=精品课程&message=查看&color=pink&style=flat"></a>
14 15 16 17
<a href="https://www.zhihu.com/people/labuladong"><img src="https://img.shields.io/badge/%E7%9F%A5%E4%B9%8E-@labuladong-000000.svg?style=flat-square&logo=Zhihu"></a>
<a href="https://space.bilibili.com/14089380"><img src="https://img.shields.io/badge/B站-@labuladong-000000.svg?style=flat-square&logo=Bilibili"></a>
</p>

L
labuladong 已提交
18
![](https://labuladong.github.io/algo/images/souyisou1.png)
19

L
labuladong 已提交
20
**通知:[数据结构精品课](https://aep.h5.xeknow.com/s/1XJHEO) 已更新到 V1.9,第 11 期刷题打卡挑战即将开始,[点这里报名](https://mp.weixin.qq.com/s/eUG2OOzY3k_ZTz-CFvtv5Q)。**
21 22 23



L
labuladong 已提交
24
读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:
25

L
labuladong 已提交
26 27 28 29 30 31 32 33 34 35 36
| LeetCode | 力扣 | 难度 |
| :----: | :----: | :----: |
| [167. Two Sum II - Input Array Is Sorted](https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/) | [167. 两数之和 II - 输入有序数组](https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/) | 🟢
| [26. Remove Duplicates from Sorted Array](https://leetcode.com/problems/remove-duplicates-from-sorted-array/) | [26. 删除有序数组中的重复项](https://leetcode.cn/problems/remove-duplicates-from-sorted-array/) | 🟢
| [27. Remove Element](https://leetcode.com/problems/remove-element/) | [27. 移除元素](https://leetcode.cn/problems/remove-element/) | 🟢
| [283. Move Zeroes](https://leetcode.com/problems/move-zeroes/) | [283. 移动零](https://leetcode.cn/problems/move-zeroes/) | 🟢
| [344. Reverse String](https://leetcode.com/problems/reverse-string/) | [344. 反转字符串](https://leetcode.cn/problems/reverse-string/) | 🟢
| [5. Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring/) | [5. 最长回文子串](https://leetcode.cn/problems/longest-palindromic-substring/) | 🟠
| [83. Remove Duplicates from Sorted List](https://leetcode.com/problems/remove-duplicates-from-sorted-list/) | [83. 删除排序链表中的重复元素](https://leetcode.cn/problems/remove-duplicates-from-sorted-list/) | 🟢
| - | [剑指 Offer 57. 和为s的两个数字](https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/) | 🟢
| - | [剑指 Offer II 006. 排序数组中两个数字之和](https://leetcode.cn/problems/kLl5u1/) | 🟢
37 38 39

**-----------**

L
labuladong 已提交
40
> 本文有视频版:[数组双指针技巧汇总](https://www.bilibili.com/video/BV1iG411W7Wm/)
L
labuladong 已提交
41

L
labuladong 已提交
42
在处理数组和链表相关问题时,双指针技巧是经常用到的,双指针技巧主要分为两类:**左右指针****快慢指针**
L
labuladong 已提交
43

L
labuladong 已提交
44
所谓左右指针,就是两个指针相向而行或者相背而行;而所谓快慢指针,就是两个指针同向而行,一快一慢。
L
labuladong 已提交
45

L
labuladong 已提交
46
对于单链表来说,大部分技巧都属于快慢指针,前文 [单链表的六大解题套路](https://labuladong.github.io/article/fname.html?fname=链表技巧) 都涵盖了,比如链表环判断,倒数第 `K` 个链表节点等问题,它们都是通过一个 `fast` 快指针和一个 `slow` 慢指针配合完成任务。
L
labuladong 已提交
47

L
labuladong 已提交
48
在数组中并没有真正意义上的指针,但我们可以把索引当做数组中的指针,这样也可以在数组中施展双指针技巧,**本文主要讲数组相关的双指针算法**
L
labuladong 已提交
49

L
labuladong 已提交
50
### 一、快慢指针技巧
L
labuladong 已提交
51

L
labuladong 已提交
52
**数组问题中比较常见的快慢指针技巧,是让你原地修改数组**
L
labuladong 已提交
53

L
labuladong 已提交
54
比如说看下力扣第 26 题「删除有序数组中的重复项」,让你在有序数组去重:
L
labuladong 已提交
55

L
labuladong 已提交
56
![](https://labuladong.github.io/algo/images/数组去重/title.png)
L
labuladong 已提交
57

L
labuladong 已提交
58
函数签名如下:
L
labuladong 已提交
59 60

```java
L
labuladong 已提交
61
int removeDuplicates(int[] nums);
L
labuladong 已提交
62 63
```

L
labuladong 已提交
64 65 66 67 68 69 70 71 72
简单解释一下什么是原地修改:

如果不是原地修改的话,我们直接 new 一个 `int[]` 数组,把去重之后的元素放进这个新数组中,然后返回这个新数组即可。

但是现在题目让你原地删除,不允许 new 新数组,只能在原数组上操作,然后返回一个长度,这样就可以通过返回的长度和原始数组得到我们去重后的元素有哪些了。

由于数组已经排序,所以重复的元素一定连在一起,找出它们并不难。但如果毎找到一个重复元素就立即原地删除它,由于数组中删除元素涉及数据搬移,整个时间复杂度是会达到 `O(N^2)`

高效解决这道题就要用到快慢指针技巧:
L
labuladong 已提交
73

L
labuladong 已提交
74
我们让慢指针 `slow` 走在后面,快指针 `fast` 走在前面探路,找到一个不重复的元素就赋值给 `slow` 并让 `slow` 前进一步。
L
labuladong 已提交
75

L
labuladong 已提交
76 77 78
这样,就保证了 `nums[0..slow]` 都是无重复的元素,当 `fast` 指针遍历完整个数组 `nums` 后,`nums[0..slow]` 就是整个数组去重之后的结果。

看代码:
L
labuladong 已提交
79 80

```java
L
labuladong 已提交
81 82 83
int removeDuplicates(int[] nums) {
    if (nums.length == 0) {
        return 0;
L
labuladong 已提交
84
    }
L
labuladong 已提交
85 86 87 88 89 90 91 92
    int slow = 0, fast = 0;
    while (fast < nums.length) {
        if (nums[fast] != nums[slow]) {
            slow++;
            // 维护 nums[0..slow] 无重复
            nums[slow] = nums[fast];
        }
        fast++;
L
fixbug  
labuladong 已提交
93
    }
L
labuladong 已提交
94 95 96 97 98 99
    // 数组长度为索引 + 1
    return slow + 1;
}
```

算法执行的过程如下 GIF 图:
L
fixbug  
labuladong 已提交
100

L
labuladong 已提交
101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118
![](https://labuladong.github.io/algo/images/数组去重/1.gif)

再简单扩展一下,看看力扣第 83 题「删除排序链表中的重复元素」,如果给你一个有序的单链表,如何去重呢?

其实和数组去重是一模一样的,唯一的区别是把数组赋值操作变成操作指针而已,你对照着之前的代码来看:

```java
ListNode deleteDuplicates(ListNode head) {
    if (head == null) return null;
    ListNode slow = head, fast = head;
    while (fast != null) {
        if (fast.val != slow.val) {
            // nums[slow] = nums[fast];
            slow.next = fast;
            // slow++;
            slow = slow.next;
        }
        // fast++
L
labuladong 已提交
119 120
        fast = fast.next;
    }
L
labuladong 已提交
121 122 123
    // 断开与后面重复元素的连接
    slow.next = null;
    return head;
L
labuladong 已提交
124 125 126
}
```

L
labuladong 已提交
127 128 129 130 131 132 133 134 135
算法执行的过程请看下面这个 GIF:

![](https://labuladong.github.io/algo/images/数组去重/2.gif)

这里可能有读者会问,链表中那些重复的元素并没有被删掉,就让这些节点在链表上挂着,合适吗?

这就要探讨不同语言的特性了,像 Java/Python 这类带有垃圾回收的语言,可以帮我们自动找到并回收这些「悬空」的链表节点的内存,而像 C++ 这类语言没有自动垃圾回收的机制,确实需要我们编写代码时手动释放掉这些节点的内存。

不过话说回来,就算法思维的培养来说,我们只需要知道这种快慢指针技巧即可。
L
labuladong 已提交
136

L
labuladong 已提交
137
**除了让你在有序数组/链表中去重,题目还可能让你对数组中的某些元素进行「原地删除」**
L
labuladong 已提交
138

L
labuladong 已提交
139
比如力扣第 27 题「移除元素」,看下题目:
L
labuladong 已提交
140

L
labuladong 已提交
141
![](https://labuladong.github.io/algo/images/数组去重/title1.png)
L
labuladong 已提交
142

L
labuladong 已提交
143
函数签名如下:
L
labuladong 已提交
144

L
labuladong 已提交
145 146 147
```java
int removeElement(int[] nums, int val);
```
L
labuladong 已提交
148

L
labuladong 已提交
149
题目要求我们把 `nums` 中所有值为 `val` 的元素原地删除,依然需要使用快慢指针技巧:
L
labuladong 已提交
150

L
labuladong 已提交
151
如果 `fast` 遇到值为 `val` 的元素,则直接跳过,否则就赋值给 `slow` 指针,并让 `slow` 前进一步。
L
labuladong 已提交
152

L
labuladong 已提交
153
这和前面说到的数组去重问题解法思路是完全一样的,就不画 GIF 了,直接看代码:
L
labuladong 已提交
154 155

```java
L
labuladong 已提交
156 157 158 159 160 161 162 163 164 165
int removeElement(int[] nums, int val) {
    int fast = 0, slow = 0;
    while (fast < nums.length) {
        if (nums[fast] != val) {
            nums[slow] = nums[fast];
            slow++;
        }
        fast++;
    }
    return slow;
L
labuladong 已提交
166 167 168
}
```

L
labuladong 已提交
169
注意这里和有序数组去重的解法有一个细节差异,我们这里是先给 `nums[slow]` 赋值然后再给 `slow++`,这样可以保证 `nums[0..slow-1]` 是不包含值为 `val` 的元素的,最后的结果数组长度就是 `slow`
L
labuladong 已提交
170

L
labuladong 已提交
171
实现了这个 `removeElement` 函数,接下来看看力扣第 283 题「移动零」:
L
labuladong 已提交
172

L
labuladong 已提交
173
给你输入一个数组 `nums`,请你**原地修改**,将数组中的所有值为 0 的元素移到数组末尾,函数签名如下:
L
labuladong 已提交
174

L
labuladong 已提交
175 176 177
```java
void moveZeroes(int[] nums);
```
L
labuladong 已提交
178

L
labuladong 已提交
179
比如说给你输入 `nums = [0,1,4,0,2]`,你的算法没有返回值,但是会把 `nums` 数组原地修改成 `[1,4,2,0,0]`
L
labuladong 已提交
180

L
labuladong 已提交
181
结合之前说到的几个题目,你是否有已经有了答案呢?
L
labuladong 已提交
182

L
labuladong 已提交
183
题目让我们将所有 0 移到最后,其实就相当于移除 `nums` 中的所有 0,然后再把后面的元素都赋值为 0 即可。
L
labuladong 已提交
184

L
labuladong 已提交
185
所以我们可以复用上一题的 `removeElement` 函数:
L
labuladong 已提交
186 187

```java
L
labuladong 已提交
188 189 190 191 192 193 194
void moveZeroes(int[] nums) {
    // 去除 nums 中的所有 0,返回不含 0 的数组长度
    int p = removeElement(nums, 0);
    // 将 nums[p..] 的元素赋值为 0
    for (; p < nums.length; p++) {
        nums[p] = 0;
    }
L
labuladong 已提交
195
}
L
labuladong 已提交
196 197 198

// 见上文代码实现
int removeElement(int[] nums, int val);
L
labuladong 已提交
199 200
```

L
labuladong 已提交
201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227
到这里,原地修改数组的这些题目就已经差不多了。数组中另一大类快慢指针的题目就是「滑动窗口算法」。

我在另一篇文章 [滑动窗口算法核心框架详解](https://labuladong.github.io/article/fname.html?fname=滑动窗口技巧进阶) 给出了滑动窗口的代码框架:

```cpp
/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;
    
    int left = 0, right = 0;
    int valid = 0; 
    while (right < s.size()) {
        char c = s[right];
        // 右移(增大)窗口
        right++;
        // 进行窗口内数据的一系列更新

        while (window needs shrink) {
            char d = s[left];
            // 左移(缩小)窗口
            left++;
            // 进行窗口内数据的一系列更新
        }
    }
}
```
L
labuladong 已提交
228

L
labuladong 已提交
229
具体的题目本文就不重复了,这里只强调滑动窗口算法的快慢指针特性:
L
labuladong 已提交
230

L
labuladong 已提交
231 232 233
`left` 指针在后,`right` 指针在前,两个指针中间的部分就是「窗口」,算法通过扩大和缩小「窗口」来解决某些问题。

### 二、左右指针的常用算法
L
labuladong 已提交
234 235 236

**1、二分查找**

L
labuladong 已提交
237
我在另一篇文章 [二分查找框架详解](https://labuladong.github.io/article/fname.html?fname=二分查找详解) 中有详细探讨二分搜索代码的细节问题,这里只写最简单的二分算法,旨在突出它的双指针特性:
L
labuladong 已提交
238 239 240

```java
int binarySearch(int[] nums, int target) {
L
labuladong 已提交
241 242
    // 一左一右两个指针相向而行
    int left = 0, right = nums.length - 1;
L
labuladong 已提交
243 244 245 246 247 248 249 250 251 252 253 254 255 256 257
    while(left <= right) {
        int mid = (right + left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; 
        else if (nums[mid] > target)
            right = mid - 1;
    }
    return -1;
}
```

**2、两数之和**

L
labuladong 已提交
258
看下力扣第 167 题「两数之和 II」:
L
labuladong 已提交
259

L
labuladong 已提交
260
![](https://labuladong.github.io/algo/images/双指针/title.png)
L
labuladong 已提交
261

L
labuladong 已提交
262
只要数组有序,就应该想到双指针技巧。这道题的解法有点类似二分查找,通过调节 `left``right` 就可以调整 `sum` 的大小:
L
labuladong 已提交
263 264 265

```java
int[] twoSum(int[] nums, int target) {
L
labuladong 已提交
266
    // 一左一右两个指针相向而行
L
labuladong 已提交
267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            // 题目要求的索引是从 1 开始的
            return new int[]{left + 1, right + 1};
        } else if (sum < target) {
            left++; // 让 sum 大一点
        } else if (sum > target) {
            right--; // 让 sum 小一点
        }
    }
    return new int[]{-1, -1};
}
```

L
labuladong 已提交
283 284
我在另一篇文章 [一个函数秒杀所有 nSum 问题](https://labuladong.github.io/article/fname.html?fname=nSum) 中也运用类似的左右指针技巧给出了 `nSum` 问题的一种通用思路,这里就不做赘述了。

L
labuladong 已提交
285 286
**3、反转数组**

L
labuladong 已提交
287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311
一般编程语言都会提供 `reverse` 函数,其实这个函数的原理非常简单,力扣第 344 题「反转字符串」就是类似的需求,让你反转一个 `char[]` 类型的字符数组,我们直接看代码吧:

```java
void reverseString(char[] s) {
    // 一左一右两个指针相向而行
    int left = 0, right = s.length - 1;
    while (left < right) {
        // 交换 s[left] 和 s[right]
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        left++;
        right--;
    }
}
```

**4、回文串判断**

首先明确一下,回文串就是正着读和反着读都一样的字符串。

比如说字符串 `aba``abba` 都是回文串,因为它们对称,反过来还是和本身一样;反之,字符串 `abac` 就不是回文串。

现在你应该能感觉到回文串问题和左右指针肯定有密切的联系,比如让你判断一个字符串是不是回文串,你可以写出下面这段代码:

L
labuladong 已提交
312
```java
L
labuladong 已提交
313 314 315
boolean isPalindrome(String s) {
    // 一左一右两个指针相向而行
    int left = 0, right = s.length() - 1;
L
labuladong 已提交
316
    while (left < right) {
L
labuladong 已提交
317 318 319 320 321
        if (s.charAt(left) != s.charAt(right)) {
            return false;
        }
        left++;
        right--;
L
labuladong 已提交
322
    }
L
labuladong 已提交
323
    return true;
L
labuladong 已提交
324 325 326
}
```

L
labuladong 已提交
327 328 329
那接下来我提升一点难度,给你一个字符串,让你用双指针技巧从中找出最长的回文串,你会做吗?

这就是力扣第 5 题「最长回文子串」:
L
labuladong 已提交
330

L
labuladong 已提交
331
![](https://labuladong.github.io/algo/images/回文/title.png)
L
labuladong 已提交
332

L
labuladong 已提交
333
函数签名如下:
334

L
labuladong 已提交
335 336 337
```java
String longestPalindrome(String s);
```
L
labuladong 已提交
338

L
labuladong 已提交
339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388
找回文串的难点在于,回文串的的长度可能是奇数也可能是偶数,解决该问题的核心是**从中心向两端扩散的双指针技巧**

如果回文串的长度为奇数,则它有一个中心字符;如果回文串的长度为偶数,则可以认为它有两个中心字符。所以我们可以先实现这样一个函数:

```java
// 在 s 中寻找以 s[l] 和 s[r] 为中心的最长回文串
String palindrome(String s, int l, int r) {
    // 防止索引越界
    while (l >= 0 && r < s.length()
            && s.charAt(l) == s.charAt(r)) {
        // 双指针,向两边展开
        l--; r++;
    }
    // 返回以 s[l] 和 s[r] 为中心的最长回文串
    return s.substring(l + 1, r);
}
```

这样,如果输入相同的 `l``r`,就相当于寻找长度为奇数的回文串,如果输入相邻的 `l``r`,则相当于寻找长度为偶数的回文串。

那么回到最长回文串的问题,解法的大致思路就是:

```python
for 0 <= i < len(s):
    找到以 s[i] 为中心的回文串
    找到以 s[i]  s[i+1] 为中心的回文串
    更新答案
```

翻译成代码,就可以解决最长回文子串这个问题:

```java
String longestPalindrome(String s) {
    String res = "";
    for (int i = 0; i < s.length(); i++) {
        // 以 s[i] 为中心的最长回文子串
        String s1 = palindrome(s, i, i);
        // 以 s[i] 和 s[i+1] 为中心的最长回文子串
        String s2 = palindrome(s, i, i + 1);
        // res = longest(res, s1, s2)
        res = res.length() > s1.length() ? res : s1;
        res = res.length() > s2.length() ? res : s2;
    }
    return res;
}
```

你应该能发现最长回文子串使用的左右指针和之前题目的左右指针有一些不同:之前的左右指针都是从两端向中间相向而行,而回文子串问题则是让左右指针从中心向两端扩展。不过这种情况也就回文串这类问题会遇到,所以我也把它归为左右指针了。

到这里,数组相关的双指针技巧就全部讲完了,这些技巧的更多扩展延伸见 [更多双指针经典高频题](https://appktavsiei5995.pc.xiaoe-tech.com/detail/i_62a1dd68e4b09dda1273a5f9/1)
L
labuladong 已提交
389

390
**_____________**
L
labuladong 已提交
391

L
labuladong 已提交
392
**《labuladong 的算法小抄》已经出版,关注公众号查看详情;后台回复关键词「**进群**」可加入算法群;回复「**全家桶**」可下载配套 PDF 和刷题全家桶**
L
labuladong 已提交
393 394

![](https://labuladong.github.io/algo/images/souyisou2.png)
L
labuladong 已提交
395 396


R
Ryan Deng 已提交
397 398
======其他语言代码======

B
brucecat 已提交
399 400 401 402 403 404 405 406
[141.环形链表](https://leetcode-cn.com/problems/linked-list-cycle)

[142.环形链表II](https://leetcode-cn.com/problems/linked-list-cycle-ii)

[167.两数之和 II - 输入有序数组](https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted)



B
BruceCat 已提交
407
### java
ZhengAu's avatar
ZhengAu 已提交
408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430

[zhengpj95](https://github.com/zhengpj95) 提供 Java 代码

```java
public class Solution {
    public boolean hasCycle(ListNode head) {
        //链表为空或只有一个结点,无环
        if (head == null || head.next == null) return false;

        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            // 快慢指针相遇则表示有环
            if (fast == slow) return true;
        }

        //fast指针到末尾,无环
        return false;
    }
}
```

B
BruceCat 已提交
431 432
### c++

D
DearDeer7 已提交
433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454
[deardeer7](https://github.com/DearDeer7/) 提供 C++ 代码
```cpp
class Solution {
public:
    bool hasCycle(ListNode *head) {
        // 链表为空或有一个元素,则无环
        if(!head || !head->next) return false; 
        
        ListNode* slow = head;
        ListNode* fast = head->next;

        while(fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
            // 快慢指针相遇,则有环
            if(fast == slow) return true;
        }
        return false; // 链表走完,快慢指针未相遇,则无环
    }
};
```

B
BruceCat 已提交
455

456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492
[zhengpj95](https://github.com/zhengpj95) 提供 【2、已知链表中含有环,返回这个环的起始位置】 C++ 代码

> 其实快慢指针问题,也就是著名的 *[Floyd's cycle detection algorithm](https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_Tortoise_and_Hare)* 问题。

```c++
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        // 如果链表为空或者第一个结点的指针为空,则无环
        if (!head || !head->next) {
            return NULL;
        }

        // 快慢指针找相遇点
        ListNode *fast = head, *slow = head;
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) {
                break;
            }
        }
        // 如果没有相遇点,表示没有环,直接返回即可
        // 此时,快慢指针要么指向同一个结点,要么快指针指向空(偶数个结点)或者倒数第一个结点(奇数个结点)
        if (fast != slow) {
            return NULL;
        }
        //让慢指针回到第一个结点,然后快慢指针重新同步前进,两指针相遇时就是环的起点位置
        slow = head;
        while (fast != slow) {
            fast = fast->next;
            slow = slow->next;
        }
        return fast;
    }
};
```
B
BruceCat 已提交
493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511

### python

[MarineJoker](https://github.com/MarineJoker) 提供 167.两数之和 II - 输入有序数组 Python 代码
```python
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers) - 1
        while left < right:
            two_sum = numbers[left] + numbers[right]
            if two_sum > target:
                right -= 1 # 使得two_sum变小
            elif two_sum < target:
                left += 1 # 使得two_sum变大
            elif two_sum == target:
                return [left+1, right+1] # 由于索引由1开始
        return [-1, -1]
```

R
Ryan Deng 已提交
512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531
[ryandeng32](https://github.com/ryandeng32/) 提供 Python 代码
```python
class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        # 检查链表头是否为None,是的话则不可能为环形
        if head is None: 
            return False 
        # 快慢指针初始化
        slow = fast = head 
        # 若链表非环形则快指针终究会遇到None,然后退出循环
        while fast.next and fast.next.next: 
            # 更新快慢指针
            slow = slow.next
            fast = fast.next.next
            # 快指针追上慢指针则链表为环形
            if slow == fast: 
                return True 
        # 退出循环,则链表有结束,不可能为环形
        return False 
```
M
MarineJoker 已提交
532

B
brucecat 已提交
533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757


### javascript

#### 一、快慢指针的常见算法

**1、判定链表中是否含有环**

[141.环形链表](https://leetcode-cn.com/problems/linked-list-cycle)

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

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    let fast, slow;
    fast = slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        
        if (fast == slow) return true;
    }
    return false;
};
```



**2、已知链表中含有环,返回这个环的起始位置**

[142.环形链表II](https://leetcode-cn.com/problems/linked-list-cycle-ii)

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

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    let fast, slow;
    fast = slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) break;
    }
    // 上面的代码类似 hasCycle 函数
    if (fast == null || fast.next == null) {
        // fast 遇到空指针说明没有环
        return null;
    }

    slow = head;
    while (slow != fast) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
};
```



**3、寻找链表的中点**

[876. 链表的中间结点](https://leetcode-cn.com/problems/middle-of-the-linked-list/)

```js
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var middleNode = function(head) {
    let fast, slow;
    fast = slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    // slow 就在中间位置
    return slow;
};
```

**4、寻找链表的倒数第 k 个元素**

[剑指 Offer 22. 链表中倒数第k个节点](https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/)

```js
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var getKthFromEnd = function(head, k) {
    let slow, fast;
    slow = fast = head;
    while (k-- > 0) 
        fast = fast.next;

    while (fast != null) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
};
```





#### 二、左右指针的常用算法

**1、二分查找**

[704. 二分查找](https://leetcode-cn.com/problems/binary-search/)

```js
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    if (nums.length === 0) return -1;
    let left = 0, right = nums.length - 1;
    while (left <= right) {
        let mid = Math.floor(left + (right - left) / 2);
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] === target) {
            // 直接返回
            return mid;
        }
    }
    // 直接返回
    return -1;
};
```

**2、两数之和**

[167.两数之和 II - 输入有序数组](https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted)

```js
/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let left = 0, right = nums.length - 1;
    while (left < right) {
        let sum = nums[left] + nums[right];
        if (sum === target) {
            // 题目要求的索引是从 1 开始的
            return [left + 1, right + 1];
        } else if (sum < target) {
            left++; // 让 sum 大一点
        } else if (sum > target) {
            right--; // 让 sum 小一点
        }
    }
    return [-1, -1];
};
```

**3、反转数组**

[344. 反转字符串](https://leetcode-cn.com/problems/reverse-string/)

```js
/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function(s) {
    let left = 0;
    let right = s.length - 1;
    while (left < right) {
        // swap(s[left], s[right])
        let temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        left++; right--;
    }
};
```

**4、滑动窗口算法**

L
labuladong 已提交
758
详见[这篇文章](https://labuladong.gitee.io/algo/)