涉及题目：

序号	题号	题目名称	练什么	说明
9	1	两数之和	暴力/哈希	LeetCode第一题，用双重for循环暴力做就行，不需要哈希表
10	26	删除有序数组中的重复项	快慢指针	原地操作数组，练习用双指针在一个数组上做原地修改
11	27	移除元素	快慢指针	和26类似，原地移除指定值
12	283	移动零	快慢指针	把所有0移到数组末尾，非零元素保持相对顺序
13	88	合并两个有序数组	双指针	从后往前合并，避免覆盖。注意边界条件
14	11	盛最多水的容器	左右双指针	左右两个指针向中间逼近，理解为什么矮的那边要移动
15	15	三数之和	排序+双指针	先排序，固定一个数，另外两个用双指针找。注意去重
16	704	二分查找	二分法	最基础的二分查找，注意左闭右闭和左闭右开两种写法

一、数组基础

1. 数组的本质

• 一块连续内存，存放相同类型的多个元素
• 通过索引 O(1) 访问任意位置（起始地址 + 索引 × 元素大小）
• 索引从 0 开始，长度为 n 的数组合法索引是 0 到 n-1
• C 语言不检查越界，越界访问可能崩溃或产生诡异 bug，必须自己保证索引合法

2. 初始化注意事项

int arr[5];              // 未初始化，里面是随机值
int arr[5] = {0};        // 全部初始化为0
int arr[5] = {1, 2};     // 部分初始化，剩余位置自动填0 → {1,2,0,0,0}

未初始化的栈上数组里是随机值，要用的话先显式初始化。

3. 数组名与指针的关系

• 数组名在大多数上下文里自动转换为指向第一个元素的指针
• arr[i] 和 *(arr+i) 完全等价
• 指针也可以用下标访问：int *p = arr; p[2] 等价于 arr[2]
• 区别：数组名是常量不能赋值（arr = arr+1 非法），指针是变量可以赋值

4. 数组作为函数参数会退化成指针

void func(int arr[], int n) {  }
// int arr[] 实际上就是 int *arr，sizeof(arr) 得到的是指针大小（8字节），不是数组大小

推论：函数内部无法通过 sizeof 获取数组长度，必须额外传入长度参数。 LeetCode 的函数签名就是这样设计的，数组和长度作为两个参数传入。

5. 在定义数组的作用域内获取长度

int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);   // 5

仅在定义数组的那个函数内有效，传进别的函数就失效了。

二、双指针技巧

1. 对撞指针（左右双指针）

模式：left 从头、right 从尾，向中间靠拢，每轮至少移动其中一个指针。

int left = 0, right = n - 1;
while (left < right) {
    // 根据条件决定移动left还是right
    left++;
    right++;
}

核心原理：利用有序性或问题结构，每次移动排除一批不可能的组合，把 O(n²) 降到 O(n)。

应用一：有序数组中找两数之和

思路：

1. left 从头，right 从尾
2. 算 nums[left] + nums[right]
3. 等于 target → 找到了
4. 小于 target → left++（让和变大）
5. 大于 target → right--（让和变小）

为什么能排除：如果和太小，说明 nums[left] 和当前 nums[right] 都配不上，而 right 左边的数更小更配不上，所以 nums[left] 可以排除，left++。反向同理。

应用二：盛最多水的容器（题目11）

容积 = 宽 × min(左柱高度, 右柱高度)

思路：

1. left 从头，right 从尾（初始宽度最大）
2. 每轮计算容积，更新最大值
3. 移动较矮的那根柱子

为什么移动矮的：假设左柱矮。不管右柱怎么往左移，min 里还是左柱（它最矮），而宽度又在缩小，所以容积只会更小。左柱已经"用完了"，必须换一根更高的试试，所以 left++。

应用三：三数之和（题目15）

思路：固定一个数 + 对撞指针找另外两个

1. 先对数组排序
2. for 循环固定第一个数 nums[i]
3. 在 i 右边的区间，用对撞指针找两数之和为 -nums[i]
4. 去重：固定的数和前一个相同就跳过；找到一组解后左右指针跳过相邻的相同值

时间复杂度从暴力 O(n³) 降到 O(n²)。

---

2. 快慢指针（同向双指针）

模式：两个指针从同一端出发，同方向移动。快指针扫描每个元素，慢指针标记结果位置。

int slow = 0;
for (int fast = 0; fast < n; fast++) {
    if (满足保留条件) {
        nums[slow] = nums[fast];
        slow++;
    }
}
// slow就是结果数组的长度

