双指针法

一、相向双指针

1. 前提条件

相向双指针一般用于：

数组、字符串、链表这类线性结构。

最常见是数组和字符串。

它的基本形式是：

left 从左边开始；
right 从右边开始；
两个指针向中间靠拢。

代码形式：

int left = 0;
int right = n - 1;

while (left < right) {
// 处理逻辑
}
2. 核心概念

相向双指针的核心不是“两个指针乱走”，而是：

每移动一次指针，都能排除一部分不可能的答案。

所以它一般要求题目中有某种规律，例如：

1. 数组有序
2. 左右边界决定答案
3. 面积受短板限制
4. 字符串左右对称
5. 左右最大值决定当前位置结果
6. 固定模板
   int left = 0;
   int right = n - 1;

while (left < right) {
if (条件1) {
left++;
} else if (条件2) {
right--;
} else {
// 找到答案或者更新答案
}
}

更通用地说：

1. 初始化 left 和 right
2. while(left < right)
3. 根据当前 left 和 right 计算结果
4. 根据规律移动其中一个指针
5. 常见移动规律
   情况一：有序数组求和
   sum 太小，left++
   sum 太大，right--
   情况二：盛最多水的容器
   左边短，left++
   右边短，right--
   情况三：接雨水
   左边低，处理 left
   右边低，处理 right
   情况四：判断回文
   左右相等，left++，right--
   左右不等，直接失败
6. 易错点
   易错点 1：不是所有数组题都能用双指针

如果没有规律，不能乱用。

比如无序数组中直接这样写是错的：

int left = 0;
int right = numsSize - 1;

然后直接判断：

nums[left] + nums[right]

因为原数组无序，left++ 或 right-- 没有明确意义。

易错点 2：循环条件一般是 left < right

因为相向双指针通常要求两个不同位置。

while (left < right)

如果写成：

while (left <= right)

可能会把同一个元素用两次。

易错点 3：每轮至少移动一个指针

否则会死循环。

错误：

while (left < right) {
int sum = nums[left] + nums[right];

if (sum == target) {
    // 忘记 return 或 break
}

}
二、LeetCode 1：两数之和

1. 前提条件

题目给：
数组 nums
目标值 target
要求：

找两个不同位置的数，使它们的和等于 target。

返回：

这两个数在原数组中的下标。

注意重点：

返回的是原数组下标，不是排序后的下标。
2. 核心概念

LeetCode 第一题本身最常用的方法是：

哈希表

但是如果想用相向双指针，也可以。

不过要满足一个前提：

数组必须有序。

所以双指针版本的思路是：

先排序，再用 left 和 right 找 target。

但是排序会打乱下标，所以还要保存：

原始下标 index。
3. 为什么排序后可以双指针？

假设排序后：

nums = [2, 7, 11, 15]
target = 9

初始化：

left 指向最小值 2
right 指向最大值 15

当前和：

2 + 15 = 17

太大了，所以要让和变小。

因为数组有序，右边数字更大，所以移动：

right--;

如果当前和太小：

sum < target

说明要让和变大，所以移动：

left++;

所以规律是：

sum < target，left++
sum > target，right--
sum == target，找到答案
4. 固定模板
int left = 0;
int right = numsSize - 1;

while (left < right) {
int sum = nums[left] + nums[right];

if (sum == target) {
    // 找到答案
} else if (sum < target) {
    left++;
} else {
    right--;
}

}

但是第一题不能直接这么写，因为要返回原下标。

所以实际需要保存：

struct Element {
int val;
int index;
};

其中：

val：元素的值
index：元素在原数组中的下标
5. C 语言模板：排序 + 双指针
#include <stdlib.h>

struct Element {
int val;
int index;
};

int cmp(const void* a, const void* b) {
const struct Element* x = (const struct Element*)a;
const struct Element* y = (const struct Element*)b;

if (x->val < y->val) {
    return -1;
} else if (x->val > y->val) {
    return 1;
} else {
    return 0;
}

}

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
struct Element* arr = malloc(numsSize * sizeof(struct Element));

for (int i = 0; i < numsSize; i++) {
    arr[i].val = nums[i];
    arr[i].index = i;
}

qsort(arr, numsSize, sizeof(struct Element), cmp);

int left = 0;
int right = numsSize - 1;

