前言

🚀 你好，欢迎来到《编程闯关记》！
这里是算法与数据结构的实战基地，也是你从“暴力解法”到“最优解”的进化场。

🔍 专栏初衷：

用清晰的图解 + 多语言代码（Python/Java/C++/C），拆解每道题背后的逻辑。
不只讲“怎么做”，更讲“为什么”——从题目分析、边界条件到复杂度优化。
适合想夯实基础或突击面试的你，尤其针对LeetCode/牛客高频题！

💡 如何使用本专栏：
1️⃣ 先独立思考：尝试自己写出第一版代码（哪怕很烂）。
2️⃣ 对比解法：看看我的思路和你的差异，吸收优化技巧。
3️⃣ 举一反三：每篇末尾会附相似题目链接，趁热打铁。

📌 坚持打卡：
算法没有捷径，但正确的方法能让你少走弯路。每天15分钟，和我一起用代码雕刻思维！

（正文开始👇）

1.移除元素

力扣链接直达<请点击
在这里插入图片描述

int removeElement(int* nums, int numsSize, int val) 
{int count = 0;for(int i=0;i<numsSize;i++){if(nums[i]!=val){nums[count] = nums[i];count++;}}return count;
}

代码说明：

初始化计数count： count从0开始，用于记录不等于val的元素数量，并作为新数组的索引。
**遍历数组：**使用i遍历整个数组，检查每个元素是否等于val。
如果nums[i]不等于val，则将其复制到nums[k]的位置，并递增k。
如果等于val，则跳过该元素。
返回结果：最终k即为新数组的长度，且数组的前k个元素均为不等于val的元素。

这种方法高效且满足题目要求的原地修改条件。
在这里插入图片描述

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

力扣链接直达<请点击
在这里插入图片描述

int removeDuplicates(int* nums, int numsSize) {if (numsSize == 0) return 0; // 空数组直接返回 0int k = 0; // 慢指针，初始指向第一个元素for (int i = 1; i < numsSize; i++) {if (nums[i] != nums[k]) { // 发现新元素k++; // 移动慢指针nums[k] = nums[i]; // 存入新元素}// 如果 nums[i] == nums[k]，跳过（i 继续前进）}return k + 1; // 返回去重后的长度
}

在这里插入图片描述

在 “原地移除重复元素” 的算法中，当遇到重复元素时，并不是真的删除它，而是通过 覆盖（跳过） 的方式，让后面的非重复元素占据前面的位置，最终只保留不重复的部分。

关键点

不真正删除元素：数组在内存中是连续的，不能直接删除某个元素，只能覆盖。
双指针策略：
- 慢指针 k：记录 不重复元素应该存放的位置。
- 快指针 i：遍历数组，检查是否有新元素。
覆盖重复元素：
- 如果 nums[i] 是新元素（即 nums[i] != nums[k]），就把它存到 nums[k+1]，然后 k++。
- 如果 nums[i] 是重复的（即 nums[i] == nums[k]），就 跳过它（i 继续前进，k 不动）。

详细步骤（以 `nums = [1, 1, 2, 2, 3]` 为例）

`i`	`k`	`nums[i]`	`nums[k]`	操作	`nums` 变化
1	0	`1`	`1`	`nums[i] == nums[k]`，跳过	`[1, 1, 2, 2, 3]`（不变）
2	0	`2`	`1`	`nums[i] != nums[k]`，存入 `nums[1] = 2`，`k++`	`[1, 2, 2, 2, 3]`
3	1	`2`	`2`	`nums[i] == nums[k]`，跳过	`[1, 2, 2, 2, 3]`（不变）
4	1	`3`	`2`	`nums[i] != nums[k]`，存入 `nums[2] = 3`，`k++`	`[1, 2, 3, 2, 3]`

最终结果：

前 k+1 = 3 个元素是去重后的：[1, 2, 3]（后面的 2, 3 可以忽略）。
返回 k + 1 = 3（去重后的长度）。

为什么 `nums[i] == nums[k]` 时，`k` 不移动？

k 指向的是当前不重复部分的最后一个元素。
如果 nums[i] 和 nums[k] 相同，说明 nums[i] 是重复的，直接跳过（不存入数组）。
只有遇到新元素时，才存入 nums[k+1] 并移动 k。

总结

移除重复元素 实际上是 用后面的不重复元素覆盖前面的重复位置。
k 的作用：
- 记录 去重后的数组末尾位置。
- 只有遇到新元素时才移动 k，否则跳过。
时间复杂度 O(n)，空间复杂度 O(1)（原地修改）。

这样，最终 nums 的前 k+1 个元素就是去重后的结果，而后面部分可以忽略。

3.合并两个有序数组

力扣链接直达<请点击
在这里插入图片描述

解决思路

由于 nums1 有足够的空间容纳 nums2 的元素，我们可以利用 双指针 的方法从后向前合并，以避免覆盖 nums1 中还未处理的元素。具体步骤如下：

初始化指针：
- i 指向 nums1 的最后一个有效元素（即 m - 1）。
- j 指向 nums2 的最后一个元素（即 n - 1）。
- k 指向 nums1 的最后一个位置（即 m + n - 1）。
从后向前比较并合并：
- 比较 nums1[i] 和 nums2[j]，将较大的元素放到 nums1[k]。
- 移动相应的指针（i 或 j）和 k。
处理剩余元素：
- 如果 nums2 中还有剩余元素（即 j >= 0），直接复制到 nums1 的前面。

解决代码

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int i = m - 1;      // nums1 的最后一个有效元素int j = n - 1;      // nums2 的最后一个元素int k = m + n - 1;  // nums1 的最后一个位置// 从后向前合并while (i >= 0 && j >= 0) {if (nums1[i] > nums2[j]) {nums1[k--] = nums1[i--];} else {nums1[k--] = nums2[j--];}}// 如果 nums2 还有剩余元素，直接复制到 nums1 的前面while (j >= 0) {nums1[k--] = nums2[j--];}
}

在这里插入图片描述

代码解释

初始化指针：
- i 从 nums1 的有效末尾开始。
- j 从 nums2 的末尾开始。
- k 从 nums1 的最后一个位置开始。
比较并合并：
- 比较 nums1[i] 和 nums2[j]，将较大的元素放入 nums1[k]，并移动相应的指针。
- 这样确保 nums1 的后半部分不会被覆盖，直到所有元素正确归位。
处理剩余元素：
- 如果 nums2 中还有元素未合并（即 j >= 0），直接复制到 nums1 的前面，因为 nums1 的前面部分已经处理完毕。

示例

输入：

nums1 = [1, 2, 3, 0, 0, 0], m = 3
nums2 = [2, 5, 6], n = 3

执行过程：

i = 2, j = 2, k = 5：
- nums1[2] = 3 < nums2[2] = 6 → nums1[5] = 6, j--, k--
i = 2, j = 1, k = 4：
- nums1[2] = 3 < nums2[1] = 5 → nums1[4] = 5, j--, k--
i = 2, j = 0, k = 3：
- nums1[2] = 3 > nums2[0] = 2 → nums1[3] = 3, i--, k--
i = 1, j = 0, k = 2：
- nums1[1] = 2 == nums2[0] = 2 → nums1[2] = 2, j--, k--
j = -1，循环结束。
nums2 已无剩余元素，合并完成。