学习记录

• 时间： 4天（10.2 - 10.5）
• 题量： 9题
• 完成度： 9/9（全部AC，但错了很多次）

---

我的学习过程

这是我算法系统学习的第1-4天，从双指针开始。之前大二学过数据结构课程，这次是系统整理和练习。

Day01-02（10.2-10.3）： 双指针基础（5题）

• 移动零、两数之和、删除重复项、反转字符串、盛水容器
• 一开始完全不会，经常把索引和值搞混

Day02-03（10.3-10.4）： 双指针进阶（3题）

• 有效三角形、查找总价格、和≥target最短子数组
• 循环逻辑老是写错，调试花了很多时间

Day04（10.5）： 巩固练习（1题）

• 有序数组平方
• 犯了个严重错误：原地修改导致重复操作

---

双指针的核心概念（我的理解）

什么是双指针？

我的理解就是：用两个变量（left和right）指向数组的不同位置，通过移动它们来解决问题。

关键是要搞清楚：

• 两个指针怎么初始化？
• 两个指针怎么移动？
• 什么时候停止？

双指针的三种类型

通过这9道题，我发现双指针主要有3种：

1. 快慢指针（原地修改）

特点： 两个指针都从左边开始，一快一慢

适用： 需要原地修改数组的题目

模板：

int slow = 0;
for(int fast = 0; fast < n; fast++) {
    if(/* 满足条件 */) {
        nums[slow] = nums[fast];
        slow++;
    }
}
return slow;

我做过的题：

• 移动零（LeetCode 283）
• 删除重复项（LeetCode 26）

2. 对撞指针（有序数组）

特点： 一个指针从左边开始，一个从右边开始，往中间走

适用： 有序数组找两个数的和、积等

模板：

int left = 0, right = n - 1;
while(left < right) {
    if(/* 条件 */) {
        // 找到了
    } else if(/* sum太小 */) {
        left++;
    } else {
        right--;
    }
}

我做过的题：

• 两数之和（有序数组版）
• 查找总价格（剑指Offer）
• 盛水最多的容器（LeetCode 11）
• 有序数组平方（LeetCode 977）

3. 三指针（三数问题）

特点： 固定一个数，另外两个用对撞指针

适用： 三数之和、三角形等

模板：

for(int i = 0; i < n; i++) {
    // 固定nums[i]
    int left = i + 1, right = n - 1;
    while(left < right) {
        // 对撞指针找另外两个数
    }
}

我做过的题：

• 三数之和（LeetCode 15）⭐⭐⭐
• 有效三角形（LeetCode 611）

---

典型题目分类

类型1：快慢指针（原地修改）

LeetCode 283. 移动零

我的第一次错误：

if(right != 0) {  // ❌ right是索引，不是值！
    nums[slow++] = nums[right];
}

错在哪： 我把索引和值搞混了！right是第几个位置（索引），nums[right]才是那个位置的值。

正确写法：

if(nums[right] != 0) {  // ✅ nums[right]是值
    nums[slow++] = nums[right];
}

教训： 写代码前先问自己：我要的是第几个（索引）还是是什么（值）？

这个错误我后来又犯了好几次！

---

LeetCode 26. 删除有序数组中的重复项

这题比较顺，10分钟AC了。

核心思路： 快慢指针，fast遍历，slow记录不重复的位置。

int slow = 0;
for(int fast = 1; fast < n; fast++) {
    if(nums[fast] != nums[slow]) {
        nums[++slow] = nums[fast];
    }
}
return slow + 1;

关键点： nums[fast] != nums[slow] 判断是否重复。

---

类型2：对撞指针（有序数组）

LeetCode 1. 两数之和（有序数组版）

我的第一次错误：

for(; left < right; left++) {
    for(; left < right; right--) {  // ❌ 内层right不重置
        // ...
    }
}

问题： 第二次外循环时，right已经是0了，导致无限循环！

教训： 嵌套循环要注意变量重置。不过后来发现根本不需要两层循环，一个while就够了。

正确写法：

while(left < right) {
    int sum = nums[left] + nums[right];
    if(sum == target) return {left, right};
    else if(sum < target) left++;
    else right--;
}

---

LeetCode 11. 盛水最多的容器

我的第一次错误：

