在C语言数组考试里，有限空间下数组重复元素查找是高频中等难度压轴难题。绝大多数同学第一反应就是开数组、开哈希表统计次数，完全不符合题目「常数额外空间、线性时间复杂度」的硬性要求。
今天从数组下标内存映射底层逻辑，拆解原地哈希经典算法，彻底吃透C语言数组空间最优解题思路。
 
一、经典笔试原题
 
给定长度为n的整型数组，数组内所有数字范围都在 [1,n] 之间，每个数字最多出现2次，请找出所有重复出现2次的数字。
强制要求：时间复杂度O(n)、只能使用常数额外空间，不能新开数组、哈希表、集合容器。
 
二、C语言底层下标映射解题逻辑
 
精准利用题目数字特性：数组长度为n、数字取值1~n，数字 x 可以精准对应数组下标 x-1 ，直接把原数组本身当作哈希存储容器，完全不占用额外内存。
核心标记思路：利用数字正负符号，记录数字是否已经遍历出现过
 
1. 遍历数组每一位数字，先取绝对值，还原原本数值，避免前面取反修改干扰
2. 通过数值定位对应哈希下标： 下标 = 当前数字-1 
3. 判断下标位置数字正负：
 
- 下标位置数字为负数：代表这个数字之前已经遍历出现过，当前数字就是重复元素，直接存入结果
- 下标位置数字为正数：把该位置数字整体取反变为负数，标记这个数字已经出现过一次
 
4. 全程仅一轮for循环遍历，线性时间复杂度，除结果数组外零额外空间
 
三、C语言完整可运行代码实现
#include <stdio.h>
#include <stdlib.h>

// 查找数组重复数字，返回结果数组与长度
int* findDuplicates(int* nums, int numsSize, int* returnSize){
    int* res = (int*)malloc(numsSize*sizeof(int));
    *returnSize = 0;

    for(int i=0;i<numsSize;i++){
        // 取绝对值还原原本数值
        int num = abs(nums[i]);
        int idx = num - 1;
        // 位置已被标记，数字重复
        if(nums[idx] < 0){
            res[(*returnSize)++] = num;
        }else{
            // 取反做出现标记
            nums[idx] = -nums[idx];
        }
    }
    return res;
}

int main(){
    int arr[] = {4,3,2,7,8,2,3,1};
    int len;
    int* ans = findDuplicates(arr,8,&len);
    // 打印重复结果
    for(int i=0;i<len;i++) printf("%d ",ans[i]);
    return 0;
}
 
 
四、高频易错难点深度剖析
 
1. 必须先取绝对值！前面遍历会修改数组正负符号，不取绝对值会直接下标越界、数组寻址崩溃
2. C语言数组下标从0开始，题目数字从1开始，必须 数值-1 完成下标一一映射，一步错位全错
3. 正负符号仅做存在标记，不会破坏数字本身大小关系，遍历结束完全可逆还原原数组
4. 完美适配题目「最多出现2次」限制，两次遍历一次标记、一次判定，逻辑完全闭环
 
五、算法学习总结
 
C语言数组最难的考点，从来不是循环遍历，而是内存下标映射、原地空间复用思维。
原地哈希写法是大厂面试王牌解法，无序数组查找、缺失数字、重复元素题型全部通用，不用额外开辟内存，极致压缩空间复杂度，吃透一套逻辑搞定一整类数组算法难题。坚持每日攻克C语言底层编程难点，夯实数据结构算法基础。