int* result = malloc(2 * sizeof(int));

while (left < right) {
    int sum = arr[left].val + arr[right].val;

    if (sum == target) {
        result[0] = arr[left].index;
        result[1] = arr[right].index;
        *returnSize = 2;

        free(arr);
        return result;
    } else if (sum < target) {
        left++;
    } else {
        right--;
    }
}

free(arr);
free(result);
*returnSize = 0;
return NULL;

}
6. 易错点
易错点 1：不能排序后直接返回 left 和 right

错误：

result[0] = left;
result[1] = right;

因为这是排序后的下标，不是原数组下标。

应该返回：

result[0] = arr[left].index;
result[1] = arr[right].index;
易错点 2：比较函数不要直接相减

不推荐：

return x->val - y->val;

因为可能整数溢出。

推荐：

if (x->val < y->val) return -1;
if (x->val > y->val) return 1;
return 0;
易错点 3：返回数组必须 malloc

LeetCode 提示：

/**

• Note: The returned array must be malloced, assume caller calls free().
  */

意思是：

返回的数组必须是 malloc 申请的。

错误：

int result[2];
return result;

因为局部数组函数结束后就失效了。

正确：

int* result = malloc(2 * sizeof(int));
return result;
7. 复杂度

排序 + 双指针：

时间复杂度：O(n log n)
空间复杂度：O(n)

如果用哈希表：

时间复杂度：O(n)
空间复杂度：O(n)

所以第一题最优解通常是哈希表，但排序双指针很适合练相向双指针思想。

8. 题型总结

两数之和的双指针规律：

前提：数组有序。
目标：找两个数的和等于 target。
移动：
sum < target，说明和太小，left++
sum > target，说明和太大，right--
sum == target，找到答案

一句话：

两数之和的相向双指针，本质是利用有序数组的单调性。
三、LeetCode 11：盛最多水的容器

1. 前提条件

题目给你一个数组：height[i]

表示第 i 个位置有一条高度为 height[i] 的竖线。

要你选择两条竖线，使它们和 x 轴围成的容器最多能装多少水。

2. 核心概念

选择两个位置：

left 和 right

容器的宽度是：

right - left

容器的高度取决于短板：

min(height[left], height[right])

所以面积是：

面积 = 宽度 × 短板高度

也就是：

area = (right - left) * min(height[left], height[right]);

注意：

容器能装多少水，不取决于高的那边，而取决于矮的那边。
3. 为什么用相向双指针？

一开始：

left = 0;
right = heightSize - 1;

此时宽度最大。

然后每次计算当前面积，更新最大值。

关键是移动哪一边。

如果：

height[left] < height[right]

说明左边是短板。

此时如果移动右边：

宽度变小；
短板仍然可能是左边；
面积很难变大。

所以应该移动短板：

left++;

同理，如果右边更短：

right--;
4. 固定模板
int maxArea(int* height, int heightSize) {
int left = 0;
int right = heightSize - 1;
int max = 0;

while (left < right) {
    int width = right - left;

    int h;
    if (height[left] < height[right]) {
        h = height[left];
    } else {
        h = height[right];
    }

    int area = width * h;

    if (area > max) {
        max = area;
    }

    if (height[left] < height[right]) {
        left++;
    } else {
        right--;
    }
}

return max;

}
5. 移动规律
左边短，left++
右边短，right--
一样高，移动哪边都可以

口诀：谁短移动谁。
6. 为什么不是移动高的那边？

假设：

height[left] = 3
height[right] = 10

当前面积的高度只能是：3

因为短板是左边。

如果移动右边，宽度会变小，而左边短板还是 3，所以不可能通过移动右边突破短板限制。

真正可能让面积变大的方式是：

移动短板，尝试找到更高的边界。
7. 易错点
易错点 1：面积高度取短板

错误：

area = (right - left) * height[right];

或者：

area = (right - left) * height[left];

正确：

area = (right - left) * min(height[left], height[right]);
易错点 2：移动高的那边

错误理解：谁高移动谁。

正确：谁短移动谁。

因为短板决定容器高度。

易错点 3：先移动再算面积

应该先用当前 left 和 right 算面积，再移动指针。

正确顺序：

1. 计算当前面积
2. 更新最大值
3. 移动短板
4. 复杂度
   时间复杂度：O(n)
   空间复杂度：O(1)