int calv(int a, int b) {  // ❌ C++不允许函数嵌套
    return height[a] * height[a] * (b - a);  // 高度平方了！
}

错误1： C++不支持在函数内部定义函数
错误2： 容积公式错了，高度不应该平方

正确公式： min(height[left], height[right]) * (right - left)

移动策略： 移动较短的那一边，因为容积受限于短边。

教训： 公式要理解清楚，不要想当然。

---

LeetCode 977. 有序数组的平方

这题我错了两次，印象深刻。

第一次错误：原地修改陷阱

nums[left] *= nums[left];  // 第一次平方
// ... 后面又判断
if(nums[left] < nums[right]) {
    nums[left] *= nums[left];  // 又平方了一次！-4→16→256
}

问题： 边修改边判断，导致重复平方。-4先变16，下次又把16当新数平方成256。

教训： 需要多次使用原值时，不能原地修改！要先保存或用新数组。

---

第二次错误：push_back方向错了

if(leftVal < rightVal) {
    ret.push_back(leftVal);  // ❌ push小的，结果是从大到小
    right--;
}

问题： 我以为push小的能保证递增，但忽略了两端本来就是最大值！

执行过程：

[-4, -1, 0, 3, 10]
两端：16 vs 100 → push(16) → [16]
两端：16 vs 9  → push(9)  → [16, 9]
两端：1 vs 9   → push(1)  → [16, 9, 1]
...
结果：[16, 9, 1, 0, 0]  // 从大到小，反了！

正确思路： 应该push大的，然后从后往前填充。

vector<int> ret(n);
for(int i = n - 1; i >= 0; i--) {
    if(leftVal > rightVal) {
        ret[i] = leftVal;  // 大的放后面
        left++;
    } else {
        ret[i] = rightVal;
        right--;
    }
}

教训： 双指针从两端往中间走，两端是极值（最大/最小），要搞清楚方向。

---

类型3：三指针（固定+对撞）

LeetCode 611. 有效三角形的个数

思路： 排序后，固定最大边，用双指针在左区间找另外两条边。

我的第一次错误：

for(; rightmax > 2;) {  // 外层循环
    while(left < right) {
        if(nums[left] + nums[right] > nums[rightmax]) {
            ret += right - left;
            right--;
            rightmax--;  // ❌ 在内层减，错了！
        }
    }
}

错误点：

1. rightmax-- 放错位置了，应该在外层循环
2. 每次固定新的rightmax后，没有重新初始化left和right
3. 循环条件应该是 rightmax >= 2

正确写法：

for(int rightmax = n-1; rightmax >= 2; rightmax--) {
    int left = 0;
    int right = rightmax - 1;  // ⚠️ 每次都重新初始化
    
    while(left < right) {
        if(nums[left] + nums[right] > nums[rightmax]) {
            ret += right - left;  // 一次性统计所有满足的三角形
            right--;
        } else {
            left++;
        }
    }
}

为什么 ret += right - left？
因为当 nums[left] + nums[right] > nums[rightmax] 时：

• nums[left] 和 nums[right] 能构成 ✅
• nums[left+1] 和 nums[right] 也能（因为更大） ✅
• nums[left+2] 和 nums[right] 也能 ✅
• … 一共有 right - left 个！

教训： 指针在外层循环时要重新初始化。

---

LeetCode 15. 三数之和 ⭐⭐⭐⭐⭐

这题是双指针的集大成者，我错了好几次。

错误1：又是索引vs值

int target = -c;  // ❌ c是索引

应该是：int target = -nums[c];

错误2：push_back语法错了

ret.push_back(nums[left], nums[right], nums[c]);  // ❌ 不能传3个参数

应该是：ret.push_back({nums[left], nums[right], nums[c]});

错误3：没有去重

三数之和最难的是去重！有3个去重点：

// 去重点1：固定数去重
if(i > 0 && nums[i] == nums[i-1]) continue;

// 去重点2：找到答案后，left去重
while(left < right && nums[left] == nums[left+1]) left++;

// 去重点3：找到答案后，right去重
while(left < right && nums[right] == nums[right-1]) right--;

教训： 三数之和的去重很细节，要理解为什么这样去重。

---

我踩的坑（总结）

