在算法学习中数组是最基础也是最重要的数据结构之一。今天我们来分析三道经典的数组操作题从最容易想到的暴力解法出发逐步推导出最优算法。题一两数之和题目大意给定一个整数数组nums和一个整数目标值target请你在该数组中找出和为目标值的那两个整数并返回它们的数组下标。方法一暴力枚举看到找出两个数最直观的想法就是枚举数组中的每一个数x然后寻找数组中是否存在target - x。/** * Note: The returned array must be malloced, assume caller calls free(). */ int* twoSum(int* nums, int numsSize, int target, int* returnSize) { int* result (int*)malloc(2 * sizeof(int)); *returnSize 2; // 外层循环枚举第一个数 for (int i 0; i numsSize; i) { // 内层循环枚举第二个数 for (int j i 1; j numsSize; j) { if (nums[i] nums[j] target) { result[0] i; result[1] j; return result; } } } return result; }复杂度分析时间复杂度O(n²)两层循环遍历数组。空间复杂度O(1)只使用了常数个额外变量。方法二哈希表优化暴力法的问题在于寻找target - x时我们做了太多重复工作。如果能把已经遍历过的数存起来就能做到查找 O(1)。核心思想遍历数组时用一个哈希表记录每个数值对应的下标。对于当前的nums[i]检查target - nums[i]是否已经在哈希表中。在 C 语言中标准库没有直接提供哈希表。如果后续学习了指针和数据结构可以用开放寻址法或链地址法自己实现一个哈希表也可以使用类似uthash这样的第三方库。这里我们先理解思想用空间换时间将查找过程从 O(n) 降到 O(1)。下面是一个使用uthash库的具体实现示例#include stdio.h #include stdlib.h // 引入 uthash 头文件 #include uthash.h // 定义哈希表结构体 struct hash_table { int key; // 存储数组元素值 int value; // 存储数组下标 UT_hash_handle hh; // uthash 内部使用的句柄 }; /** Note: The returned array must be malloced, assume caller calls free(). / int twoSum(int* nums, int numsSize, int target, int* returnSize) { struct hash_table* hash NULL; // 哈希表指针初始化为 NULL int* result (int*)malloc(2 * sizeof(int)); *returnSize 2; // 遍历数组 for (int i 0; i numsSize; i) { int complement target - nums[i]; // 计算补数 struct hash_table* tmp NULL; // 在哈希表中查找补数是否存在 HASH_FIND_INT(hash, amp;complement, tmp); if (tmp ! NULL) { // 找到匹配返回两个下标 result[0] tmp-gt;value; // 之前存储的下标 result[1] i; // 当前下标 return result; } // 将当前元素插入哈希表 struct hash_table* new_entry (struct hash_table*)malloc(sizeof(struct hash_table)); new_entry-gt;key nums[i]; new_entry-gt;value i; HASH_ADD_INT(hash, key, new_entry); } // 理论上题目保证有解这里返回空数组表示未找到 return result; } // 使用示例main函数仅用于演示 int main() { int nums[] {2, 7, 11, 15}; int target 9; int returnSize; int* result twoSum(nums, 4, target, amp;returnSize); if (returnSize 2) { printf(下标: [%d, %d]\n, result[0], result[1]); } free(result); return 0; }关键步骤说明引入 uthash首先需要下载并包含uthash.h头文件。定义结构体定义一个包含key数组元素值、value数组下标和UT_hash_handle的结构体。初始化哈希表声明一个指向哈希表的指针并初始化为NULL。遍历查找对于每个元素nums[i]计算补数target - nums[i]使用HASH_FIND_INT在哈希表中查找。找到匹配如果找到补数返回之前存储的下标和当前下标。插入新元素如果没找到使用HASH_ADD_INT将当前元素插入哈希表。内存管理注意在真实项目中需要释放哈希表内存这里为简洁省略。复杂度分析时间复杂度O(n)只需遍历数组一次哈希表查找和插入的平均时间复杂度为 O(1)。空间复杂度O(n)哈希表需要存储 n 个元素。题二删除有序数组中的重复项题目大意给你一个非严格递增排列的数组nums请你原地删除重复出现的元素使每个元素只出现一次返回删除后数组的新长度。元素的相对顺序应该保持一致。方法一暴力辅助数组既然要去重可以新建一个辅助数组把第一次出现的元素依次放进去最后再把辅助数组的内容复制回原数组。int removeDuplicates(int* nums, int numsSize) { if (numsSize 0) return 0; int temp[numsSize]; // 辅助数组 temp[0] nums[0]; int k 1; // temp 数组的有效长度 for (int i 1; i numsSize; i) { if (nums[i] ! temp[k - 1]) { // 只保留不重复的元素 temp[k] nums[i]; k; } } // 复制回原数组 for (int i 0; i k; i) { nums[i] temp[i]; } return k; }复杂度分析时间复杂度O(n)遍历两次数组。空间复杂度O(n)需要额外的辅助数组。方法二双指针快慢指针仔细观察会发现由于数组是有序的重复元素一定连续出现。我们根本不需要额外的数组直接在原数组上操作即可。设置两个下标指针思想但用数组下标实现慢指针slow指向去重后数组的最后一个有效位置。快指针fast负责遍历整个数组寻找下一个不重复的元素。int removeDuplicates(int* nums, int numsSize) { if (numsSize 0) return 0; int slow 0; // 慢指针指向已去重部分的末尾 for (int fast 1; fast numsSize; fast) { // 当快指针发现新的不重复元素时 if (nums[fast] ! nums[slow]) { slow; // 慢指针先向前一步 nums[slow] nums[fast]; // 覆盖写入新元素 } // 如果相等fast 继续向前slow 不动相当于跳过重复元素 } return slow 1; // 长度等于下标加 1 }复杂度分析时间复杂度O(n)只遍历一次数组。空间复杂度O(1)完全原地修改没有使用额外数组。题三移除元素题目大意给你一个数组nums和一个值val你需要原地移除所有数值等于val的元素并返回移除后数组的新长度。元素的顺序可能发生改变。方法一暴力法遍历数组每遇到一个等于val的元素就把后面的所有元素向前移动一位。int removeElement(int* nums, int numsSize, int val) { int i 0; while (i numsSize) { if (nums[i] val) { // 发现目标值将后面所有元素前移一位 for (int j i; j numsSize - 1; j) { nums[j] nums[j 1]; } numsSize--; // 数组总长度减 1 // 注意i 不要加 1因为新移过来的元素还要检查 } else { i; } } return numsSize; }复杂度分析时间复杂度O(n²)最坏情况下每次都要移动 O(n) 个元素。空间复杂度O(1)。方法二双指针快慢指针这道题和第 26 题几乎如出一辙我们同样可以用两个下标来避免大量元素移动快指针fast遍历数组寻找不等于val的元素。慢指针slow指向新数组的下一个写入位置。int removeElement(int* nums, int numsSize, int val) { int slow 0; // 慢指针新数组的写入位置 for (int fast 0; fast numsSize; fast) { if (nums[fast] ! val) { nums[slow] nums[fast]; // 保留不等于 val 的元素 slow; } // 等于 val 的元素被 fast 跳过不会被写入 } return slow; // slow 正好是有效元素的个数 }复杂度分析时间复杂度O(n)只遍历一次数组。空间复杂度O(1)原地修改。题二与题三的对比总结这两道题虽然题干不同但解题框架几乎一模一样掌握了一道另一道就能迅速写出下面是两道题的核心对比对比维度第 26 题删除有序数组中的重复项第 27 题移除元素核心操作原地修改数组原地修改数组判断条件nums[fast] ! nums[slow]与前一个保留元素比较nums[fast] ! val与给定值比较快指针起点fast 1第一个元素一定保留fast 0从头检查每个元素慢指针起点slow 0slow 0写入时机发现新元素时slow后再写入发现保留元素时直接写入再slow返回值slow 1长度 下标 1slow长度正好等于下标数组要求必须有序重复元素连续可以无序顺序要求相对顺序必须保持一致相对顺序可以改变上述写法仍保持顺序共同的本质快指针负责探索整个数组慢指针负责构建新数组。快指针每找到一个符合条件的元素就交给慢指针写入。两者就像流水线上的两个工人一个负责筛选一个负责打包配合默契一次遍历完成任务。写在最后从这三道题中我们可以提炼出数组问题中非常实用的解题策略看到找两个数先想暴力枚举再考虑能否用哈希表将查找优化到 O(1)。看到原地修改数组且保留部分元素立刻想到双指针快慢指针技巧。快指针遍历慢指针构造这是处理数组去重、移除、筛选类问题的黄金法则。
从暴力到双指针：三道数组经典题的算法解析
在算法学习中数组是最基础也是最重要的数据结构之一。今天我们来分析三道经典的数组操作题从最容易想到的暴力解法出发逐步推导出最优算法。题一两数之和题目大意给定一个整数数组nums和一个整数目标值target请你在该数组中找出和为目标值的那两个整数并返回它们的数组下标。方法一暴力枚举看到找出两个数最直观的想法就是枚举数组中的每一个数x然后寻找数组中是否存在target - x。/** * Note: The returned array must be malloced, assume caller calls free(). */ int* twoSum(int* nums, int numsSize, int target, int* returnSize) { int* result (int*)malloc(2 * sizeof(int)); *returnSize 2; // 外层循环枚举第一个数 for (int i 0; i numsSize; i) { // 内层循环枚举第二个数 for (int j i 1; j numsSize; j) { if (nums[i] nums[j] target) { result[0] i; result[1] j; return result; } } } return result; }复杂度分析时间复杂度O(n²)两层循环遍历数组。空间复杂度O(1)只使用了常数个额外变量。方法二哈希表优化暴力法的问题在于寻找target - x时我们做了太多重复工作。如果能把已经遍历过的数存起来就能做到查找 O(1)。核心思想遍历数组时用一个哈希表记录每个数值对应的下标。对于当前的nums[i]检查target - nums[i]是否已经在哈希表中。在 C 语言中标准库没有直接提供哈希表。如果后续学习了指针和数据结构可以用开放寻址法或链地址法自己实现一个哈希表也可以使用类似uthash这样的第三方库。这里我们先理解思想用空间换时间将查找过程从 O(n) 降到 O(1)。下面是一个使用uthash库的具体实现示例#include stdio.h #include stdlib.h // 引入 uthash 头文件 #include uthash.h // 定义哈希表结构体 struct hash_table { int key; // 存储数组元素值 int value; // 存储数组下标 UT_hash_handle hh; // uthash 内部使用的句柄 }; /** Note: The returned array must be malloced, assume caller calls free(). / int twoSum(int* nums, int numsSize, int target, int* returnSize) { struct hash_table* hash NULL; // 哈希表指针初始化为 NULL int* result (int*)malloc(2 * sizeof(int)); *returnSize 2; // 遍历数组 for (int i 0; i numsSize; i) { int complement target - nums[i]; // 计算补数 struct hash_table* tmp NULL; // 在哈希表中查找补数是否存在 HASH_FIND_INT(hash, amp;complement, tmp); if (tmp ! NULL) { // 找到匹配返回两个下标 result[0] tmp-gt;value; // 之前存储的下标 result[1] i; // 当前下标 return result; } // 将当前元素插入哈希表 struct hash_table* new_entry (struct hash_table*)malloc(sizeof(struct hash_table)); new_entry-gt;key nums[i]; new_entry-gt;value i; HASH_ADD_INT(hash, key, new_entry); } // 理论上题目保证有解这里返回空数组表示未找到 return result; } // 使用示例main函数仅用于演示 int main() { int nums[] {2, 7, 11, 15}; int target 9; int returnSize; int* result twoSum(nums, 4, target, amp;returnSize); if (returnSize 2) { printf(下标: [%d, %d]\n, result[0], result[1]); } free(result); return 0; }关键步骤说明引入 uthash首先需要下载并包含uthash.h头文件。定义结构体定义一个包含key数组元素值、value数组下标和UT_hash_handle的结构体。初始化哈希表声明一个指向哈希表的指针并初始化为NULL。遍历查找对于每个元素nums[i]计算补数target - nums[i]使用HASH_FIND_INT在哈希表中查找。找到匹配如果找到补数返回之前存储的下标和当前下标。插入新元素如果没找到使用HASH_ADD_INT将当前元素插入哈希表。内存管理注意在真实项目中需要释放哈希表内存这里为简洁省略。复杂度分析时间复杂度O(n)只需遍历数组一次哈希表查找和插入的平均时间复杂度为 O(1)。空间复杂度O(n)哈希表需要存储 n 个元素。题二删除有序数组中的重复项题目大意给你一个非严格递增排列的数组nums请你原地删除重复出现的元素使每个元素只出现一次返回删除后数组的新长度。元素的相对顺序应该保持一致。方法一暴力辅助数组既然要去重可以新建一个辅助数组把第一次出现的元素依次放进去最后再把辅助数组的内容复制回原数组。int removeDuplicates(int* nums, int numsSize) { if (numsSize 0) return 0; int temp[numsSize]; // 辅助数组 temp[0] nums[0]; int k 1; // temp 数组的有效长度 for (int i 1; i numsSize; i) { if (nums[i] ! temp[k - 1]) { // 只保留不重复的元素 temp[k] nums[i]; k; } } // 复制回原数组 for (int i 0; i k; i) { nums[i] temp[i]; } return k; }复杂度分析时间复杂度O(n)遍历两次数组。空间复杂度O(n)需要额外的辅助数组。方法二双指针快慢指针仔细观察会发现由于数组是有序的重复元素一定连续出现。我们根本不需要额外的数组直接在原数组上操作即可。设置两个下标指针思想但用数组下标实现慢指针slow指向去重后数组的最后一个有效位置。快指针fast负责遍历整个数组寻找下一个不重复的元素。int removeDuplicates(int* nums, int numsSize) { if (numsSize 0) return 0; int slow 0; // 慢指针指向已去重部分的末尾 for (int fast 1; fast numsSize; fast) { // 当快指针发现新的不重复元素时 if (nums[fast] ! nums[slow]) { slow; // 慢指针先向前一步 nums[slow] nums[fast]; // 覆盖写入新元素 } // 如果相等fast 继续向前slow 不动相当于跳过重复元素 } return slow 1; // 长度等于下标加 1 }复杂度分析时间复杂度O(n)只遍历一次数组。空间复杂度O(1)完全原地修改没有使用额外数组。题三移除元素题目大意给你一个数组nums和一个值val你需要原地移除所有数值等于val的元素并返回移除后数组的新长度。元素的顺序可能发生改变。方法一暴力法遍历数组每遇到一个等于val的元素就把后面的所有元素向前移动一位。int removeElement(int* nums, int numsSize, int val) { int i 0; while (i numsSize) { if (nums[i] val) { // 发现目标值将后面所有元素前移一位 for (int j i; j numsSize - 1; j) { nums[j] nums[j 1]; } numsSize--; // 数组总长度减 1 // 注意i 不要加 1因为新移过来的元素还要检查 } else { i; } } return numsSize; }复杂度分析时间复杂度O(n²)最坏情况下每次都要移动 O(n) 个元素。空间复杂度O(1)。方法二双指针快慢指针这道题和第 26 题几乎如出一辙我们同样可以用两个下标来避免大量元素移动快指针fast遍历数组寻找不等于val的元素。慢指针slow指向新数组的下一个写入位置。int removeElement(int* nums, int numsSize, int val) { int slow 0; // 慢指针新数组的写入位置 for (int fast 0; fast numsSize; fast) { if (nums[fast] ! val) { nums[slow] nums[fast]; // 保留不等于 val 的元素 slow; } // 等于 val 的元素被 fast 跳过不会被写入 } return slow; // slow 正好是有效元素的个数 }复杂度分析时间复杂度O(n)只遍历一次数组。空间复杂度O(1)原地修改。题二与题三的对比总结这两道题虽然题干不同但解题框架几乎一模一样掌握了一道另一道就能迅速写出下面是两道题的核心对比对比维度第 26 题删除有序数组中的重复项第 27 题移除元素核心操作原地修改数组原地修改数组判断条件nums[fast] ! nums[slow]与前一个保留元素比较nums[fast] ! val与给定值比较快指针起点fast 1第一个元素一定保留fast 0从头检查每个元素慢指针起点slow 0slow 0写入时机发现新元素时slow后再写入发现保留元素时直接写入再slow返回值slow 1长度 下标 1slow长度正好等于下标数组要求必须有序重复元素连续可以无序顺序要求相对顺序必须保持一致相对顺序可以改变上述写法仍保持顺序共同的本质快指针负责探索整个数组慢指针负责构建新数组。快指针每找到一个符合条件的元素就交给慢指针写入。两者就像流水线上的两个工人一个负责筛选一个负责打包配合默契一次遍历完成任务。写在最后从这三道题中我们可以提炼出数组问题中非常实用的解题策略看到找两个数先想暴力枚举再考虑能否用哈希表将查找优化到 O(1)。看到原地修改数组且保留部分元素立刻想到双指针快慢指针技巧。快指针遍历慢指针构造这是处理数组去重、移除、筛选类问题的黄金法则。