拷打字节面试官之-吃透c语言-哈希算法 如何在3面拷打字节cto 3万行算法源码带你吃透算法面试所有考题
继续跟新： 牛客面试101热题笔刷榜单 哈希算法
哈希 》》》偏技巧的题目
（1）：哈希算法，绝非简单的数组
1. 福利：这篇文章凭什么让你点赞收藏？
兄弟们，如果你还在纠结于哈希表和Map的那点事儿，觉得哈希算法就是简单的key-value存取，那你可太小看它了。在牛客和力扣的面试题里，哈希算法早就被玩出花来了。
这篇博客，我将以一个程序员的视角，和你一起攻克牛客101热题榜哈希算法部分的几道核心题目。咱们要做到：
思路透彻：不仅告诉你怎么做，还告诉你为什么这么做，以及有没有更好的方法。
代码硬核：用C语言，把每一行代码的逻辑和性能都给你讲得明明白白。
知识补给：如果题目涉及你不太了解的知识点（比如位运算、数学证明），我都会深入浅出地给你补上，让你再无知识死角。
好了 现在要用最朴素、最硬核的方式 开始干活
2. 出现次数超过一半的数字：从空间换时间到摩尔投票法的降维打击
2.1 题目分析与思路演进
这道题的背景很简单：给你一个数组，里面有一个数字出现的次数超过了数组长度的一半。你的任务是找出这个数字。
2.1.1 思路一：最直接的暴力解法 (哈希表计数)
你草稿里的#2刷和#3刷都用到了哈希表的思想，这也是最直观的解法。
核心逻辑：
搞一个哈希表（这里你用了一个超大数组作为哈希表的底层实现）。
遍历数组，每遇到一个数字，就在哈希表中对应位置的计数器加一。
再遍历哈希表，找到那个计数大于数组长度一半的数字，返回它。
你的代码分析与优化：
// #include <stdio.h>
// #include <stdlib.h>
// #2刷
// int hash[10001] = {0}; // 固定大小数组
// for (int i = 0; i < numbersLen; i++)
// {
// hash[numbers[i]]++; // 计数，非常棒
// }
// for (int i = 0; i <= 10000; i++)
// {
// if (hash[i] > numbersLen / 2)
// {
// return i;
// }
// }
// return -1;这段代码的思路是完全正确的。但有几个问题：
空间浪费：
int hash[10001]这个数组的大小取决于你预估的数字范围。如果数字的范围很大，比如10^9，那你就无法用这种方法了，因为数组会太大。效率问题：你遍历了整个数组计数，又遍历了整个哈希表找结果。如果数字范围很大，第二次遍历的效率就会很低。
你#3刷的代码改进了第二次遍历的效率：
// #3刷
// int hash[1000000] = {0};
// for(int i =0;i<numbersLen;i++){
// hash[numbers[i]]++;
// }
// for(int i = 0;i<numbersLen;i++){ // 第二次遍历原数组，只检查出现过的数字
// int temp = numbers[i];
// if(hash[temp]>numbersLen/2){
// return temp;
// }
// }这个改进非常聪明，它避免了遍历整个哈希表。它只遍历原数组，然后去哈希表中查这些数字的计数，这样就避免了对大范围数字的无效查找。这个方法的时间复杂度是O(n)，空间复杂度是O(n)（最坏情况下）。
2.1.2 思路二：摩尔投票法（Boyer-Moore Voting Algorithm），降维打击！
你最后一段代码直接用上了这个神级算法，堪称“降维打击”。它完全放弃了哈希表，把空间复杂度直接降到了O(1)。
核心思想：
想象一下，你和你的对手（就是那个超过一半的数字）在打架。
你把一个数字当作你的“旗帜”，
count就是你的“血量”。遍历数组：
如果当前数字和你的“旗帜”一样，你的血量就加1。
如果不一样，你的血量就减1。
当你的血量归零时，说明你的“旗帜”被打掉了，你就得换一个新的旗帜（当前数字）。
为什么这个方法管用？因为那个“超过一半”的数字，它的数量是如此之多，以至于不管你的血量怎么被消耗，它最后都能“剩下来”。就像一支人数过半的军队，不管怎么和另一支军队互相消耗，最后剩下的士兵一定还是这支军队的。
算法流程图：
开始|+--- 初始化 flag = numbers[0], count = 1|+--- 遍历数组 (i 从 1 到 numbersLen-1)|+--- 检查 count 是否为 0| || +--- 是: flag = numbers[i], count = 1|+--- 否: 检查 numbers[i] == flag|+--- 是: count++|+--- 否: count--|+--- 遍历结束|+--- 返回 flag
结束这个算法巧妙地利用了“超过一半”这个条件，用一个O(1)的空间就把问题解决了。这就是算法的魅力！
2.2 代码精讲与实现（摩尔投票法）
你的代码已经写得非常好了，逻辑清晰。我这里提供一个稍微完善的版本，并加上更详细的注释，方便你理解每一步的用意。
#include <stdio.h>
#include <stdlib.h>/*** @brief 寻找数组中出现次数超过一半的数字** 该函数使用摩尔投票法 (Boyer-Moore Voting Algorithm)，在O(n)的时间复杂度* 和O(1)的空间复杂度内解决问题。** @param numbers int整型一维数组，保证有这样一个数字。* @param numbersLen int numbers数组长度。* @return int 返回出现次数超过一半的那个数字。*/
int MoreThanHalfNum_Solution(int *numbers, int numbersLen) {if (numbersLen == 0) {// 根据题目，通常不会传入空数组，但严谨起见，需要处理return 0; }int candidate = numbers[0]; // 候选人，相当于你的“旗帜”int count = 1; // 计数器，相当于你的“血量”// 从第二个元素开始遍历for (int i = 1; i < numbersLen; i++) {// 如果计数器为0，说明之前的候选人被“消耗”光了// 此时，更换新的候选人，并将计数器重置为1if (count == 0) {candidate = numbers[i];count = 1;} else {// 如果当前数字与候选人相同，则计数器加1if (numbers[i] == candidate) {count++;} else {// 如果不同，则计数器减1，相当于与候选人同归于尽count--;}}}// 理论上，摩尔投票法最后剩下的candidate就是众数// 但如果题目不保证存在众数，我们还需要进行一次验证// 题目中保证了，所以这一步可以省略，但作为严谨的程序员，还是加上吧！int finalCount = 0;for (int i = 0; i < numbersLen; i++) {if (numbers[i] == candidate) {finalCount++;}}// 如果最后剩下的候选人出现次数确实超过一半，就返回它// 否则，根据题目要求，返回-1或者其他值if (finalCount > numbersLen / 2) {return candidate;} else {return -1; // 题目通常不需这一步，但这是完整解法}
}2.3 小结与思维升华
方法 | 时间复杂度 | 空间复杂度 | 优缺点 |
|---|---|---|---|
哈希表 | O(n) | O(n) | 思路直观，易于实现，但空间开销大，且数字范围有限制 |
摩尔投票法 | O(n) | O(1) | 空间效率极高，思路巧妙，但仅适用于“超过一半”这种特殊情况 |
摩尔投票法是一种典型的利用题目特殊条件来优化算法的例子。它告诉我们，很多看似需要额外空间解决的问题，都可以通过巧妙的算法设计，实现“空间换时间”的逆向操作，也就是**“时间换空间”**。
这道题的精髓就在于，它考察的不是你对哈希表这种数据结构的熟练度，而是你是否能跳出常规思维，找到更高效的算法。
3. 出现一次的两个数字：从哈希计数到异或运算的极致简化
3.1 题目分析与思路演进
这道题是上一道题的变种，难度直线飙升。它要求你在一个数组里，找出两个只出现了一次的数字，而其他数字都出现了两次。
3.1.1 思路一：哈希表计数（你提供的代码）
你的代码采用了哈希计数的方法，思路完全正确，而且实现得也很严谨。
核心逻辑：
计数：用一个哈希数组，遍历数组并记录每个数字出现的次数。
查找：再遍历一次哈希数组，找出计数为1的两个数字。
排序：将找到的两个数字按从小到大排序。
你的代码分析与优化：
#include<stdio.h>
#include<stdlib.h>
#define MAX_size 1000000
int* FindNumsAppearOnce(int* nums, int numsLen, int* returnSize ) {int hash[1000000] ;for(int i=0;i<1000000;i++){hash[i]=0;}for(int i = 0;i<numsLen;i++){hash[nums[i]]++;}// ...
}你的代码用了一个100万大小的数组作为哈希表，并进行了初始化。这在牛客的题库里通常能通过，因为数据范围通常不会超过这个上限。但同样，这种方法有它的局限性：
内存限制：如果题目给的数字范围是
10^9，这种方法就直接GG了。不优雅：虽然能解决问题，但不够“硬核”。面试官更希望看到你对底层原理的理解。
3.1.2 思路二：异或运算（XOR）的神奇魔法
这才是这道题的终极解法，它只用到了异或运算，时间复杂度O(n)，空间复杂度O(1)。
异或运算的性质（必须掌握）：
交换律和结合律：aoplusb=boplusa；(aoplusb)oplusc=aoplus(boplusc)。
任何数与0异或，结果不变：aoplus0=a。
任何数与自身异或，结果为0：aoplusa=0。
核心思想：
第一步：全员异或。将数组中所有元素进行异或。由于其他数字都出现了两次，两两异或会得到0，所以最后的结果
xorSum就是那两个只出现一次的数字的异或值。假设这两个数字是
a和b，那么xorSum = a ^ b。xorSum的二进制表示中，至少有一位是1。这一位是1，说明a和b在这一位上是不同的。
第二步：分组。利用
xorSum中某一位的1，将原数组中的所有数字分为两组。第一组：该位为1的数字。
第二组：该位为0的数字。
第三步：组内异或。对这两组数字分别进行异或。
第一组异或的结果就是
a（因为b不在这一组，其他数都出现了两次）。第二组异或的结果就是
b（因为a不在这一组，其他数都出现了两次）。
这个方法非常巧妙，它利用了异或运算的自消亡特性，将一个复杂的问题分解为两个简单的子问题。
算法流程图：
开始|+--- 步骤一：全员异或| || +--- 计算 xorSum = 所有元素的异或| || +--- xorSum = a ^ b|+--- 步骤二：寻找区分位| || +--- 找到 xorSum 二进制表示中最低位的 '1' (比如通过 xorSum & (-xorSum))| || +--- 这个 '1' 就是 a 和 b 的不同之处|+--- 步骤三：分组并异或|+--- 初始化 group1 = 0, group2 = 0|+--- 遍历原数组|+--- 如果当前数字在区分位上是 '1'| || +--- group1 ^= 当前数字|+--- 否则| || +--- group2 ^= 当前数字|+--- 返回 group1 和 group2
结束这种解法简直是艺术！它把空间复杂度直接降到了最低
1 “出现次数超过一半的数字”和“出现一次的两个数字”这两道题，从你的代码初稿出发，一路带你看到了摩尔投票法和异或运算， 继续更新第二部分~
（2）：原地哈希与双指针的极致应用
4. 缺失的第一个正整数：不占一分一毫，原地哈希的骚操作
4.1 题目分析与思路演进
这道题是哈希算法里一个非常经典的变种。它要求我们找出数组中第一个缺失的正整数。这里的关键在于：正整数，而且是第一个。
你草稿里的思路非常棒，想到了通过“替换”来达到目的。这正是“原地哈希”的核心思想。
4.1.1 思路分析：原地哈希（In-place Hashing）
所谓原地哈希，就是利用数组本身的索引作为哈希表的键，将元素放到它“应该”在的位置上，从而节省额外的空间。
核心逻辑：
我们想让数组中的数字
k被放到索引为k-1的位置上。比如，
nums[0]应该放1，nums[1]应该放2，以此类推。我们遍历数组，如果发现
nums[i]不在它应该在的位置（即nums[i]不是i+1），并且这个数字是在有效范围内的（大于0，且小于等于数组长度），我们就把它换到它该去的位置上。这个交换的过程要一直持续，直到
nums[i]找到它的“归宿”。这就是你代码中while循环的精髓。
4.1.2 你的代码分析与优化
你对原地哈希的理解很到位，但代码中有一处小小的笔误，导致了逻辑错误。
你的代码：
// ...
// while (nums[i] > 0 && nums[i] < numsLen && num[i] != i + 1)
// {
// int temp = nums[i];
// int nums[i] = nums[temp - 1]; // 错误：这里是 nums[temp-1] 而不是 num[temp-1]
// num[temp - 1] = temp; // 错误：这里是 num 而不是 nums
// }
// ...你代码中的nums[i] = nums[temp-1]和num[temp-1] = temp应该是nums[i] = nums[temp-1]和nums[temp-1] = temp，而且nums[i] != i+1这个条件应该在循环内部检查，因为交换后nums[i]可能仍然不在正确的位置。
正确的逻辑流程图：
graph TDA[开始] --> B[遍历数组 i 从 0 到 numsLen-1]B --> C{当前数字 nums[i] 是否在正确位置?}C -->|是| D[继续下一个 i]C -->|否| E{数字 nums[i] 是否有效?}E -->|无效| DE -->|有效| F[交换 nums[i] 和 nums[nums[i]-1]]F --> CD --> G{遍历结束?}G -->|否| BG -->|是| H[第二次遍历 i 从 0 到 numsLen-1]H --> I{nums[i] == i+1 ?}I -->|是| J[继续下一个 i]I -->|否| K[返回 i+1]J --> L{遍历结束?}L -->|是| M[返回 numsLen+1]4.2 代码精讲与实现（原地哈希）
下面我为你重写了这部分代码，并加上了详细的注释。这个版本修正了你代码中的错误，并确保逻辑严密。
#include <stdio.h>/*** @brief 交换两个整数的值* 这是一个小辅助函数，用来简化代码*/
void swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param nums int整型一维数组* @param numsLen int nums数组长度* @return int整型*/
int minNumberDisappeared(int* nums, int numsLen) {// 步骤一：原地哈希，将数字k放到索引k-1的位置// 遍历整个数组，将每个数字放到它“应该在”的位置for (int i = 0; i < numsLen; i++) {// 使用一个while循环，确保当前位置的数字被正确放置// 条件：// 1. nums[i] > 0 && nums[i] <= numsLen：确保数字在有效范围内// 2. nums[i] != nums[nums[i] - 1]：避免死循环，如果数字已经就位，就不用再换了// 这个条件是关键，它防止了自己和自己交换，也防止了重复数字的死循环while (nums[i] > 0 && nums[i] <= numsLen && nums[i] != nums[nums[i] - 1]) {// 将nums[i]放到它应该在的位置 nums[i]-1swap(&nums[i], &nums[nums[i] - 1]);}}// 步骤二：遍历数组，找出第一个不符合要求的数字// 经过上一步，如果一个数字k存在，那么它一定在索引k-1的位置上for (int i = 0; i < numsLen; i++) {// 如果nums[i]不等于i+1，说明i+1这个正整数缺失了if (nums[i] != i + 1) {return i + 1;}}// 步骤三：如果所有数字都就位，说明缺失的是numsLen+1return numsLen + 1;
}5. 三数之和：排序与双指针的完美交响乐
5.1 题目分析与思路演进
三数之和是一个非常经典的面试题，它考察的是你如何把暴力解法的O(n^3)$时间复杂度优化到$O(n^2)。你给出的思路——排序加双指针——正是最优解。
5.1.1 思路分析：排序 + 双指针
核心逻辑：
第一步：排序。先对整个数组进行排序。这是关键，因为排序后，我们才能通过双指针来快速逼近目标和。
第二步：固定一个数。遍历数组，固定一个数
num[i]，把它作为三元组中的第一个元素。第三步：双指针逼近。在
num[i]后面的子数组中，设置两个指针left和right，分别指向子数组的头和尾。如果
num[i] + num[left] + num[right] == 0，找到一个解。如果
sum > 0，说明和太大，right向左移动，让和变小。如果
sum < 0，说明和太小，left向右移动，让和变大。
第四步：去重。由于数组中有重复数字，我们需要在每一步都进行去重处理，避免找到重复的三元组。
5.1.2 你的代码分析与优化
你的代码逻辑框架非常正确，看得出来你对这个方法理解很深。但有几个细节可以做得更好。
你的代码：
// ...
// int **threeSum(int *num, int numLen, int *returnSize, int **returnColumnSizes){
// // ...
// if (num == NULL || numLen < 3)
// {
// *returnSize = 0;
// returnColumnSizes = NULL;
// return num; // 错误：返回了原始数组，可能导致内存泄漏或错误
// }
// // ...
// }内存管理：在C语言中，动态分配的内存需要手动释放。你的代码在
if条件中返回了num，这很危险。正确的做法是返回NULL或者一个空数组。而且returnColumnSizes = NULL;会导致传入的指针无法被正确使用。去重逻辑：你考虑了
i的去重 (if (i > 0 && num[i] == num[i - 1]))，非常棒。但left和right的去重可以更简洁，并且要在找到解之后，立即进行去重操作，然后移动指针。
5.2 代码精讲与实现（排序+双指针）
下面我为你重写了这部分代码，并提供了详细的注释。这个版本修正了你的内存管理和去重逻辑，使其更加健壮。
#include <stdlib.h>
#include <string.h> // 使用 memcpy 和 memset// 比较函数，用于 qsort
int cmp(const void *a, const void *b) {return *(int *)a - *(int *)b;
}/*** @brief 在已排序的数组中，使用双指针找到三数之和为0的所有三元组。* @param nums int整型一维数组* @param numsLen int nums数组长度* @param returnSize int* 返回数组行数* @param returnColumnSizes int** 返回数组列数* @return int** 返回所有符合条件的三元组*/
int** threeSum(int* num, int numLen, int* returnSize, int** returnColumnSizes) {*returnSize = 0;// 检查边界条件if (num == NULL || numLen < 3) {*returnColumnSizes = NULL;return NULL;}// 步骤一：排序，这是双指针法的基础qsort(num, numLen, sizeof(int), cmp);// 为结果分配足够大的内存空间。在C语言中，这是一个挑战// 通常面试时会给出最大结果集，这里我们假设最坏情况int** result = (int**)malloc(sizeof(int*) * numLen * (numLen - 1) / 2);// 为每一行的列数分配内存*returnColumnSizes = (int*)malloc(sizeof(int) * numLen * (numLen - 1) / 2);// 步骤二：固定一个数，然后使用双指针for (int i = 0; i < numLen - 2; i++) {// 剪枝优化：如果当前数已经大于0，那么后面三个数的和不可能为0if (num[i] > 0) {break;}// 去重：如果当前数和前一个数相同，跳过以避免重复三元组if (i > 0 && num[i] == num[i - 1]) {continue;}int left = i + 1;int right = numLen - 1;while (left < right) {long long sum = (long long)num[i] + num[left] + num[right];if (sum == 0) {// 找到一个解，将其存储起来result[*returnSize] = (int*)malloc(sizeof(int) * 3);result[*returnSize][0] = num[i];result[*returnSize][1] = num[left];result[*returnSize][2] = num[right];(*returnColumnSizes)[*returnSize] = 3;(*returnSize)++;// 找到解后，移动指针并进行去重while (left < right && num[left] == num[left + 1]) {left++;}while (left < right && num[right] == num[right - 1]) {right--;}left++;right--;} else if (sum > 0) {// 和太大，右指针左移right--;} else {// 和太小，左指针右移left++;}}}return result;
}（第二部分完，待续）
好了兄弟们，第二部分到此结束！我们彻底干掉了“缺失的第一个正整数”和“三数之和”。
缺失的正整数：我们学会了如何利用原地哈希这种神仙技巧，把哈希表装进了原数组里，用$O(1)$空间解决了问题。
三数之和：我们则重温了排序+双指针的经典套路，并重点梳理了去重逻辑，确保你的代码在面试时滴水不漏。
下一篇，咱们要聊聊哈希算法的本质，以及如何将这些思想应用到其他更复杂的题目中。那才是真正把技术内化成自己的东西。
做好准备，咱们最后一部分，不见不散！
（3）：原地哈希与双指针的极致应用
4. 缺失的第一个正整数：不占一分一毫，原地哈希的骚操作
4.1 题目分析与思路演进
这道题是哈希算法里一个非常经典的变种。它要求我们找出数组中第一个缺失的正整数。这里的关键在于：正整数，而且是第一个。
你草稿里的思路非常棒，想到了通过“替换”来达到目的。这正是“原地哈希”的核心思想。
4.1.1 思路分析：原地哈希（In-place Hashing）
所谓原地哈希，就是利用数组本身的索引作为哈希表的键，将元素放到它“应该”在的位置上，从而节省额外的空间。
核心逻辑：
我们想让数组中的数字
k被放到索引为k-1的位置上。比如，
nums[0]应该放1，nums[1]应该放2，以此类推。我们遍历数组，如果发现
nums[i]不在它应该在的位置（即nums[i]不是i+1），并且这个数字是在有效范围内的（大于0，且小于等于数组长度），我们就把它换到它该去的位置上。这个交换的过程要一直持续，直到
nums[i]找到它的“归宿”。这就是你代码中while循环的精髓。
4.1.2 你的代码分析与优化
你对原地哈希的理解很到位，但代码中有一处小小的笔误，导致了逻辑错误。
你的代码：
// ...
// while (nums[i] > 0 && nums[i] < numsLen && num[i] != i + 1)
// {
// int temp = nums[i];
// int nums[i] = nums[temp - 1]; // 错误：这里是 nums[temp-1] 而不是 num[temp-1]
// num[temp - 1] = temp; // 错误：这里是 num 而不是 nums
// }
// ...你代码中的nums[i] = nums[temp-1]和num[temp-1] = temp应该是nums[i] = nums[temp-1]和nums[temp-1] = temp，而且nums[i] != i+1这个条件应该在循环内部检查，因为交换后nums[i]可能仍然不在正确的位置。
正确的逻辑流程图：
graph TDA[开始] --> B[遍历数组 i 从 0 到 numsLen-1]B --> C{当前数字 nums[i] 是否在正确位置?}C -->|是| D[继续下一个 i]C -->|否| E{数字 nums[i] 是否有效?}E -->|无效| DE -->|有效| F[交换 nums[i] 和 nums[nums[i]-1]]F --> CD --> G{遍历结束?}G -->|否| BG -->|是| H[第二次遍历 i 从 0 到 numsLen-1]H --> I{nums[i] == i+1 ?}I -->|是| J[继续下一个 i]I -->|否| K[返回 i+1]J --> L{遍历结束?}L -->|是| M[返回 numsLen+1]4.2 代码精讲与实现（原地哈希）
下面我为你重写了这部分代码，并加上了详细的注释。这个版本修正了你代码中的错误，并确保逻辑严密。
#include <stdio.h>/*** @brief 交换两个整数的值* 这是一个小辅助函数，用来简化代码*/
void swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param nums int整型一维数组* @param numsLen int nums数组长度* @return int整型*/
int minNumberDisappeared(int* nums, int numsLen) {// 步骤一：原地哈希，将数字k放到索引k-1的位置// 遍历整个数组，将每个数字放到它“应该在”的位置for (int i = 0; i < numsLen; i++) {// 使用一个while循环，确保当前位置的数字被正确放置// 条件：// 1. nums[i] > 0 && nums[i] <= numsLen：确保数字在有效范围内// 2. nums[i] != nums[nums[i] - 1]：避免死循环，如果数字已经就位，就不用再换了// 这个条件是关键，它防止了自己和自己交换，也防止了重复数字的死循环while (nums[i] > 0 && nums[i] <= numsLen && nums[i] != nums[nums[i] - 1]) {// 将nums[i]放到它应该在的位置 nums[i]-1swap(&nums[i], &nums[nums[i] - 1]);}}// 步骤二：遍历数组，找出第一个不符合要求的数字// 经过上一步，如果一个数字k存在，那么它一定在索引k-1的位置上for (int i = 0; i < numsLen; i++) {// 如果nums[i]不等于i+1，说明i+1这个正整数缺失了if (nums[i] != i + 1) {return i + 1;}}// 步骤三：如果所有数字都就位，说明缺失的是numsLen+1return numsLen + 1;
}5. 三数之和：排序与双指针的完美交响乐
5.1 题目分析与思路演进
三数之和是一个非常经典的面试题，它考察的是你如何把暴力解法的O(n^3)$时间复杂度优化到$O(n^2)。你给出的思路——排序加双指针——正是最优解。
5.1.1 思路分析：排序 + 双指针
核心逻辑：
第一步：排序。先对整个数组进行排序。这是关键，因为排序后，我们才能通过双指针来快速逼近目标和。
第二步：固定一个数。遍历数组，固定一个数
num[i]，把它作为三元组中的第一个元素。第三步：双指针逼近。在
num[i]后面的子数组中，设置两个指针left和right，分别指向子数组的头和尾。如果
num[i] + num[left] + num[right] == 0，找到一个解。如果
sum > 0，说明和太大，right向左移动，让和变小。如果
sum < 0，说明和太小，left向右移动，让和变大。
第四步：去重。由于数组中有重复数字，我们需要在每一步都进行去重处理，避免找到重复的三元组。
5.1.2 你的代码分析与优化
你的代码逻辑框架非常正确，看得出来你对这个方法理解很深。但有几个细节可以做得更好。
你的代码：
// ...
// int **threeSum(int *num, int numLen, int *returnSize, int **returnColumnSizes){
// // ...
// if (num == NULL || numLen < 3)
// {
// *returnSize = 0;
// returnColumnSizes = NULL;
// return num; // 错误：返回了原始数组，可能导致内存泄漏或错误
// }
// // ...
// }内存管理：在C语言中，动态分配的内存需要手动释放。你的代码在
if条件中返回了num，这很危险。正确的做法是返回NULL或者一个空数组。而且returnColumnSizes = NULL;会导致传入的指针无法被正确使用。去重逻辑：你考虑了
i的去重 (if (i > 0 && num[i] == num[i - 1]))，非常棒。但left和right的去重可以更简洁，并且要在找到解之后，立即进行去重操作，然后移动指针。
5.2 代码精讲与实现（排序+双指针）
下面我为你重写了这部分代码，并提供了详细的注释。这个版本修正了你的内存管理和去重逻辑，使其更加健壮。
#include <stdlib.h>
#include <string.h> // 使用 memcpy 和 memset// 比较函数，用于 qsort
int cmp(const void *a, const void *b) {return *(int *)a - *(int *)b;
}/*** @brief 在已排序的数组中，使用双指针找到三数之和为0的所有三元组。* @param nums int整型一维数组* @param numsLen int nums数组长度* @param returnSize int* 返回数组行数* @param returnColumnSizes int** 返回数组列数* @return int** 返回所有符合条件的三元组*/
int** threeSum(int* num, int numLen, int* returnSize, int** returnColumnSizes) {*returnSize = 0;// 检查边界条件if (num == NULL || numLen < 3) {*returnColumnSizes = NULL;return NULL;}// 步骤一：排序，这是双指针法的基础qsort(num, numLen, sizeof(int), cmp);// 为结果分配足够大的内存空间。在C语言中，这是一个挑战// 通常面试时会给出最大结果集，这里我们假设最坏情况int** result = (int**)malloc(sizeof(int*) * numLen * (numLen - 1) / 2);// 为每一行的列数分配内存*returnColumnSizes = (int*)malloc(sizeof(int) * numLen * (numLen - 1) / 2);// 步骤二：固定一个数，然后使用双指针for (int i = 0; i < numLen - 2; i++) {// 剪枝优化：如果当前数已经大于0，那么后面三个数的和不可能为0if (num[i] > 0) {break;}// 去重：如果当前数和前一个数相同，跳过以避免重复三元组if (i > 0 && num[i] == num[i - 1]) {continue;}int left = i + 1;int right = numLen - 1;while (left < right) {long long sum = (long long)num[i] + num[left] + num[right];if (sum == 0) {// 找到一个解，将其存储起来result[*returnSize] = (int*)malloc(sizeof(int) * 3);result[*returnSize][0] = num[i];result[*returnSize][1] = num[left];result[*returnSize][2] = num[right];(*returnColumnSizes)[*returnSize] = 3;(*returnSize)++;// 找到解后，移动指针并进行去重while (left < right && num[left] == num[left + 1]) {left++;}while (left < right && num[right] == num[right - 1]) {right--;}left++;right--;} else if (sum > 0) {// 和太大，右指针左移right--;} else {// 和太小，左指针右移left++;}}}return result;
}好了 已经干掉了“缺失的第一个正整数”和“三数之和”
缺失的正整数：我们学会了如何利用原地哈希这种神仙技巧，把哈希表装进了原数组里，用$O(1)$空间解决了问题。
三数之和：我们则重温了排序+双指针的经典套路，并重点梳理了去重逻辑，确保你的代码在面试时滴水不漏。
下一篇，咱们要聊聊哈希算法的本质，以及如何将这些思想应用到其他更复杂的题目中。那才是真正把技术内化成自己的东西
（4）：哈希算法的本质与进阶思维
6. 哈希的本质：映射与降维
6.1 什么是哈希？
在我们解题时，我们经常把哈希简单理解为“键值对”存储。但从底层来看，哈希的本质是一个映射函数，它将一个任意大小的输入（键）转换成一个固定大小的输出（哈希值）。
你可以用一张图来理解这个过程：
graph TDsubgraph "输入空间 (Keys)"A[任意数据<br>例如：字符串, 大整数]endsubgraph "哈希函数 (Hash Function)"B[f(key) -> hash_value]endsubgraph "输出空间 (Hash Values)"C[固定范围<br>例如：0 到 10000]endA --> BB --> C哈希表正是利用这个映射，将数据存储在一个数组里。这个数组的索引，就是哈希值。
6.2 原地哈希：将数组本身当做哈希表
在“缺失的第一个正整数”那道题中，我们使用的原地哈希，就是对哈希思想的一个极致应用。我们没有创建任何新的数据结构，而是把数组本身作为了哈希表。
它的核心逻辑可以被抽象为：
将数字 k 映射到数组索引 k−1 的位置。
这种方法之所以奏效，是因为：
映射关系简单：
f(k) = k - 1，这是一个最简单的哈希函数。无冲突：因为题目限制了数字都是正整数，且我们只关心
1到numsLen的范围，所以每个数字都有一个唯一的“归宿”索引。
这给了我们一个重要的启示：在解决问题时，不要总想着创建新的数据结构，有时候，利用已有的数据结构（比如数组）的特性，也能实现哈希的功能。
6.3 进阶思考：哈希冲突与解决方案
如果哈希函数没有那么完美，会发生什么？哈希冲突。
哈希冲突（Hash Collision）： 两个不同的输入，通过哈希函数计算得到了相同的哈希值。
在实际的哈希表中，哈希冲突是无法避免的。我们通常通过两种方式来解决：
链地址法（Separate Chaining）：
在哈希表中的每个桶（数组元素）里，维护一个链表。
当发生冲突时，将新的元素添加到对应桶的链表末尾。
优点：实现简单，对哈希表的大小不敏感。
缺点：需要额外的内存来存储链表节点，且查找效率取决于链表的长度。
开放寻址法（Open Addressing）：
当发生冲突时，不是去创建链表，而是在数组中寻找下一个可用的空位。
寻找空位的方法有很多，比如线性探测（Linear Probing）或二次探测（Quadratic Probing）。
优点：不需要额外的内存，数据都存储在连续的内存块中，缓存命中率高。
缺点：容易产生**“聚集”**现象，导致连续空位被占满，查找效率下降。
这两个方法在不同的场景下各有优劣。作为嵌入式程序员，理解这两种底层实现，对于选择合适的数据结构至关重要。
7. 超越哈希：从数据结构到算法思维的融合
7.1 三数之和：排序 + 双指针 + 去重
“三数之和”这道题，我们用的是排序和双指针，但这和哈希有什么关系呢？
关系一：降低复杂度。哈希算法的核心在于将
O(n)的查找时间降到O(1)。而排序 + 双指针，则将一个O(n^3)的暴力解法降到了O(n^2)，它们都是在时间复杂度上做文章。关系二：解决查找问题。哈希表通过映射来解决查找问题。而双指针则是在一个有序空间里，利用两个指针的相对移动，来高效地寻找满足条件的组合。它们殊途同归，都是为了提高查找效率
这个过程可以被抽象为：
graph TDsubgraph "暴力解法 (O(n^3))"A[三重循环<br>i, j, k 遍历数组]endsubgraph "优化解法 (O(n^2))"B1[1. 排序数组<br>(O(n log n))]B2[2. 固定一个数 i<br>(O(n))]B3[3. 双指针 left, right<br>(O(n))]B1 & B2 & B3 --> B4[总复杂度 = O(n^2)]endA --> B4双指针法，就是哈希表在有序数据中的一种变体。
7.2 摩尔投票法：从空间到算法的降维打击
“摩尔投票法”这道题，最直观的哈希解法是O(n)时间，O(n)空间。而摩尔投票法是O(n)时间，O(1)空间。
这又给我们一个重要的启示：
如果题目有特殊的限定条件（比如“超过一半”），那么很可能存在一个比常规数据结构更高效的算法。
摩尔投票法就是利用了“超过一半”这个限定，巧妙地通过计数器来抵消不同元素的影响。它把一个看似需要额外空间来解决的问题，转换成了一个纯粹的算法问题。这是一种思维上的降维打击。
7.3 位运算（异或）：从逻辑到硬件的降维
在“出现一次的两个数字”这道题中，我们从哈希表跳到了异或运算。
异或运算是比加减乘除更底层的运算，它直接在二进制位上操作。这种方法之所以高效，是因为它将一个逻辑问题（找出两个不同的数）转换成了一个位运算问题。
这种转换，就像把一个复杂的软件问题，交给了底层的硬件去解决一样，效率自然是最高的。
8. 总结与超越：你的算法之路
好了，兄弟们，我们已经走完了哈希算法的全部旅程。从这里开始，你的算法思维将进入一个新的阶段。
当遇到查找或去重问题时，你不再只想到哈希表，而是会思考：有没有可能用双指针？或者利用数组本身进行原地哈希？
当遇到特殊的限定条件时，你不再只是照搬模板，而是会想：这个条件能不能成为我解决问题的突破口？就像摩尔投票法一样。
当看到数字或位相关的题目时，你不再惧怕，而是会想起异或运算这种神奇的魔法。
你的思维路径，将从： 看题目 -> 找数据结构 -> 写代码
进化为： 看题目 -> 分析问题本质 -> 寻找最合适的算法思想 -> 选择/设计数据结构 -> 实现代码
总之，算法算法，写多了，自然就会了~
*** 附录：源码
1 出现次数超过一半的数字
思路：>>>>> 搞一个count 、flag作为当时的数字的记载器，一个个遍历，一个样的就加一个，不一样就扣一个
// #include <stdio.h>
// #include <stdlib.h>// int MoreThanHalfNum_Solution(int *numbers, int numbersLen)
// {
// // int hash[10001] = {0};
// // for(int i=0;i<numbersLen){
// // hash[numbers[i]]=1;
// // }// // for(int i=0;i<numbersLen;i++){
// // if(hash[i]>numbersLen/2){
// // return i;
// // }
// // }// // #2ˢ
// // int hash[10001] = {0};// // for (int i = 0; i < numbersLen; i++)
// // {
// // hash[numbers[i]]++;
// // }
// // for (int i = 0; i <= 10000; i++)
// // {
// // if (hash[i] > numbersLen / 2)// // {
// // return i;
// // }
// // }// // #3ˢ
// int hash[1000000] = {0};// for(int i =0;i<numbersLen;i++){
// hash[numbers[i]]++;
// }
// for(int i = 0;i<numbersLen;i++){
// int temp = numbers[i];
// if(hash[temp]>numbersLen/2){
// return temp;
// }
// }// return -1;
// }// #3刷
int MoreThanHalfNum_Solution(int *numbers, int numbersLen)
{int count = 1;int flag = numbers[0];for (int i = 1; i < numbersLen; i++){if (count == 0){flag = numbers[i];count += 1;}else{if (numbers[i] == flag){count++;}else{count--;}}}return flag;
}2 出现一次id两个数字？
思路：访问到了在hash里面加一个。。。。最后统计哪些==1
源码：
#include<stdio.h>
#include<stdlib.h>
#define MAX_size 1000000int* FindNumsAppearOnce(int* nums, int numsLen, int* returnSize ) {// write code here// int hash[MAX_size] = {0};// for(int i = 0 ;i<MAX_size;i++){// printf("%d\n,",hash[i]);// }// for(int i = 0 ;i<numsLen;i++){// hash[nums[i]]++;// }// int* res = (int*)malloc(sizeof(int));// int cnt = 0;// for(int i = 0;i<numsLen;i++){// if(hash[nums[i]]==1){// res[cnt++] = nums[i];// if(cnt==2){// break;// }// }// }// if(res[0]>res[1]){// int t = res[0];// res[0] = res[1];// res[1] =t ;// }// return res;int hash[1000000] ;for(int i=0;i<1000000;i++){hash[i]=0;}for(int i = 0;i<numsLen;i++){hash[nums[i]]++;}int* res = (int*)malloc(2*sizeof(int));int count=0;for(int i =0;i<MAX_size;i++){if(hash[i]==1){res[count++] = i;}}if(res[0]>res[1]){int temp = res[0];res[0] = res[1];res[1] = temp;}return res;
}int main(){int a =6;int *size_a = &a;int arr[6] = {1, 2, 1, 3, 2, 4};int* res = (int*)malloc(2*sizeof(int));res = FindNumsAppearOnce(arr,6,size_a);printf("res is :%d -%d\n",res[0],res[1]);printf("yeah\n");return 0 ;
}3 缺失的第一个正整数：
思路：一个个遍，最终的效果应该达到： 0 1 2 3 这些位置的数字 【 1 2 3 4】》 第0个 就是 0+1
如果nums[i !=i+1 就直接替换！
源码：
/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param nums int整型一维数组* @param numsLen int nums数组长度* @return int整型*/
int minNumberDisappeared(int *nums, int numsLen)
{// write code herefor (int i = 0; i < numsLen; i++){while (nums[i] > 0 && nums[i] < numsLen && num[i] != i + 1){int temp = nums[i];int nums[i] = nums[temp - 1];num[temp - 1] = temp;}}for (int i = 0; i < numsLen; i++){if (num[i] != i + 1){return i + 1;}}return numsLen + 1;
}4 三数之和：
双指针 不断逼近！本来是O（N^3），直接变成n^2
i从0到numlen遍历，left++从i+1，right--从numLen-1，如果num=0，就进行相应处理
/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param num int整型一维数组* @param numLen int num数组长度* @return int整型二维数组* @return int* returnSize 返回数组行数* @return int** returnColumnSizes 返回数组列数*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int cmp(const void *a, const void *b)
{return *(int *)a - *(int *)b;
}int **threeSum(int *num, int numLen, int *returnSize, int **returnColumnSizes)
{// write code hereif (num == NULL || numLen < 3){*returnSize = 0;returnColumnSizes = NULL;return num;}qsort(num, numLen, sizeof(int), cmp);int maxSize = numLen * numLen;int **res = (int **)malloc(maxSize * sizeof(int *));*returnColumnSizes = (int *)malloc(maxSize * sizeof(int));for (int i = 0; i < numLen - 2; i++){int left = i + 1;int right = numLen - 1;// 和之前一眼的 去掉// if (num[i] == num[i + 1])// {// continue;// }if (i > 0 && num[i] == num[i - 1]){continue;}while (left < right){int sum = num[i] + num[left] + num[right];if (sum == 0){// 直接放进去// 这里还是写错了！！！res[*returnSize]res[*returnSize] = (int *)malloc(3 * sizeof(int));res[*returnSize][0] = num[i];res[*returnSize][1] = num[left];res[*returnSize][2] = num[right];(*returnColumnSizes)[*returnSize] = 3;(*returnSize) += 1;// 去掉重复的while (left < right && num[left] == num[left + 1]){left++;}while (left < right && num[right] == num[right - 1]){right--;}left++;right--;}else if (sum > 0){right--;}else{left++;}}}return res;
}