坑1：索引 vs 值混淆（犯了5次！）

这是我最常犯的错误！

// ❌ 错误写法：
if(right != 0)           // right是索引
target = -c              // c是索引
while(hash[right] > 1)   // right是索引

// ✅ 正确写法：
if(nums[right] != 0)           // nums[right]是值
target = -nums[c]              // nums[c]是值
while(hash[s[right]] > 1)      // s[right]是字符（值）

记忆口诀：

写代码前先问自己：“我要的是第几个（索引）还是是什么（值）？”

发生在：

• 移动零
• 两数之和
• 无重复字符（后面滑动窗口）
• 三数之和

坑2：循环逻辑问题

错误示例1：无限循环

for(; left < right; left++) {
    for(; left < right; right--) {  // right不重置
        // 第二次外循环，right=0了，死循环
    }
}

错误示例2：变量在错误位置更新

while(left < right) {
    if(condition) {
        ret += right - left;
        rightmax--;  // ❌ 不应该在这里
    }
}

坑3：C++语法问题

问题1：函数嵌套

int func() {
    int inner() { }  // ❌ C++不允许
}

问题2：vector初始化

vector<int> ret = [];  // ❌ 错误
vector<int> ret {};    // ✅ 正确
vector<int> ret;       // ✅ 正确

问题3：push_back语法

ret.push_back(a, b, c);     // ❌ 错误
ret.push_back({a, b, c});   // ✅ 正确（vector<vector<int>>）

坑4：原地修改陷阱

nums[left] *= nums[left];  // 第一次平方
// ... 后面再判断
if(nums[left] < nums[right]) {
    nums[left] *= nums[left];  // 又平方了！
}

教训： 需要多次使用原值时，要先保存或用新数组！

坑5：双指针方向问题

// 从两端往中间，两端是最大值
if(leftVal < rightVal) {
    ret.push_back(leftVal);  // ❌ push小的，结果从大到小
}

教训： 双指针从两端往中间，要搞清楚极值在哪边。

---

我的薄弱环节

• 三指针的去重逻辑：三数之和的3个去重点还不太熟练，需要多练
• 复杂循环的控制：嵌套循环容易写错，尤其是指针重置
• C++基础语法：函数定义、vector初始化、push_back还不够熟

---

下一步计划

• 继续比特课程，下一步应该是前缀和或二分查找
• 三数之和要再复习一次，尤其是去重部分
• 以后写代码前，先问自己：要索引还是值？

---

典型模板总结

快慢指针模板

int slow = 0;
for(int fast = 0; fast < n; fast++) {
    if(/* 条件 */) {
        nums[slow++] = nums[fast];
    }
}
return slow;

对撞指针模板

int left = 0, right = n - 1;
while(left < right) {
    if(/* 条件 */) {
        // 找到了
    } else if(/* sum太小 */) {
        left++;
    } else {
        right--;
    }
}

三指针模板

for(int i = 0; i < n; i++) {
    if(i > 0 && nums[i] == nums[i-1]) continue;  // 去重
    
    int left = i + 1, right = n - 1;
    while(left < right) {
        // 对撞指针
        if(满足) {
            // 记录结果
            // left和right去重
            left++; right--;
        } else if(sum < target) {
            left++;
        } else {
            right--;
        }
    }
}

---

我的理解

双指针的本质：

• 就是用两个变量遍历数组，通过控制它们的移动来减少循环层数
• 单指针暴力法是O(n²)，双指针能优化到O(n)

三种类型的选择：

1. 快慢指针： 题目要求原地修改，不能用额外空间 → 用快慢指针
2. 对撞指针： 数组有序 + 找两个数的和/差/积 → 用对撞指针
3. 三指针： 找三个数满足某条件 → 固定一个 + 对撞指针找另外两个

移动策略：

• 快慢指针：fast每次都动，slow按条件动
• 对撞指针：比较后，小了动left，大了动right
• 三指针：先去重，再对撞

什么时候复习：

• 三数之和要再做一遍（去重还不熟）
• 有序数组平方要再做一遍（方向容易错）
• 其他题暂时不用复习，模板记住了

---

写于： 2025年10月8日
刷题进度： 0题 → 9题
下个专题： 滑动窗口（已完成8题）