双指针技巧秒杀七道数组题目
数据结构精品课 已更新到 V2.1， 手把手刷二叉树系列课程 上线。
———–
本文有视频版： 数组双指针技巧汇总。建议关注我的 B 站账号，我会用视频领读的方式带大家学习那些稍有难度的算法技巧。
所谓左右指针，就是两个指针相向而行或者相背而行；而所谓快慢指针，就是两个指针同向而行，一快一慢。
对于单链表来说，大部分技巧都属于快慢指针，前文
单链表的六大解题套路 都涵盖了，比如链表环判断，倒数第 K 个链表节点等问题，它们都是通过一个 fast 快指针和一个 slow 慢指针配合完成任务。
在数组中并没有真正意义上的指针，但我们可以把索引当做数组中的指针，这样也可以在数组中施展双指针技巧，本文主要讲数组相关的双指针算法。
一、快慢指针技巧
数组问题中比较常见的快慢指针技巧，是让你原地修改数组。
比如说看下力扣第 26 题「 删除有序数组中的重复项」，让你在有序数组去重：
函数签名如下：
int removeDuplicates(int[] nums);
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
int removeDuplicates(vector<int>& nums);
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def removeDuplicates(nums: List[int]) -> int:
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func removeDuplicates(nums []int) int {}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var removeDuplicates = function(nums) {};
简单解释一下什么是原地修改：
如果不是原地修改的话，我们直接 new 一个 int[] 数组，把去重之后的元素放进这个新数组中，然后返回这个新数组即可。
但是现在题目让你原地删除，不允许 new 新数组，只能在原数组上操作，然后返回一个长度，这样就可以通过返回的长度和原始数组得到我们去重后的元素有哪些了。
由于数组已经排序，所以重复的元素一定连在一起，找出它们并不难。但如果毎找到一个重复元素就立即原地删除它，由于数组中删除元素涉及数据搬移，整个时间复杂度是会达到 O(N^2)。
高效解决这道题就要用到快慢指针技巧：
我们让慢指针 slow 走在后面，快指针 fast 走在前面探路，找到一个不重复的元素就赋值给 slow 并让 slow 前进一步。
这样，就保证了 nums[0..slow] 都是无重复的元素，当 fast 指针遍历完整个数组 nums 后，nums[0..slow] 就是整个数组去重之后的结果。
看代码：
int removeDuplicates(int[] nums) {
if (nums.length == 0) {
return 0;
}
int slow = 0, fast = 0;
while (fast < nums.length) {
if (nums[fast] != nums[slow]) {
slow++;
// 维护 nums[0..slow] 无重复
nums[slow] = nums[fast];
}
fast++;
}
// 数组长度为索引 + 1
return slow + 1;
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
int removeDuplicates(vector<int>& nums) {
if (nums.size() == 0) {
return 0;
}
int slow = 0, fast = 0;
while (fast < nums.size()) {
if (nums[fast] != nums[slow]) {
slow++;
// 维护 nums[0..slow] 无重复
nums[slow] = nums[fast];
}
fast++;
}
// 数组长度为索引 + 1
return slow + 1;
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def removeDuplicates(nums: List[int]) -> int:
if len(nums) == 0:
return 0
# 维护 nums[0..slow] 无重复
slow = 0
fast = 1
while fast < len(nums):
if nums[fast] != nums[slow]:
slow += 1
# 维护 nums[0..slow] 无重复
nums[slow] = nums[fast]
fast += 1
# 数组长度为索引 + 1
return slow + 1
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func removeDuplicates(nums []int) int {
if len(nums) == 0 {
return 0
}
slow,fast :=0,0
for fast<len(nums) {
if nums[fast] != nums[slow] {
slow++
// 维护 nums[0..slow] 无重复
nums[slow] = nums[fast]
}
fast++
}
// 数组长度为索引 + 1
return slow + 1
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var removeDuplicates = function(nums) {
if (nums.length == 0) {
return 0;
}
var slow = 0, fast = 0;
while (fast < nums.length) {
if (nums[fast] != nums[slow]) {
slow++;
// 维护 nums[0..slow] 无重复
nums[slow] = nums[fast];
}
fast++;
}
// 数组长度为索引 + 1
return slow + 1;
};
👾 代码可视化动画 👾
算法执行的过程如下 GIF 图：
再简单扩展一下，看看力扣第 83 题「 删除排序链表中的重复元素」，如果给你一个有序的单链表，如何去重呢？
其实和数组去重是一模一样的，唯一的区别是把数组赋值操作变成操作指针而已，你对照着之前的代码来看：
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++
fast = fast.next;
}
// 断开与后面重复元素的连接
slow.next = null;
return head;
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
ListNode* deleteDuplicates(ListNode* head) {
if (head == nullptr) return nullptr;
ListNode* slow = head; // 当前元素
ListNode* fast = head; // 下一个元素
while (fast != nullptr) {
if (fast->val != slow->val) {
// 当前元素的下一个元素设置为下一个不相等的元素
slow->next = fast;
// 当前元素向后移动
slow = slow->next;
}
// 下一个元素向后移动
fast = fast->next;
}
// 断开与后面重复元素的连接
slow->next = nullptr;
return head;
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def deleteDuplicates(head: ListNode) -> ListNode:
if not head: # 如果链表为空，返回 null 。
return None
slow, fast = head, head
while fast: # 遍历链表，并找到重复元素。
if fast.val != slow.val: # 如果 fast 指向的节点与 slow 指向的节点的值不相等，说明链表中出现了重复元素。
slow.next = fast # 将 slow 指向 fast 的位置。
slow = slow.next # slow 指向下一个节点。
fast = fast.next # fast 指向下一个节点。
slow.next = None # 断开与后面重复元素的连接
return head # 返回处理后的链表头节点。
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
// deleteDuplicates 函数实现从排序链表中删除重复元素。
func deleteDuplicates(head *ListNode) *ListNode {
if head == nil {
return nil
}
// 初始化双指针slow, fast
slow, fast := head, head
for fast != nil {
if fast.Val != slow.Val {
// slow指针与快指针相等的值赋值为快指针的值
slow.Next = fast
// 将指针后移，操作下一个节点
slow = slow.Next
}
// 将指针后移，操作下一个节点
fast = fast.Next
}
// 断开与后面重复元素的连接
slow.Next = nil
return head
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var deleteDuplicates = function(head) {
if (head === null) return null;
let slow = head, fast = head;
while (fast !== null) {
if (fast.val !== slow.val) {
// nums[slow] = nums[fast];
slow.next = fast;
// slow++;
slow = slow.next;
}
// fast++
fast = fast.next;
}
// 断开与后面重复元素的连接
slow.next = null;
return head;
};
算法执行的过程请看下面这个 GIF：
这里可能有读者会问，链表中那些重复的元素并没有被删掉，就让这些节点在链表上挂着，合适吗？
这就要探讨不同语言的特性了，像 Java/Python 这类带有垃圾回收的语言，可以帮我们自动找到并回收这些「悬空」的链表节点的内存，而像 C++ 这类语言没有自动垃圾回收的机制，确实需要我们编写代码时手动释放掉这些节点的内存。
不过话说回来，就算法思维的培养来说，我们只需要知道这种快慢指针技巧即可。
除了让你在有序数组/链表中去重，题目还可能让你对数组中的某些元素进行「原地删除」。
比如力扣第 27 题「 移除元素」，看下题目：
函数签名如下：
int removeElement(int[] nums, int val);
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
int removeElement(vector<int>& nums, int val);
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def removeElement(nums: List[int], val: int) -> int:
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func removeElement(nums []int, val int) int {}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var removeElement = function(nums, val) {};
题目要求我们把 nums 中所有值为 val 的元素原地删除，依然需要使用快慢指针技巧：
如果 fast 遇到值为 val 的元素，则直接跳过，否则就赋值给 slow 指针，并让 slow 前进一步。
这和前面说到的数组去重问题解法思路是完全一样的，就不画 GIF 了，直接看代码：
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;
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
int removeElement(vector<int>& nums, int val) {
int fast = 0, slow = 0;
while (fast < nums.size()) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def removeElement(nums: List[int], val: int) -> int:
fast, slow = 0, 0
while fast < len(nums):
if nums[fast] != val:
nums[slow] = nums[fast]
slow += 1
fast += 1
return slow
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func removeElement(nums []int, val int) int {
fast, slow := 0, 0
for fast < len(nums) {
if nums[fast] != val {
nums[slow] = nums[fast]
slow++
}
fast++
}
return slow
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var removeElement = function(nums, val) {
var fast = 0, slow = 0;
while (fast < nums.length) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
注意这里和有序数组去重的解法有一个细节差异，我们这里是先给 nums[slow] 赋值然后再给 slow++，这样可以保证 nums[0..slow-1] 是不包含值为 val 的元素的，最后的结果数组长度就是 slow。
实现了这个 removeElement 函数，接下来看看力扣第 283 题「
移动零」：
给你输入一个数组 nums，请你原地修改，将数组中的所有值为 0 的元素移到数组末尾，函数签名如下：
void moveZeroes(int[] nums);
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
void moveZeroes(vector<int>& nums);
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def moveZeroes(nums: List[int]) -> None:
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func moveZeroes(nums []int) {}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
function moveZeroes(nums) {
// function body
}
比如说给你输入 nums = [0,1,4,0,2]，你的算法没有返回值，但是会把 nums 数组原地修改成 [1,4,2,0,0]。
结合之前说到的几个题目，你是否有已经有了答案呢？
题目让我们将所有 0 移到最后，其实就相当于移除 nums 中的所有 0，然后再把后面的元素都赋值为 0 即可。
所以我们可以复用上一题的 removeElement 函数：
void moveZeroes(int[] nums) {
// 去除 nums 中的所有 0，返回不含 0 的数组长度
int p = removeElement(nums, 0);
// 将 nums[p..] 的元素赋值为 0
for (; p < nums.length; p++) {
nums[p] = 0;
}
}
// 见上文代码实现
int removeElement(int[] nums, int val);
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
void moveZeroes(vector<int>& nums) {
// 去除 nums 中的所有 0，返回不含 0 的数组长度
int p = removeElement(nums, 0);
// 将 nums[p..] 的元素赋值为 0
for (; p < nums.size(); p++) {
nums[p] = 0;
}
}
// 见上文代码实现
int removeElement(vector<int>& nums, int val);
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def moveZeroes(nums: List[int]) -> None:
def removeElement(nums: List[int], val: int) -> int:
# 去除 nums 中的所有 val，返回不含 val 的数组长度
pointer = 0
for i in range(len(nums)):
if nums[i] != val:
nums[pointer] = nums[i]
pointer += 1
return pointer
# 去除 nums 中的所有 0，返回不含 0 的数组长度
p = removeElement(nums, 0)
# 将 nums[p..] 的元素赋值为 0
for i in range(p, len(nums)):
nums[i] = 0
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func moveZeroes(nums []int) {
// 去除 nums 中的所有 0，返回不含 0 的数组长度
p := removeElement(nums, 0)
// 将 nums[p..] 的元素赋值为 0
for ; p < len(nums); p++ {
nums[p] = 0
}
}
// 见上文代码实现
func removeElement(nums []int, val int) int {
// ...
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
// 去除 nums 中的所有 0，返回不含 0 的数组长度
var removeElement = function(nums, val) {
var i = 0;
for (var j = 0; j < nums.length; j++) {
if (nums[j] !== val) {
nums[i] = nums[j];
i++;
}
}
return i;
};
var moveZeroes = function(nums) {
// 去除 nums 中的所有 0，返回不含 0 的数组长度
var p = removeElement(nums, 0);
// 将 nums[p..] 的元素赋值为 0
for (; p < nums.length; p++) {
nums[p] = 0;
}
};
👾 代码可视化动画 👾
到这里，原地修改数组的这些题目就已经差不多了。数组中另一大类快慢指针的题目就是「滑动窗口算法」。
我在另一篇文章 滑动窗口算法核心框架详解 给出了滑动窗口的代码框架：
// 注意：java 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
/* 滑动窗口算法框架 */
public void slidingWindow(String s, String t) {
HashMap<Character, Integer> need = new HashMap<>();
HashMap<Character, Integer> window = new HashMap<>();
for (char c : t.toCharArray()) need.put(c, need.getOrDefault(c, 0) + 1);
int left = 0, right = 0;
int valid = 0;
while (right < s.length()) {
char c = s.charAt(right);
// 右移（增大）窗口
right++;
// 进行窗口内数据的一系列更新
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c))) valid++;
}
while (window needs shrink) {
char d = s.charAt(left);
// 左移（缩小）窗口
left++;
// 进行窗口内数据的一系列更新
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) valid--;
window.put(d, window.getOrDefault(d, 0) - 1);
}
}
}
}
/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
unordered_map<char, int> window;
int left = 0, right = 0;
while (right < s.size()) {
char c = s[right];
// 右移（增大）窗口
right++;
// 进行窗口内数据的一系列更新
while (window needs shrink) {
char d = s[left];
// 左移（缩小）窗口
left++;
// 进行窗口内数据的一系列更新
}
}
}
# 注意：python 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
# 滑动窗口算法框架
def slidingWindow(s: str, t: str):
from collections import defaultdict
need = defaultdict(int)
window = defaultdict(int)
for c in t:
need[c] += 1
left, right = 0, 0
valid = 0
while right < len(s):
c = s[right]
right += 1
# 进行窗口内数据的一系列更新
window[c] += 1
while window needs shrink:
d = s[left]
left += 1
# 进行窗口内数据的一系列更新
// 注意：go 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
// 滑动窗口算法框架
func slidingWindow(s string, t string) {
// 初始化need 和 window
need := make(map[rune]int)
window := make(map[rune]int)
for _, c := range t {
need[c]++
}
left, right := 0, 0
valid := 0
for right < len(s) {
c := rune(s[right])
right++
// 进行窗口内数据的更新
for window needs shrink {
d := rune(s[left])
left++
// 进行窗口内数据的一系列更新
}
}
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。
var slidingWindow = function(s, t) {
var need = new Map();
var window = new Map();
for (var i = 0; i < t.length; i++) {
var c = t[i];
if (need.has(c)) {
need.set(c, need.get(c) + 1);
} else {
need.set(c, 1);
}
}
var left = 0, right = 0;
var valid = 0;
while (right < s.length) {
var c = s[right];
// 右移（增大）窗口
right++;
// 进行窗口内数据的一系列更新
while (window needs shrink) {
var d = s[left];
// 左移（缩小）窗口
left++;
// 进行窗口内数据的一系列更新
}
}
}
具体的题目本文就不重复了，这里只强调滑动窗口算法的快慢指针特性：
left 指针在后，right 指针在前，两个指针中间的部分就是「窗口」，算法通过扩大和缩小「窗口」来解决某些问题。
二、左右指针的常用算法
1、二分查找
我在另一篇文章 二分查找框架详解 中有详细探讨二分搜索代码的细节问题，这里只写最简单的二分算法，旨在突出它的双指针特性：
int binarySearch(int[] nums, int target) {
// 一左一右两个指针相向而行
int left = 0, right = nums.length - 1;
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;
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
int binarySearch(vector<int>& nums, int target) {
// 一左一右两个指针相向而行
int left = 0, right = nums.size() - 1;
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;
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def binarySearch(nums: List[int], target: int) -> int:
# 一左一右两个指针相向而行
left = 0
right = len(nums)-1
while left <= right:
mid = (right + left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func binarySearch(nums []int, target int) int {
// 一左一右两个指针相向而行
left, right := 0, len(nums)-1
for left <= right {
mid := (left + right) / 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
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var binarySearch = function(nums, target) {
// 一左一右两个指针相向而行
var left = 0, right = nums.length - 1;
while (left <= right) {
var mid = Math.floor((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、两数之和
看下力扣第 167 题「 两数之和 II」：
只要数组有序，就应该想到双指针技巧。这道题的解法有点类似二分查找，通过调节 left 和 right 就可以调整 sum 的大小：
int[] twoSum(int[] nums, int target) {
// 一左一右两个指针相向而行
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};
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
vector<int> twoSum(vector<int>& nums, int target) {
// 一左一右两个指针相向而行
int left = 0, right = nums.size() - 1;
while (left < right) {
int 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};
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def twoSum(nums: List[int], target: int) -> List[int]:
# 一左一右两个指针相向而行
left, right = 0, len(nums) - 1
while left < right:
sum = nums[left] + nums[right]
if sum == target:
# 题目要求的索引是从 1 开始的
return [left + 1, right + 1]
elif sum < target:
left += 1 # 让 sum 大一点
else:
right -= 1 # 让 sum 小一点
return [-1, -1]
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func twoSum(nums []int, target int) []int {
// 一左一右两个指针相向而行
left, right := 0, len(nums) - 1
for left < right {
sum := nums[left] + nums[right]
if sum == target {
// 题目要求的索引是从 1 开始的
return []int{left + 1, right + 1}
} else if sum < target {
left++ // 让 sum 大一点
} else if sum > target {
right-- // 让 sum 小一点
}
}
return []int{-1, -1}
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var twoSum = function(nums, target) {
// 一左一右两个指针相向而行
var left = 0, right = nums.length - 1;
while (left < right) {
var 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];
};
我在另一篇文章
一个函数秒杀所有 nSum 问题 中也运用类似的左右指针技巧给出了 nSum 问题的一种通用思路，这里就不做赘述了。
3、反转数组
一般编程语言都会提供 reverse 函数，其实这个函数的原理非常简单，力扣第 344 题「
反转字符串」就是类似的需求，让你反转一个 char[] 类型的字符数组，我们直接看代码吧：
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--;
}
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
void reverseString(vector<char>& s) {
// 一左一右两个指针相向而行
int left = 0, right = s.size() - 1;
while (left < right) {
// 交换 s[left] 和 s[right]
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def reverseString(s: List[str]) -> None:
# 一左一右两个指针相向而行
left = 0
right = len(s) - 1
while left < right:
# 交换 s[left] 和 s[right]
temp = s[left]
s[left] = s[right]
s[right] = temp
left += 1
right -= 1
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func reverseString(s []byte) {
// 一左一右两个指针相向而行
left, right := 0, len(s)-1
for left < right {
// 交换 s[left] 和 s[right]
temp := s[left]
s[left] = s[right]
s[right] = temp
left++
right--
}
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var reverseString = function(s) {
// 一左一右两个指针相向而行
let left = 0,
right = s.length - 1;
while (left < right) {
// 交换 s[left] 和 s[right]
let temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
};
4、回文串判断
首先明确一下，回文串就是正着读和反着读都一样的字符串。
比如说字符串 aba 和 abba 都是回文串，因为它们对称，反过来还是和本身一样；反之，字符串 abac 就不是回文串。
现在你应该能感觉到回文串问题和左右指针肯定有密切的联系，比如让你判断一个字符串是不是回文串，你可以写出下面这段代码：
boolean isPalindrome(String s) {
// 一左一右两个指针相向而行
int left = 0, right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
bool isPalindrome(string s) {
// 一左一右两个指针相向而行
int left = 0, right = s.length() - 1;
while (left < right) {
if (s[left] != s[right]) { // 如果不相同，就不是回文串
return false;
}
left++;
right--;
}
return true;
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def isPalindrome(s: str) -> bool:
# 一左一右两个指针相向而行
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func isPalindrome(s string) bool {
// 一左一右两个指针相向而行
left := 0
right := len(s) - 1
for left < right {
if s[left] != s[right] {
return false
}
left++
right--
}
return true
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var isPalindrome = function(s) {
// 一左一右两个指针相向而行
let left = 0, right = s.length-1;
while (left < right) {
if (s.charAt(left) !== s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
};
那接下来我提升一点难度，给你一个字符串，让你用双指针技巧从中找出最长的回文串，你会做吗？
这就是力扣第 5 题「 最长回文子串」：
函数签名如下：
String longestPalindrome(String s);
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
string longestPalindrome(string s);
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def longestPalindrome(s: str) -> str:
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func longestPalindrome(s string) string {}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var longestPalindrome = function(s) {}
找回文串的难点在于，回文串的的长度可能是奇数也可能是偶数，解决该问题的核心是从中心向两端扩散的双指针技巧。
如果回文串的长度为奇数，则它有一个中心字符；如果回文串的长度为偶数，则可以认为它有两个中心字符。所以我们可以先实现这样一个函数：
// 在 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);
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
// 在 s 中寻找以 s[l] 和 s[r] 为中心的最长回文串
string palindrome(string s, int l, int r) {
// 防止索引越界
while (l >= 0 && r < s.length()
&& s[l] == s[r]) {
// 双指针，向两边展开
l--; r++;
}
// 返回以 s[l] 和 s[r] 为中心的最长回文串
return s.substr(l + 1, r - l - 1);
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
# 在 s 中寻找以 s[l] 和 s[r] 为中心的最长回文串
def palindrome(s: str, l: int, r: int) -> str:
# 防止索引越界
while l >= 0 and r < len(s) and s[l] == s[r]:
# 双指针，向两边展开
l -= 1
r += 1
# 返回以 s[l] 和 s[r] 为中心的最长回文串
return s[l + 1 : r]
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
// 在 s 中寻找以 s[l] 和 s[r] 为中心的最长回文串
func palindrome(s string, l, r int) string {
// 防止索引越界
for l >= 0 && r < len(s) && s[l] == s[r] {
// 双指针，向两边展开
l--
r++
}
// 返回以 s[l] 和 s[r] 为中心的最长回文串
return s[l+1 : r]
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
// 在 s 中寻找以 s[l] 和 s[r] 为中心的最长回文串
var palindrome = function(s, l, 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，则相当于寻找长度为偶数的回文串。
那么回到最长回文串的问题，解法的大致思路就是：
for 0 <= i < len(s):
找到以 s[i] 为中心的回文串
找到以 s[i] 和 s[i+1] 为中心的回文串
更新答案
翻译成代码，就可以解决最长回文子串这个问题：
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;
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 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;
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def longestPalindrome(s: str) -> str:
res = ""
for i in range(len(s)):
# 以 s[i] 为中心的最长回文子串
s1 = palindrome(s, i, i)
# 以 s[i] 和 s[i+1] 为中心的最长回文子串
s2 = palindrome(s, i, i + 1)
# res = longest(res, s1, s2)
res = res if len(res) > len(s1) else s1
res = res if len(res) > len(s2) else s2
return res
def palindrome(s, l, r):
while (l >= 0 and r < len(s) and s[l] == s[r]):
l -= 1
r += 1
return s[l+1:r]
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func longestPalindrome(s string) string {
res := ""
for i := 0; i < len(s); i++ {
// 以 s[i] 为中心的最长回文子串
s1 := palindrome(s, i, i)
// 以 s[i] 和 s[i+1] 为中心的最长回文子串
s2 := palindrome(s, i, i + 1)
// res = longest(res, s1, s2)
if len(res) > len(s1) {
res = res
} else {
res = s1
}
if len(res) > len(s2) {
res = res
} else {
res = s2
}
}
return res
}
func palindrome(s string, l int, r int) string {
// 防止索引越界
for l >= 0 && r < len(s) && s[l] == s[r] {
// 向两边展开
l--
r++
}
// 返回以 s[l] 和 s[r] 为中心的最长回文串
return s[l+1 : r]
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var longestPalindrome = function(s) {
var res = "";
for (var i = 0; i < s.length; i++) {
// 以 s[i] 为中心的最长回文子串
var s1 = palindrome(s, i, i);
// 以 s[i] 和 s[i+1] 为中心的最长回文子串
var 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;
};
function palindrome(s, left, right) {
while (left >= 0 && right < s.length && s[left] == s[right]) {
left--;
right++;
}
return s.substring(left + 1, right);
}
🌟 代码可视化动画 🌟
你应该能发现最长回文子串使用的左右指针和之前题目的左右指针有一些不同：之前的左右指针都是从两端向中间相向而行，而回文子串问题则是让左右指针从中心向两端扩展。不过这种情况也就回文串这类问题会遇到，所以我也把它归为左右指针了。
到这里，数组相关的双指针技巧就全部讲完了，这些技巧的更多扩展延伸见 更多双指针经典高频题。
引用本文的题目
安装 我的 Chrome 刷题插件 点开下列题目可直接查看解题思路：
引用本文的文章
＿＿＿＿＿＿＿＿＿＿＿＿＿
《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复关键词「进群」可加入算法群；回复「全家桶」可下载配套 PDF 和刷题全家桶：
共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释