学习方向： C++ / 数据结构基础
训练阶段： Coding Day 5
今日主题： 双指针覆盖法、原地修改数组、连续区间统计、当前状态与历史最优状态
一、双指针原地删除数组中的零元素
1. 题目要求
已知数组：
int arr[6] = {4, 0, 7, 0, 2, 9};
使用双指针覆盖法，将所有非零元素移动到数组前面，同时保持它们原来的顺序。
预期输出：
处理后的数组：4 7 2 9
有效元素个数：4
要求使用 read 和 write 两个指针，不创建额外数组。
2. 我的原始代码（独立完成）
#include <iostream>
using namespace std;
int main()
{
int arr[6] = {4, 0, 7, 0, 2, 9};
int* read = arr;
int* write = arr;
for (int i = 0; i < 6; i++)
{
if (*read != 0)
{
*write = *read;
write++;
}
read++;
}
int validCount = write - arr;
cout << "处理后的数组：";
for (int i = 0; i < validCount; i++)
{
cout << arr[i] << " ";
}
cout << endl;
cout << "有效元素个数：" << validCount << endl;
}
检查结果：完全正确，无须修改核心算法。
3. 双指针的工作原理
这道题最关键的是理解两个指针承担不同职责。
int* read = arr;
int* write = arr;
最开始，两个指针都指向数组第一个元素。
但它们的移动规则不同。
read：读取指针
负责依次检查数组中的每个元素。
read++;
无论当前元素是不是零，read 都需要移动。
write：写入指针
负责指出下一个非零元素应该写入的位置。
if (*read != 0)
{
*write = *read;
write++;
}
只有当前元素不等于零时，才进行写入并移动 write。
4. 程序执行过程
初始数组：
下标： 0 1 2 3 4 5
元素： 4 0 7 0 2 9
| i | 读取值 | 写入操作 | write 移动后的下标 |
|---|---|---|---|
| 0 | 4 | arr[0] = 4 | 1 |
| 1 | 0 | 跳过 | 1 |
| 2 | 7 | arr[1] = 7 | 2 |
| 3 | 0 | 跳过 | 2 |
| 4 | 2 | arr[2] = 2 | 3 |
| 5 | 9 | arr[3] = 9 | 4 |
最终数组实际变成：
4 7 2 9 2 9
但只有前四个元素有效：
4 7 2 9
这一点需要特别注意。
双指针覆盖并不会改变数组的物理长度。
原数组仍然有六个元素，只是我们通过一个变量记录其中有多少个元素属于有效数据。
5. 为什么 write - arr 可以计算有效长度？
我使用：
int validCount = write - arr;
这个表达式涉及指针相减。
对于同一个数组中的两个指针，它们相减得到的是相隔的元素数量，而不是字节数量。
例如：
int arr[6];
int* p = arr + 4;
cout << p - arr;
结果为：
4
因为 p 和数组首元素相隔四个 int 元素。
本题中，write 每保存一个非零元素，就前进一次。
最终前进四次，因此：
validCount = 4;
6. 与 Day 4 的对比
11 月 12 日第一次接触双指针原地删除时，我最初想到的是使用左移操作：
*(p + i) = *(p + i + 1);
即发现零元素后，把后面的元素整体向前移动。
但当时没有正确处理读取位置、删除后的位置变化和有效长度，导致无法独立完成。
今天已经能够独立使用两个指针解决这个问题。
本题的核心收获：
read负责遍历全部元素。write负责管理有效数据的写入位置。*write = *read是复制赋值，不是交换。read++每次循环都执行。write++只在满足保留条件时执行。write - arr可以计算最终有效元素数量。
这道题使用一次遍历，时间复杂度为 O(n)，额外空间复杂度为 O(1)。
掌握状态：已能独立实现，后续需要通过变式题检验。
二、寻找最长连续正数区间
1. 题目要求
已知数组：
int arr[10] = {3, 5, -2, 4, 7, 9, -1, 2, 6, -3};
要求使用一个 for 循环和指针遍历，找出最长的一段连续正数。
预期输出：
最长连续正数长度：3
起始下标：3
结束下标：5
数组中的连续正数区间分别为：
3 5 长度 2
4 7 9 长度 3
2 6 长度 2
最长的是 4、7、9。
2. 我的原始代码（未完成）
#include <iostream>
using namespace std;
int main()
{
int arr[10] = {3, 5, -2, 4, 7, 9, -1, 2, 6, -3};
int* p = arr;
int value = 0;
int start_subscript = 0;
int over_subscript = 0;
int longest_index = 0;
int index = 0;
for (int i = 0; i < 10; i++)
{
value = *p;
if (value > 0 && start_subscript <= 0)
{
start_subscript = i;
}
if (value < 0)
{
over_subscript = i;
start_subscript = 0;
}
p++;
}
index = over_subscript - start_subscript;
if (index > longest_index)
{
longest_index = index;
}
cout << "最长连续正数长度：" << longest_index << endl;
cout << "起始下标：" << start_subscript << endl;
cout << "结束下标：" << over_subscript << endl;
return 0;
}
这道题没有独立完成，但我最初已经想到通过起始下标、结束下标来描述连续区间。
3. 错误分析
错误一：用下标 0 判断是否开始新的一段
原代码：
if (value > 0 && start_subscript <= 0)
问题在于，数组下标 0 本身就是合法的起始位置。
所以不能简单通过 start_subscript <= 0 判断当前是否处于连续区间中。
更可靠的方式是通过当前连续长度判断：
if (currentLength == 0)
{
currentStart = i;
}
当当前长度为零，说明现在没有正在延续的正数区间。
如果此时遇到正数，就记录为新一段的起点。
错误二：将负数下标当作结束下标
原代码：
if (value < 0)
{
over_subscript = i;
}
假设数组是：
3 5 -2
连续正数区间是：
起始下标：0
结束下标：1
但执行到负数 -2 时，i = 2。
这时将 i 保存为结束下标，就会多记录一个位置。
错误三：没有在循环中更新最长记录
原代码：
index = over_subscript - start_subscript;
if (index > longest_index)
{
longest_index = index;
}
这段判断位于循环外，因此只执行一次。
但数组中可能存在多个连续正数区间，需要不断比较。
例如：
3 5 长度 2
4 7 9 长度 3
2 6 长度 2
我们应该在遍历过程中不断更新已经找到的最长长度。
错误四：当前区间与历史最长区间混淆
这是这道题最主要的问题。
我只考虑了如何记录当前区间的起点和终点，却没有考虑：
如果当前区间结束，之前找到的最长区间应该怎样保留下来？
因此需要分别记录当前状态和历史最优状态。
4. 修正后的完整代码（参考学习）
#include <iostream>
using namespace std;
int main()
{
int arr[10] = {3, 5, -2, 4, 7, 9, -1, 2, 6, -3};
int* p = arr;
int currentLength = 0;
int currentStart = 0;
int longestLength = 0;
int bestStart = -1;
int bestEnd = -1;
for (int i = 0; i < 10; i++)
{
int value = *p;
if (value > 0)
{
if (currentLength == 0)
{
currentStart = i;
}
currentLength++;
if (currentLength > longestLength)
{
longestLength = currentLength;
bestStart = currentStart;
bestEnd = i;
}
}
else
{
currentLength = 0;
}
p++;
}
cout << "最长连续正数长度：" << longestLength << endl;
cout << "起始下标：" << bestStart << endl;
cout << "结束下标：" << bestEnd << endl;
return 0;
}
5. 当前状态与历史最优状态
这道题最重要的新知识，是如何使用两组变量管理不同状态。
| 变量 | 保存的内容 |
|---|---|
| currentLength | 当前正在连续出现的正数数量 |
| currentStart | 当前连续区间的起始下标 |
| longestLength | 已经发现的历史最长长度 |
| bestStart | 历史最长区间的起始下标 |
| bestEnd | 历史最长区间的结束下标 |
例如：
3 5 -2 4 7 9 -1 2 6 -3
当遍历到 -1 时，前面连续的 4、7、9 已经结束。
此时：
currentLength = 0;
但是：
longestLength = 3;
bestStart = 3;
bestEnd = 5;
历史最优结果必须保留。
如果后面出现更长的正数区间，才更新历史记录。
6. 为什么在正数分支内部比较最长长度？
if (currentLength > longestLength)
{
longestLength = currentLength;
bestStart = currentStart;
bestEnd = i;
}
这段代码的作用是：
每读取一个正数，当前连续长度就增加一次。
如果新长度超过此前的历史最长长度，就立即更新记录。
这样不必专门等到遇到负数时才计算区间长度。
另外，即使数组最后一个元素是正数，也能正确记录以数组末尾结束的最长区间。
7. 本题总结
这道题没有独立完成。
但通过讲解，已经初步理解了：
- 如何判断新的一段连续区间开始。
- 遇到非正数时为什么要清零当前长度。
- 为什么历史最长记录不能清零。
- 如何在遍历过程中更新最长长度和起止下标。
- 为什么当前状态和历史最优状态需要分别保存。
掌握状态：经讲解理解，仍需独立变式练习。
三、寻找最长连续偶数区间
1. 题目要求
已知数组：
int arr[11] = {2, 4, 6, 1, 8, 10, 12, 14, 3, 16, 18};
要求找到最长连续偶数区间，输出长度、起始下标与结束下标。
预期输出：
最长连续偶数长度：4
起始下标：4
结束下标：7
这道题与第二题的算法结构相似，但判断条件改成了偶数。
2. 我的原始代码（独立完成，存在一处错误）
#include <iostream>
using namespace std;
int main()
{
int arr[11] = {2, 4, 6, 1, 8, 10, 12, 14, 3, 16, 18};
int* p = arr;
int currentLength = 0;
int currentStart = 0;
int longestLength = 0;
int bestStart = -1;
int bestEnd = -1;
for (int i = 0; i < 10; i++)
{
int value = *p;
if (value % 2 == 0)
{
if (currentLength == 0)
{
currentStart = i;
}
currentLength++;
if (currentLength > longestLength)
{
longestLength = currentLength;
bestStart = currentStart;
bestEnd = i;
}
}
else
{
currentLength = 0;
}
p++;
}
cout << "最长连续偶数长度：" << longestLength << endl;
cout << "起始下标：" << bestStart << endl;
cout << "结束下标：" << bestEnd << endl;
}
这次算法结构正确，唯一的问题是循环边界。
3. 错误：遗漏最后一个数组元素
我定义了：
int arr[11] = {2, 4, 6, 1, 8, 10, 12, 14, 3, 16, 18};
但循环写成：
for (int i = 0; i < 10; i++)
这只会遍历下标 0～9，遗漏下标 10 的元素 18。
正确写法：
for (int i = 0; i < 11; i++)
本次遗漏最后一个元素没有改变最长区间的结果，是因为最后一段连续偶数区间只有两个元素。
但是，如果最后一段更长，程序就可能输出错误答案。
这说明：
程序对当前测试数据输出正确，不代表算法对所有合法输入都正确。
4. 修正后的完整代码
#include <iostream>
using namespace std;
int main()
{
int arr[11] = {2, 4, 6, 1, 8, 10, 12, 14, 3, 16, 18};
int* p = arr;
int currentLength = 0;
int currentStart = 0;
int longestLength = 0;
int bestStart = -1;
int bestEnd = -1;
for (int i = 0; i < 11; i++)
{
int value = *p;
if (value % 2 == 0)
{
if (currentLength == 0)
{
currentStart = i;
}
currentLength++;
if (currentLength > longestLength)
{
longestLength = currentLength;
bestStart = currentStart;
bestEnd = i;
}
}
else
{
currentLength = 0;
}
p++;
}
cout << "最长连续偶数长度：" << longestLength << endl;
cout << "起始下标：" << bestStart << endl;
cout << "结束下标：" << bestEnd << endl;
return 0;
}
5. 这次正确掌握了什么？
相比第二题，第三题已经能够独立完成：
if (currentLength == 0)
{
currentStart = i;
}
用于记录新连续区间的起点。
能够正确使用：
currentLength++;
更新当前连续长度。
并且能够正确使用：
if (currentLength > longestLength)
{
longestLength = currentLength;
bestStart = currentStart;
bestEnd = i;
}
更新历史最长记录。
在遇到奇数时，也知道只需要清零：
currentLength = 0;
而不能清零历史最优结果。
这表明已经能够将第二题刚学过的状态管理算法应用到相似问题中。
6. 延伸知识：> 与 >= 的区别
完成第三题后，还讨论了一个问题：
如果把：
if (currentLength > longestLength)
修改成：
if (currentLength >= longestLength)
会发生什么？
答案是：如果存在多段长度相同的最长区间，使用 >= 会最终保留最后一段。
原因在于：
> 只有发现严格更长的区间时才更新历史记录。
>= 则会在长度相等时也更新历史记录。
例如：
int arr[7] = {2, 4, 1, 6, 8, 3, 10};
两段长度为 2 的连续偶数区间：
第一段：下标 0～1
第二段：下标 3～4
如果使用：
currentLength > longestLength
最终保留第一段。
如果使用：
currentLength >= longestLength
最终保留第二段。
这说明比较条件不仅决定何时更新变量，还可能影响算法在多个相同最优结果之间的选择。
7. 本题总结
第三题基本独立完成，只有一处数组长度判断错误。
与第二题相比，已经能够独立使用当前状态与历史最优状态解决连续区间问题。
但由于两道题的算法结构比较接近，暂时不能认为已经完全掌握此类算法，还需要不同形式的综合测试。
四、今日核心知识总结
1. 双指针覆盖法
if (*read != 0)
{
*write = *read;
write++;
}
read++;
核心规则：
- 读取指针每次循环都移动。
- 写入指针只在满足条件时移动。
- 覆盖不等于交换，也不等于释放内存。
- 有效数据数量可以通过指针位置差计算。
2. 连续区间状态管理
if (满足连续条件)
{
if (currentLength == 0)
{
currentStart = i;
}
currentLength++;
if (currentLength > longestLength)
{
longestLength = currentLength;
bestStart = currentStart;
bestEnd = i;
}
}
else
{
currentLength = 0;
}
核心规则：
- 当前状态随着遍历不断变化。
- 连续区间被打断时，当前长度清零。
- 历史最长记录只在刷新最优结果时更新。
- 当前区间结束不代表历史记录应该清零。
3. 指针的读取与修改
int value = *p;
读取指针指向位置的值。
*p = 10;
修改指针指向位置的数据。
p++;
让指针指向下一个同类型元素。
*write = *read;
将读取位置的值复制到写入位置。
write - arr;
计算同一数组中两个指针相隔的元素数量。
4. 循环边界
本次第三题再次出现了数组长度与循环边界不一致的问题。
对于具有 n 个元素的数组，一般使用：
for (int i = 0; i < n; i++)
如果数组长度可能发生修改，尽量不要在多个地方手动重复写死长度。
5. 算法复杂度
今天学习的两种主要算法都可以通过一次遍历完成。
| 算法 | 时间复杂度 | 额外空间 |
|---|---|---|
| 双指针覆盖删除 | O(n) | O(1) |
| 最长连续区间 | O(n) | O(1) |
两者虽然应用场景不同，但都依赖循环过程中维护少量状态变量。
五、与前四次 Coding 训练的对比
| 日期 | 训练内容 | 主要进展 |
|---|---|---|
| 11 月 8 日 · Day 1 | 循环、累加、基础指针 | 开始理解指针与数组 |
| 11 月 10 日 · Day 2 | 最值查找、双指针交换 | 独立完成数组反转 |
| 11 月 11 日 · Day 3 | 多循环与综合统计 | 改善循环组织与变量更新 |
| 11 月 12 日 · Day 4 | 递推、数组原地删除 | 独立使用递推，删除算法未掌握 |
| 11 月 15 日 · Day 5 | 双指针覆盖、连续区间 | 独立完成覆盖法，能够迁移连续区间算法 |
今天最明显的进步
第一：掌握了双指针覆盖法的基础实现。
在 Day 4 中未能完成的删除零元素题，今天已经能够独立编写。
说明对双指针读写职责的理解有所提高。
第二：开始理解当前状态和历史最优状态。
第二题最初无法完成，但经过讲解后，第三题已经能够使用相同思想独立完成相似任务。
第三：可以初步理解算法中的比较策略。
能够判断 > 和 >= 在存在相同最长区间时，会使程序保留不同的结果。
目前仍然存在的问题
1. 循环边界偶尔出错。
第三题数组长度为 11，但只遍历了 10 个元素。
2. 连续区间算法的独立设计仍需加强。
第三题是第二题的直接变式，仍需要在没有参考结构的情况下再练习。
3. 指针与状态变量结合的复杂问题仍有难度。
在简单数组遍历与覆盖中已经有所进步，但涉及起点、终点和最长长度等多个变量时，还需要先分析变量之间的关系。
4. 需要加强独立调试。
以后不能仅根据示例输出正确就认为程序完全正确，还需要测试边界情况与其他输入。
六、下一阶段学习计划
下一次将进行 Coding Day 6：数组、指针与状态管理综合训练。
重点安排三个方向。
第一：双指针算法变式
不再直接重复删除零元素，而是改变筛选条件，检验是否真正理解读写指针的职责。
第二：连续区间独立设计
不提供完整代码框架，要求先自行设计需要使用哪些状态变量，再实现算法。
第三：边界条件测试
专门测试数组长度、全部满足条件、全部不满足条件、连续区间位于数组首尾等情况。
如果能够稳定完成这些练习，下一阶段再开始单链表的基础实现。
七、今日总结
今天共进行了三道 C++ Coding 练习。
第一题双指针覆盖法完全独立完成，说明前几天未掌握的知识已经取得了实际进步。
第二题最长连续正数区间没有独立完成，但通过分析，逐步理解了当前连续状态与历史最长状态之间的区别。
第三题最长连续偶数区间基本独立完成，只出现一处循环边界错误，并进一步理解了不同更新条件对最终算法结果的影响。
目前正在从能够使用 C++ 语法，逐渐过渡到能够根据问题设计变量、管理状态并组织算法。
接下来应继续重点加强独立设计能力，尤其是复杂循环中的变量状态管理和边界判断。
学习原则：独立分析 → 编写代码 → 调试验证 → 记录错误 → 变式巩固。