核心：慢管结果，快管扫描。

slow 的含义：slow 代表"下一个要写入的位置"。写入后 slow++，位置前进。所以是先写后加，不是先加后写。

应用一：移除指定元素（题目27）

原地移除所有等于 val 的元素，返回新长度。

思路：

1. fast 从头到尾遍历
2. nums[fast] != val（要保留）→ 写入 nums[slow]，slow++
3. nums[fast] == val（要删除）→ 跳过，fast 继续
4. 返回 slow

int slow = 0;
for (int fast = 0; fast < numsSize; fast++) {
    if (nums[fast] != val) {
        nums[slow] = nums[fast];
        slow++;
    }
}
return slow;

应用二：删除有序数组的重复项（题目26）

有序数组原地去重，每个元素只保留一次。

思路（和27略有不同）：

1. slow 指向"当前最后一个有效元素"（从0开始）
2. fast 从1开始遍历
3. nums[fast] != nums[slow]（是新值）→ slow++ 然后写入 nums[slow]
4. 相等则跳过
5. 返回 slow + 1（slow 是最后一个有效元素的索引，长度 = 索引 + 1）

int slow = 0;
for (int fast = 1; fast < numsSize; fast++) {
    if (nums[fast] != nums[slow]) {
        slow++;
        nums[slow] = nums[fast];
    }
}
return slow + 1;

和题目27的区别：27的slow是"下一个要写入的位置"，返回slow；26的slow是"最后一个有效元素"，返回slow+1。两种都是快慢指针，只是细节不同。

应用三：移动零（题目283）

把所有0移到末尾，非零元素保持相对顺序。

思路：本质就是题目27 val=0 的版本，多一步把 slow 之后的位置填0。

1. 用快慢指针把所有非零元素移到前面
2. slow 之后的位置全部填0

---

3. 从后往前的双指针

使用场景：从前往后操作会覆盖还没处理的数据，从后往前可以避免覆盖。

应用：合并两个有序数组（题目88）

nums1 后面留了空位，把 nums2 合并进 nums1。

思路：

1. 三个索引：i = m-1（nums1有效部分末尾），j = n-1（nums2末尾），k = m+n-1（nums1最终末尾）
2. 比较 nums1[i] 和 nums2[j]，较大的放到 nums1[k]，对应指针前移，k--
3. 某一方遍历完后，如果 nums2 还有剩余就复制到 nums1 前面；nums1 有剩余不用管（本来就在正确位置）

int i = m - 1, j = n - 1, k = m + n - 1;
while (i >= 0 && j >= 0) {
    if (nums1[i] > nums2[j]) {
        nums1[k--] = nums1[i--];
    } else {
        nums1[k--] = nums2[j--];
    }
}
while (j >= 0) {
    nums1[k--] = nums2[j--];
}

为什么 nums1 剩余不用管：如果 nums2 先处理完，说明 nums1 剩余的都更小，它们本来就在 nums1 前面的正确位置。

为什么从后往前：nums1 后面是空位，从后往前写入不会覆盖 nums1 前面还没处理的有效数据。

三、二分查找

1. 核心思想

在有序数组中，每次和中间元素比较，根据结果排除一半范围。

前提条件：数组必须有序。

时间复杂度：O(log n)。 100万个元素只需要约20次比较。

每次比较后搜索范围缩小一半：n → n/2 → n/4 → ... → 1。

缩小 k 次后范围变成 n/2^k，当 n/2^k = 1 时 k = log₂n。所以最多比较 log₂n 次。

2. 基本思路

1. 维护搜索区间 [left, right]
2. 取中间位置 mid
3. 比较 nums[mid] 和 target：

• • 相等 → 找到了，返回 mid
  • nums[mid] < target → 目标在右半边，left = mid + 1
  • nums[mid] > target → 目标在左半边，right = mid - 1

1. 区间缩小到空（left > right）还没找到 → 返回 -1

3. mid 的安全计算

// 不用 (left + right) / 2，因为当数太大时 left+right 可能溢出
int mid = left + (right - left) / 2;

4. 两种区间写法

推荐用左闭右闭，更直观。两种写法的关键区别：

	左闭右闭 [left, right] （推荐）	左闭右开 [left, right)
right 初始值	n - 1	n
while 条件	left <= right	left < right
往左缩时 right =	mid - 1	mid
往右锁时 left=	mid + 1	mid + 1

三点必须一致，不能混用。 比如用了 right = n-1 但 while 写了 left < right，会漏掉最后一个元素。