因为 left 和 right 一共最多走 n 次。

9. 题型总结

盛最多水的容器：

目标：选两个柱子，使容器面积最大。
面积：宽度 × 短板高度。
移动：谁短移动谁。
原因：只有移动短板，才可能提高容器高度。

一句话：第 11 题的相向双指针，本质是利用“短板决定容量”的规律排除答案。

四、LeetCode 42：接雨水

1. 前提条件

题目给一个数组：

height[i]

表示每个位置的柱子高度。

下雨后，柱子之间可能会接住水。

要求：

计算总共能接多少水。
2. 核心概念

对于某个位置 i，它能接多少水，取决于：

左边最高的柱子 leftMax
右边最高的柱子 rightMax

当前位置最多能接：

min(leftMax, rightMax) - height[i]

如果这个值小于 0，就说明接不了水。

核心规律：

一个位置能接水，必须左右两边都有比它高的边界。
3. 为什么可以用双指针？

普通思路是：

对每个位置分别找左边最高和右边最高。

这样比较麻烦。

双指针做法是同时维护：

leftMax：从左边走到当前位置遇到的最高柱子
rightMax：从右边走到当前位置遇到的最高柱子

每次处理较低的一边。

原因：

如果 height[left] < height[right]，
说明 left 这一侧的接水量主要由 leftMax 决定；
右边至少有一个比它高的边界存在。

所以可以放心处理 left。

同理，如果右边低，就处理 right。

4. 固定模板
   int trap(int* height, int heightSize) {
   int left = 0;
   int right = heightSize - 1;

   int leftMax = 0;
   int rightMax = 0;

   int water = 0;

   while (left < right) {
   if (height[left] < height[right]) {
   if (height[left] >= leftMax) {
   leftMax = height[left];
   } else {
   water += leftMax - height[left];
   }

        left++;
    } else {
        if (height[right] >= rightMax) {
            rightMax = height[right];
        } else {
            water += rightMax - height[right];
        }
   
        right--;
    }
   

   }

   return water;
   }
   如果 height[left] < height[right]：
   说明右边墙更高，左边能不能接水由 leftMax 决定。
   所以处理 left。

如果 height[left] >= height[right]：
说明左边墙更高，右边能不能接水由 rightMax 决定。
所以处理 right。
5. 移动规律
左边低，处理 left，然后 left++
右边低，处理 right，然后 right--

不是简单地“谁短移动谁”，而是：

谁低，说明谁那边的边界更确定，先处理谁。
6. 接雨水和盛水容器的区别
题目 目标 计算方式 移动规律
第 11 题 盛最多水 选两个柱子 算一个容器面积 谁短移动谁
第 42 题 接雨水 计算所有坑的水 每个位置累加水量 谁低处理谁

最关键区别：

第 11 题是选两个边界。
第 42 题是每个位置都要算。
7. 易错点
易错点 1：把第 11 题和第 42 题混在一起

第 11 题：

只看两个柱子形成的面积。

第 42 题：

看所有柱子之间能积多少水。
易错点 2：接雨水不是直接算左右两边高度

错误理解：

当前位置水量 = 左边柱子高度 - 当前高度

正确是：

当前位置水量 = min(左边最高, 右边最高) - 当前高度
易错点 3：忘记维护 leftMax 和 rightMax

如果只看当前左右柱子：

height[left]
height[right]

是不够的。

接雨水看的是：

左边历史最高
右边历史最高

所以要维护：

leftMax
rightMax
8. 复杂度
时间复杂度：O(n)
空间复杂度：O(1)
9. 题型总结

接雨水：

目标：计算所有位置能接的水量总和。
核心：每个位置能接多少水，取决于左右最大边界的较小值。
双指针：维护 leftMax 和 rightMax。
移动：哪边低，先处理哪边。

第 42 题的相向双指针，本质是用 leftMax 和 rightMax 动态确定每个位置的接水量。
五、总结：相向双指针题型对比
题型 前提 计算什么 移动谁
两数之和 有序数组 两数和 sum 小 left++，sum 大 right--
盛最多水 左右边界成容器 面积最大值 谁短移动谁
接雨水 左右最大边界 每个位置水量 谁低处理谁
回文判断 左右对称 字符是否相等 相等一起移动，不等返回失败