算法方法

总导航：算法与开发

这里记录解题时最常用的策略判断。二分、贪心和枚举现在统一在一个主笔记中，方便从问题特征直接选择方法；它们的适用条件和推理方式不同，因此以下章节仍然分开说明。

先判断问题，再选择算法

不要从“我想套哪个模板”开始，而要先写出候选空间、约束和可验证的性质：

先用可证明的基线得到正确答案，再考虑优化；优化必须保留边界样例和复杂度说明。

1. 二分查找：先证明单调性

二分适合在有序、单调或可判定的答案空间中不断缩小区间。使用前先明确：区间边界、判定函数的单调方向，以及循环结束时 left/right 的含义。若题目数据无序，先排序再查找；排序复杂度为 \(O(n\log n)\)，单次二分为 \(O(\log n)\)。

使用 C 的排序函数时，可以先用 qsort 准备有序数据：

#include <stdlib.h>

static int cmpInt(const void* a, const void* b) {
    int x = *(const int*)a;
    int y = *(const int*)b;
    return (x > y) - (x < y); // 避免使用 x - y 导致溢出
}

qsort(nums, numsSize, sizeof(int), cmpInt);

比较函数约定：compar(a,b) < 0 时 a 在 b 前，> 0 时 a 在 b 后，等于 0 时顺序不作要求。不要用 x - y 直接比较有符号整数，可能溢出。abs 用于取绝对值，使用前需包含 <stdlib.h>。

2. 枚举与贪心：区分“可遍历”与“可证明”

枚举是把候选状态按规则逐一试遍；例如 1423 题可以枚举从左端取多少个元素，右端数量由总数决定，再计算每一种取法的总和。若候选规模为 \(k\)，直接枚举通常是 \(O(k)\)，适合先作为正确性基线。

贪心则是在每一步选择当前看起来最优的分支。只有当局部最优能证明导向全局最优，并且选择不会破坏后续可行性时才可使用。若第一步无法证明，或后续选择可能推翻前面的判断，就应改用枚举、动态规划或其他可证明的方法。

1423 题的练习结论：枚举左端取值即可覆盖全部候选，右端取值由总长度确定；逐一计算区间和可以作为正确性基线。贪心方案无法在第一步证明局部最优会导向全局最优，因此不采用该方案。

3. 选型顺序

• subarray（连续）：优先考虑滑动窗口、前缀和或双指针。
• subsequence（不连续）：常见组合是排序 + 贪心，也可能需要前缀和或二分。
• 先检查单调性和可证明的局部最优；没有证明时，保留枚举作为基线，再比较复杂度和边界条件。

验证与复盘

每个新方法至少保留三类测试：最小输入、边界输入和会触发分支切换的输入。记录“为什么成立”与“在哪些条件下失效”，不要只保留一组通过样例。这样枚举可以作为正确性基线，二分可以核对边界收缩，贪心则必须能回溯到证明假设。