5. 左闭右闭写法的逻辑解释

• right = n - 1：右端点在搜索范围内，所以初始化为最后一个元素的索引
• left <= right：left == right 时区间 [x, x] 还有一个元素要检查，所以用 <=
• left = mid + 1 / right = mid - 1：if语句以及检查过 mid 不是 target，排除 mid 本身

6. 完整代码（题目704）

int search(int* nums, int numsSize, int target) {
    int left = 0;
    int right = numsSize - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

四、LeetCode C语言函数签名

1. 三种常见数组题的函数签名模式

模式一：原地修改，返回新长度（题目26、27、283）

int removeDuplicates(int* nums, int numsSize) {
    // 直接在nums上操作，返回有效长度
    return int;
}

最简单，不需要创建新数组。

模式二：返回一个新数组（题目1）

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    // 返回值：malloc分配的结果数组
    // returnSize：输出参数，告诉调用者结果数组有几个元素
}

涉及两个关键点：returnSize 和 malloc 返回数组。

（1）returnSize 是什么

问题：C 函数只能 return 一个值，但返回数组需要两个信息（地址 + 长度）。数组地址用 return 传，数组长度通过 returnSize 参数传出。

本质：returnSize 是 int*，指向调用者的一个 int 变量。在函数里通过解引用 *returnSize = 值 写入，调用者就知道数组长度了。就是"想在函数内修改外面的变量，传地址"的应用。

*returnSize = 2;    // 告诉调用者：返回的数组有2个元素
return result;      // 返回数组地址

没有答案时：*returnSize = 0; return NULL;

（2） 为什么必须用 malloc 创建返回的结果数组

绝对不能返回局部数组：

int result[2] = {i, j};
return result;    // x 函数返回后栈上的result被释放，返回的指针变成野指针

局部变量的生命周期和函数绑定，函数返回后这块内存就无效了。必须用 malloc 在堆上申请，堆内存不会因为函数返回而被释放

必须用 malloc 在堆上分配：

int *result = (int *)malloc(sizeof(int) * 2);
result[0] = i; //结果数组赋值
result[1] = j;
return result;    // ✓ 堆内存不会因函数返回而释放

malloc 返回的指针可以像数组一样用下标访问（result[0]、result[1]）。

需要全零数组时可以用 calloc，calloc申请的数组会自动赋值0，避免使用malloc申请后还要手动memset清零：int *arr = (int *)calloc(n, sizeof(int));

malloc数组的标注写法

// 需要n个int的数组
int *arr = (int *)malloc(sizeof(int) * n);

// 使用方式和普通数组完全一样
arr[0] = 10;
arr[1] = 20;
// ...

malloc 返回的指针可以像数组一样用下标访问（前面提到过，指针可以用下标访问）。arr[i] 等价于 *(arr + i)。

（3） 返回数组的题目完整模板

以题目1为例：

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    for (int i = 0; i < numsSize; i++) {
        for (int j = i + 1; j < numsSize; j++) {
            if (nums[i] + nums[j] == target) {
                int *result = (int *)malloc(sizeof(int) * 2);
                result[0] = i;
                result[1] = j;
                *returnSize = 2;
                return result;
            }
        }
    }
    *returnSize = 0;
    return NULL;
}

模式三：返回二维数组（题目15）

签名更复杂，涉及 int** 和 returnColumnSizes，做到那道题时再具体分析。

2. 排序：qsort

好几道题需要先排序。C 语言用 qsort，需要自己写cmp比较函数，当固定模板记：

#include <stdlib.h> （这句include不需要写，力扣环境自带）

// 写比较函数（升序），如果是降序只需要return (*(int *)b) - (*(int *)a);
int cmp(const void *a, const void *b) {
    return (*(int *)a) - (*(int *)b);
}

// 主函数：调用：qsort(数组, 元素个数, 每个元素字节数, 比较函数)，调用后该数组原地自动是排好序的结果
qsort(nums, numsSize, sizeof(int), cmp);

比较函数返回值含义：负数 → a排前面，0 → 相等，正数 → b排前面。a - b 就是升序。

---

3. 其他工具

求最大值/最小值（C 语言没有内置 max/min）：可以写宏，也可以直接函数里三元运算符

// 方式一：宏定义（写在函数外面）
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))

// 方式二：直接在代码里用三元运算符
int maxVal = (a > b) ? a : b;

求绝对值：

#include <stdlib.h>
int absVal = abs(x);  // 整数绝对值