分类： 技术分享

今天这篇讲的是 1477. 找两个和为目标值且不重叠的子数组（Medium）。它看着像滑动窗口题，但第一次提交前把我绊住的，恰恰不是滑动窗口——而是一个关于「状态里该装什么」的问题。下面按我的实际推演顺序写。

零、先把题目摊开（复述）

这一节要拿到的东西：把题面翻译成自己的话，并且圈出那三句会决定代码长什么样的规则。

题面是：给你一个整数数组 arr 和一个整数 target，找两个互不重叠的子数组，让它们的和都等于 target，返回这两个子数组长度和的最小值；找不到就返回 -1。

里面有三句话直接决定代码长什么样，我先把它们钉死：

• 「子数组」是连续的——所以可以用区间 [l, r] 表示一段，这决定了后面全是区间运算。
• 「互不重叠」指两个区间的下标集合没有交集。首尾相接是合法的：[0,1] 和 [2,3] 不算重叠。这一条是本题最大的坑，也是最大的福利——它让「切一刀」的玩法成立。
• 「长度和最小」说明不是随便找一对，而是要在所有合法方案里比较总长度。这意味着我们最终要做的是「取最小值」，而不是「计数」。

约束方面只记两条：n ≤ 10⁵，以及 arr[i] 全为正数（1 ≤ arr[i] ≤ 1000）。前者说明 O(n²) 会超时，后者是后面所有 O(n) 玩法的地基——没有「全为正」，这题会变成另一道题。

一、建模：把它画出来

这一节要拿到的东西：一张能让你「看见」题目的图，以及一句话说清「我在挑什么」。

把数组画成一排格子，每一段就是几个连续的格子。于是题目变成：在格子排队上挑两组不相交的连续格子，两组各自的数字和都是 target，让两组格子总数的和最小。

图里下面那行是关键的对照：arr[0..1] 与 arr[1..2] 都合法地为和为 target 的段，但它们共用了下标 1，因此不能同时选。这个「不能同时选」就是本题的全部难点。

二、手数最小规模：这是整道题的地基

这一节要拿到的东西：一组能手工验证的答案，它是你以后验任何代码的标尺。

拿官方第一组示例 arr = [3,2,2,4,3]、target = 3 手工数：和为 3 的连续段有两处——arr[0]（值 3）与 arr[4]（值 3）。它们不相交，长度和 1 + 1 = 2。这个好数。

换官方第三组 arr = [4,3,2,6,2,3,4]、target = 6，我第一遍就数错了——我以为有两段，其实只有一段。为了不再靠感觉，我写了个四行的枚举程序把五组示例全部跑出来，实测结果如下：

arr=[3,2,2,4,3]        target=3  合格段: [0..0][4..4]                    答案 = 2
arr=[7,3,4,7]          target=7  合格段: [0..0][1..2][3..3]              答案 = 2
arr=[4,3,2,6,2,3,4]    target=6  合格段: [3..3]                          答案 = -1
arr=[5,5,4,4,5]        target=3  合格段: (无)                             答案 = -1
arr=[3,1,1,1,5,1,2,1]  target=3  合格段: [0..0][1..3][5..6][6..7]        答案 = 3

两组数字值得停下来看：例 2 有三段合格段（[0..0]、[1..2]、[3..3]），最优选法是取两头各长 1 的，答案是 2；例 5 有四段，其中 [5..6] 与 [6..7] 共用下标 6，不能同时选，最优是 [0..0] + [5..6] = 1 + 2 = 3。

这一节真正的收获不是那五个数字，而是方法：这道题的「合格段」肉眼很难数准（我第一遍就错了），所以从下一节开始，理解与验证都交给程序；手算只用来判断量级和建立直觉。

三、第一条路：暴力怎么做到不重不漏

这一节要拿到的东西：一条能写出来的完整解法（虽然会超时），以及它为什么不够快。

暴力路的思路最直白，分两步：先枚举出所有和为 target 的段，再在段表里两两挑一对不相交的，取长度和最小。

判交的条件值得写清楚，因为它是后面所有优化的基础：两段 [a,b] 与 [c,d]（假设 a ≤ c）不重叠 ⇔ b < c。注意是 < 而不是 ≤——首尾相接（b = c−1）是合法的。

vector<pair<int,int>> seg;                 // 先枚举所有合格段
for (int i = 0; i < n; ++i) {
    long long sum = 0;
    for (int j = i; j < n; ++j) {
        sum += arr[j];
        if (sum == target) seg.push_back({i, j});
        if (sum > target) break;             // 是 > 不是 >=
    }
}
int best = -1;                            // 再两两判交
for (size_t a = 0; a < seg.size(); ++a)
    for (size_t b = a + 1; b < seg.size(); ++b) {
        if (!(seg[a].second < seg[b].first || seg[b].second < seg[a].first)) continue;
        int len = (seg[a].second - seg[a].first + 1) + (seg[b].second - seg[b].first + 1);
        if (best == -1 || len < best) best = len;
    }

四、第二条路：设计状态，把「选」变成「递推」

这一节要拿到的东西：一个能一趟扫完的状态定义，以及它第一次写错的原因（这一段是本篇最值钱的部分）。

暴力慢在「两两判交」。想一趟扫完，直觉是：边扫边记住「左边出现过的最短段长」，遇到新段就拼接。

我第一版就是这么写的，而且官方给的五组示例全过。但它有个致命缺陷：我只记住了「最短段有多长」，没记住「那段落在哪里」。当新段与那个「最短段」共用了格子时，代码照样把它们相加——于是给出一个比正确答案更小的数。

const int n = (int)arr.size(), INF = 1e9;
vector<int> bestUpTo(n, INF);            // bestUpTo[e]：右端点 <= e 的最短合格段长
unordered_map<long long,int> pos; pos[0] = 0;   // P[0] = 0，下标 0
long long pre = 0; int ans = INF;
for (int i = 1; i <= n; ++i) {
    pre += arr[i-1];
    auto it = pos.find(pre - target);
    if (it != pos.end()) {
        int start = it->second;           // 段 = arr[start .. i-1]
        int len = i - start;
        if (start - 1 >= 0 && bestUpTo[start - 1] != INF)
            ans = min(ans, bestUpTo[start - 1] + len);
        bestUpTo[i - 1] = min(bestUpTo[i - 1], len);
    }
    pos[pre] = i;
}
// 把 bestUpTo 变成真正的前缀最优（从右端点小的方向传递过来）
for (int e = 1; e < n; ++e) bestUpTo[e] = min(bestUpTo[e], bestUpTo[e - 1]);
return ans >= INF ? -1 : ans;

五、还有第三条路：滑窗找段 + 两侧最优 + 切一刀

这一节要拿到的东西：一个把「不重叠」彻底结构化的写法——它不需要任何判交，因此也不会写错判交。

上一节的解法已经能过，但它仍然在代码里依赖「查表 + 判断」。换个视角会舒服得多：任取一对不重叠的段，按右边那段的左端点切一刀，左边段必落在刀左侧、右边段必落在刀右侧。于是我们只需要两张表：

• bestEnd[r]：右端点 ≤ r 的所有合格段里最短的长度（前缀最优）。
• bestStart[l]：左端点 ≥ l 的所有合格段里最短的长度（后缀最优）。

然后枚举切点 k，答案就是 min(bestEnd[k-1] + bestStart[k])。两段分处切点两侧，不重叠由结构保证，代码里一个判交都不需要写。

「找段」这一步用滑动窗口，正好吃到「元素全为正」这个约束：右端右移和必增、左端右移和必减，所以 lo 与 hi 都只单向前进，总代价 O(n)。

// 第一步：滑动窗口找出所有合格段
vector<pair<int,int>> windows;
long long sum = 0; int lo = 0;
for (int hi = 0; hi < n; ++hi) {
    sum += arr[hi];
    while (sum > target && lo <= hi) sum -= arr[lo++];
    if (sum == target) windows.push_back({lo, hi});
}
// 第二步：两侧最优表
vector<int> bestEnd(n, INF), bestStart(n, INF);
for (auto& w : windows) {
    int len = w.second - w.first + 1;
    bestEnd[w.second]  = min(bestEnd[w.second], len);
    bestStart[w.first] = min(bestStart[w.first], len);
}
for (int r = 1; r < n; ++r)      bestEnd[r]   = min(bestEnd[r], bestEnd[r - 1]);
for (int l = n - 2; l >= 0; --l) bestStart[l] = min(bestStart[l], bestStart[l + 1]);

六、落地：我的提交代码

下面就是实际提交并通过的那一份（Accepted · 16 ms · 95.7 MB · 61/61），没有为了文章改过一行。

class Solution {
public:
    int minSumOfLengths(vector<int>& arr, int target) {
        const int n = (int)arr.size();
        const int INF = 1e9;

        // 第一步：滑动窗口找出所有和为 target 的段
        vector<pair<int, int>> windows;
        long long sum = 0;
        int lo = 0;
        for (int hi = 0; hi < n; ++hi) {
            sum += arr[hi];
            while (sum > target && lo <= hi) sum -= arr[lo++];
            if (sum == target) windows.push_back({lo, hi});
        }

        // 第二步：两侧最优表
        vector<int> bestEnd(n, INF), bestStart(n, INF);
        for (auto& w : windows) {
            int len = w.second - w.first + 1;
            bestEnd[w.second]  = min(bestEnd[w.second], len);
            bestStart[w.first] = min(bestStart[w.first], len);
        }
        for (int r = 1; r < n; ++r)      bestEnd[r] = min(bestEnd[r], bestEnd[r - 1]);
        for (int l = n - 2; l >= 0; --l) bestStart[l] = min(bestStart[l], bestStart[l + 1]);

        // 第三步：枚举切点
        int answer = INF;
        for (int k = 1; k < n; ++k) {
            if (bestEnd[k - 1] == INF || bestStart[k] == INF) continue;
            answer = min(answer, bestEnd[k - 1] + bestStart[k]);
        }
        return answer >= INF ? -1 : answer;
    }
};

复杂度：滑动窗口 O(n)（每个下标进出各一次），填两张表各 O(n)，枚举切点 O(n)，空间 O(n)。整体 O(n) 时间 / O(n) 空间。

七、验证：我为什么敢说它是对的

这一节要拿到的东西：一个叫对数器的小习惯——它比任何题解都值钱。

流程是三道关，一道都不能省：

• 第一关 · 官方示例：五组示例全过。但这一关几乎不能说明问题——本篇第一版错解就是五组全过的。
• 第二关 · 对数器：写一个「显然正确但很慢」的暴力实现，与正式解在20000 组随机小数据上逐一对比。这一关抓出了第一版的 1164 处不一致。
• 第三关 · 消毒器：用 -fsanitize=address,undefined 编译再跑一遍，确认没有越界与未定义行为。

八、复盘：今天能带走的东西

这一节要拿到的东西：一条可迁移的招式，和一条关于「写作纪律」的教训。

迁移卡（剥掉故事壳）：凡是「在序列上挑若干个互不相交的区间，使某个可加指标最优」的题，都可以先试着把「不相交」翻译成「按切点分左右」——然后用前缀最优 + 后缀最优把「两侧各取最优」压成 O(1) 查询，最后枚举切点拼答案。这套骨架的关键收益是：约束被结构吃掉了，而不是被 if 判断掉，因而没有判断写错的空间。

不能直接迁移的部分也要说清楚：本題「枚举所有合格段」这一步依赖元素全为正（滑窗的单调性）。换成正负混合，或者要求恰好 k 段（k > 2），枚举那一步必须换手段；但「切点 + 两侧最优」这一半依然成立。

另一条教训是关于写作本身的。本文的第二节我用手算给出了第三组示例的段，而且是错的——我在正文里连续算错两次，最后才意识到该用脚本枚举。这暴露了一个纪律问题：文章里出现的每一个数字都必须是程序输出，不能是手算；手算只能用来做「量级判断」和「理解过程」，一旦要写进文章，就必须有可复现的取值来源。这篇重写时我已经把该节改为如实记录这次纠错，并把所有数字换成实测输出。

附录 · C++ 小抄（小白版，逐条讲透）

上面那些折叠块是「卡住了才点」；这一节反过来——它不剧透任何东西，所以不折叠。每一条都按同一个套路讲：它是什么 → 为什么有用 → 一段能跑的代码 → 这道题里我用在哪。

1. vector<int> 与下标访问：本题的两种「容器」

它是什么：vector 是长度可变的数组；本题里我用了两种用法——vector<int> 装「每个位置的最优长度」，vector<pair<int,int>> 装「段的左右端点」。

为什么有用：前缀最优表需要按下标随机读写（bestEnd[r]），段的列表只需要顺序遍历。两种需求对应两种容器。

vector<int> bestEnd(n, INF);              // n 个元素，全部初始化为 INF
vector<pair<int,int>> windows;           // 空的，用 push_back 追加
windows.push_back({lo, hi});              // 追加一段
int len = w.second - w.first + 1;         // pair 用 .first / .second 取值

2. unordered_map：把「查找」变成 O(1)

它是什么：哈希表。本题用它存「某个前缀和出现在哪个下标」。因为元素全为正，每个前缀和的值只会出现一次，所以一个值对应一个下标，正好合适。

为什么有用：滑动窗口之外的另一条找段思路就是它——已知 P[i]，想知道「有没有某个 P[start] = P[i] − target」，查表 O(1)。

unordered_map<long long, int> pos;
pos[0] = 0;                               // 空前缀的和为 0，对应下标 0
long long pre = 0;
for (int i = 1; i <= n; ++i) {
    pre += arr[i-1];
    auto it = pos.find(pre - target);     // 找「能凑出这段的左端点」
    if (it != pos.end()) { /* 找到一段 */ }
    pos[pre] = i;
}

3. 前缀和：把「区间和」变成「两个数相减」

它是什么：P[i] 表示前 i 个元素之和。于是任意区间 [l, r] 的和 = P[r+1] − P[l]。

为什么有用：它把「区间和等于 target」这个关于一段的判断，变成了「两个前缀之差等于 target」这个关于两个点的判断——两个点的关系可以用哈希表或双指针解决。

vector<long long> P(n + 1, 0);
for (int i = 0; i < n; ++i) P[i+1] = P[i] + arr[i];
// 区间 [l, r] 的和： P[r+1] - P[l]

4. 双指针滑动窗口：单调性换来的 O(n)

它是什么：维护一个 [lo, hi] 窗口，hi 只增、lo 只增。本题靠「元素全为正」保证窗口和随 hi 增而增、随 lo 增而减。

为什么有用：如果 lo 会来回移动，复杂度就退化回 O(n²)；正因为两个指针都单向，总移动次数才是 2n。

long long sum = 0; int lo = 0;
for (int hi = 0; hi < n; ++hi) {
    sum += arr[hi];
    while (sum > target && lo <= hi) sum -= arr[lo++];   // lo 只前进
    if (sum == target) { /* 记录这段 */ }
}

5. long long：为什么区间和不能用 int 累加

它是什么：64 位整数。本题 n ≤ 10⁵、arr[i] ≤ 1000，总和最大 10⁸，仍在 int（约 2.1×10⁹）范围内——所以本题用 int 其实不会溢出。

为什么还是用 long long：这是习惯问题。target 的约束是 ≤ 10⁸，如果哪天数据范围上调（比如 arr[i] 到 10⁴），int 立刻溢出，而这类溢出在本地小数据上测不出来。用 long long 累加的成本可以忽略，收益是免掉一类难查的错。

6. INF 哨兵：怎么表达「还不存在」

它是什么：const int INF = 1e9;，用它表示「这个位置还没有任何合格段」。

为什么有用：取最小值时，不存在的值必须比任何真实值都大，否则会污染答案。本题 INF + INF = 2×10⁹ 仍在 int 内（上限约 2.147×10⁹），不会溢出——但只差一点点，所以更稳的写法是先判断 == INF 再相加。

const int INF = 1e9;
if (bestEnd[k - 1] == INF || bestStart[k] == INF) continue;   // 先挡掉「不存在」
answer = min(answer, bestEnd[k - 1] + bestStart[k]);
return answer >= INF ? -1 : answer;                           // 最后把 INF 翻译成 -1

7. 前缀最优 / 后缀最优：一个正扫、一个反扫

它是什么：把「每个位置自己的值」变成「到这个位置为止的最优值」。正向扫得到 bestEnd（右端点不超过 r 的最短长度），反向扫得到 bestStart（左端点不小于 l 的最短长度）。

为什么有用：它把「在某个范围内取最优」这件事预计算好，之后每个切点只需 O(1) 查询。这是用空间换时间最典型的形态，也是本题第三、四节的共同骨架。

for (int r = 1; r < n; ++r)      bestEnd[r] = min(bestEnd[r], bestEnd[r - 1]);     // 正向
for (int l = n - 2; l >= 0; --l) bestStart[l] = min(bestStart[l], bestStart[l + 1]); // 反向

8. std::span：不改所有权地「看见」一段内存（C++20）

它是什么：一个「指针 + 长度」的视图，不持有数据、不拷贝。span<const int> 表示「只读地看到一串 int」。

为什么有用：函数想接收「一段数组」时，老写法要么传 vector（绑死容器类型）、要么传「指针 + 长度」（两个参数容易配错）。span 一个参数就把两件事说清，而且能接 vector、原生数组、array 等各种来源。

void inspect(span<const int> s) {          // 不改内容、不拷贝
    int mx = *ranges::max_element(s);
    (void)mx;
}
vector<int> v{3, 2, 2, 4, 3};
inspect(v);                                 // vector 直接传
int raw[5] = {1, 2, 3, 4, 5};
inspect(raw);                               // 原生数组也能传

本题用在哪：如果要把「找最优段」抽成一个辅助函数，参数用 span<const int> 比 const vector<int>& 更通用——它同时接受 vector 与原生数组，而且明确表达「我只读、不持有」。力扣 C++23 环境实测可用（提交 749680173）。

9. std::views::iota + ranges::min：把「枚举下标」写成管道（C++20/23）

它是什么：views::iota(a, b) 生成 a, a+1, …, b-1 的惰性序列；views::transform(f) 把每个元素映射成 f(x)；ranges::min 取最小值。三者用 | 串起来就是一条管道。

为什么有用：本题「枚举切点 k，取 bestEnd[k-1] + bestStart[k] 的最小值」本质上是「对一串候选取最小」。老写法要写一个带 INF 哨兵的循环，管道写法直接表达意图，且不需要初始化哨兵。

// 老写法：手写循环 + INF 哨兵
int answer = INF;
for (int k = 1; k < n; ++k) {
    if (bestEnd[k-1] == INF || bestStart[k] == INF) continue;
    answer = min(answer, bestEnd[k-1] + bestStart[k]);
}
return answer >= INF ? -1 : answer;

// 管道写法：把「候选集合」直接表达出来
auto cand = views::iota(1, n)
          | views::filter([&](int k){ return bestEnd[k-1] != INF && bestStart[k] != INF; })
          | views::transform([&](int k){ return bestEnd[k-1] + bestStart[k]; });
return ranges::empty(cand) ? -1 : ranges::min(cand);

本题用在哪：两种写法都对、复杂度也相同（都是 O(n)）。但它读起来更像「在说什么」而不是「在怎么做」，所以我把它作为可选写法写在附录里，主解仍是循环版（第 六 节那份就是实际提交、通过 61/61 的版本）。力扣 C++23 环境实测可用：views::iota / views::transform / ranges::fold_left 均编译并通过求值（提交 749680038、749680173）。

10. std::ranges::fold_left：把整段「折」成一个值（C++23）

它是什么：C++23 新算法，签名是 fold_left(区间, 初值, 二元操作)，从左到右把整段折成一个值。它和 std::accumulate 的差别是：直接接受 range（不用写 begin/end），且能被管道喂进来。

为什么有用：凡是「遍历一遍、累加/累积/合并成一个值」的循环，都可以写成一行。它把「怎么遍历」从代码里拿掉，只留「怎么合并」——这正是本题「区间和」那类循环的常见形态。

vector<int> v{3, 2, 2, 4, 3};
long long total = ranges::fold_left(v, 0LL, plus<long long>());   // 14
// 配合管道：先映射再折
auto sum = ranges::fold_left(
    views::iota(1, 10) | views::transform([](int x){ return x * 2; }),
    0LL, plus<long long>());                                       // 90

本题用在哪：本题的「窗口和」是滑动的（右端加、左端减），fold_left 只做单向折叠，因此不适合替换主解的窗口维护——这正是第 4 条纪律「不许为了新而新」的例子：这里用它反而别扭。但它在「求整个数组的前缀和」「统计满足条件的个数」这类场景里很顺手，所以仍然收进小抄。

11. std::format / std::bit：格式化与位运算的小工具（C++20/23）

它是什么：std::format 是 printf 的类型安全替代（不写 %d、不会因为格式串和实参不匹配而崩）；std::bit_width(x) 返回表示 x 所需的位数，std::has_single_bit(x) 判断是不是 2 的幂。

为什么有用：调试时打日志、写对数器时输出用例，format 比 cout << 拼接或 printf 都清楚；位运算类题（本题标签里没有位运算，但位运算题很常见）用 bit_width 比手写 while (x) { x >>= 1; ++cnt; } 可靠。

string msg = format("k={} left={} right={}", k, bestEnd[k-1], bestStart[k]);   // 类型安全
int bitsNeeded = bit_width(255u);            // 8
bool isPow2 = has_single_bit(1024u);         // true

本题用在哪：写对数器时用 format 输出反例（比手拼字符串清楚，也不会像 printf 那样格式串写错就崩）；bit 里的工具本题没用到，但同栏目遇到位运算题会用到，一并收进小抄。力扣实测可用（提交 749680038 用到 format 与 has_single_bit）。

12. C++23 能力边界：什么能用、什么别用（实测）

它是什么：力扣 C++ 编译器的标准版本与特性支持范围——这一条不是语法，是「环境事实」。

为什么有用：用了环境不支持的写法，代价是一次编译错误和一个提交冷却；提前知道边界可以省掉这些。

本题用在哪：上面第 8–11 条能放心写，正是因为这一条先测过。**这张表随时会过期**——力扣升级编译器后要重新探。本文的探测方法很简单：把特性写进 Solution 提交，看它是「Compile Error」还是能跑到 WA/AC。

每天一题，重点从来不是那句答案，而是从毫无头绪到能自己推的那条路。今天这道 1621（Medium）的正解只有一行组合数 —— 但这一篇不直接抛公式：先圈规则，再手数最小规模，再写暴力，再设计状态，最后让公式自己浮出来。

零、先把题目摊开（复述）

这一节要拿到的东西：把题面翻译成自己的话，并且圈出那三句会决定代码长什么样的规则。

题意用我自己的话说一遍：一维空间里有 n 个点，第 i 个点在坐标 x = i。要选出恰好 k 条线段，每条线段的两个端点都是整数坐标、而且至少跨两个点（左端点 < 右端点）；这 k 条线段之间不重叠。问有多少种选法，答案对 10⁹ + 7 取模。

题面里有三句话必须圈出来，它们决定了后面每一行代码：

• 「每个线段至少覆盖两个点」 —— 所以端点满足 l < r，长度至少 1。
• 「端点可以重合」 —— 不重叠指的是没有公共的内部点，两条线段首尾相接是合法的。这一句是本题最大的坑，也是本题最大的福利。
• 「恰好 k 条」「不需要覆盖全部 n 个点」 —— 所以这是个”选”的问题，不是”分割/覆盖”的问题。

先自己回答这个问题（想好再看，瞄一眼就漏气了）：这题能不能直接当成「从 n 个点里选 2k 个点」来数？　看答案不能。因为每条线段的两个端点是一对（有配对关系），而且相邻线段可以共用端点 —— 直接数 C(n, 2k) 又漏又重。真正的答案要更”松”一点，第五节会推出来。

一、建模：把它画出来

这一节要拿到的东西：一张能让你”看见”题目的图，以及一句话说清”我在数什么”。

遇到”点、线、区间”这类题，第一件事永远是画图。这件事不剧透任何东西，所以直接看：

二、手数最小规模：这是整道题的地基

这一节要拿到的东西：n = 4, k = 2 的全部 5 种方案 —— 它是你以后验任何代码的标尺。

新手最容易跳过的一步，其实是最该做的一步：拿最小的合法输入，把所有方案全部写出来。先拿一张纸自己数，数完再点开下面那条 —— 答案和全部 5 种方案都在里面。

解答5 种方案 + 官方原图（剧透） · 约 2 分钟

5 种分别是：{(0,2),(2,3)}、{(0,1),(1,3)}、{(0,1),(2,3)}、{(1,2),(2,3)}、{(0,1),(1,2)}。

重点观察：其中 4 种都靠”共享端点”才成立，只有 {(0,1),(2,3)} 是完全分开的。如果题目改成”端点不许重合”，答案会从 5 直接掉到 1 —— 一句规则，差 5 倍。

三、第一条路：暴力怎么做到不重不漏

这一节要拿到的东西：一条能写出来的递推规则 + 一个合法的剪枝条件（含一个我写错过的版本）。

很多人写暴力会写成组合枚举（从所有线段里挑 k 条再判重），那样既慢又会重复。更聪明的做法是按位置递推地选：每次选定一条最靠左的线段 (a, b)，下一条线段的左端点必须 ≥ b。先自己想：递归的两个参数是什么？

解答暴力版思路 + 一个真实的踩坑（含图） · 约 2 分钟

递归参数 dfs(start, need)：从坐标 start 开始、还要选 need 条。枚举第一条线段 (a, b)（a ≥ start，b > a），然后递归 dfs(b, need − 1) —— 注意是 b 不是 b+1，因为端点可以重合。

剪枝条件是 n − start < need + 1：因为 need 条线段可以首尾相连，最少只需要 need + 1 个点。这里我第一次写成了 n − start < 2 * need（想当然地按”每条要 2 个点”算），结果 n=3, k=2 直接返回 0 —— 而正确答案是 1。

教训：剪枝写错不会报错，只会静默少算。所以暴力版必须拿”最小规模的全部答案”当标尺。

四、第二条路：设计状态，把”选”变成”递推”

这一节要拿到的东西：一个能回答”最后那个点用不用”的状态定义，以及把整列求和压成一次加法的技巧。

暴力的复杂度是指数级的。要提速，先问自己一句：我到底在重复计算什么？ 答案通常藏在一句话里 —— 前缀、后缀、或者”最后一个点用没用”。状态该怎么定？先想 3 分钟。

解答DP 状态与转移 + 两张表（剧透） · 约 3 分钟

令 f[i][j] = 前 i 个点（0 … i−1）里选 j 条线段的方案数。考虑第 i−1 个点：

① 不用它：方案数 = f[i−1][j]。

② 它是一条线段的右端点：设这条线段是 (m, i−1)，其中 1 ≤ m ≤ i−1；剩下的 j−1 条只能落在前 m+1 个点里（因为可以共用端点 m），即 f[m+1][j−1]。把 m 从 1 到 i−1 加起来。

合起来：f[i][j] = f[i−1][j] + Σ f[m][j−1]，答案就是 f[n][k]。用前缀和把那个 Σ 缓存成 S[i][j]，复杂度从 O(n²k) 降到 O(nk)。

用 n=4, k=2 验一遍：算出来是 5 —— 和第二节手数的一致，这就是好信号。

五、还有第三条路：能不能一行写完？

这一节要拿到的东西：一个闭式公式，以及它的严格来历（这一节是本篇最”值钱”的部分）。

如果你回头看 DP 那张表，会注意到一个巧合：j = 1 那一列是 1, 3, 6, 10 —— 那是 C(i, 2)。这种”表格里冒出组合数”的巧合，通常意味着这题有闭式解。这一节的问题是：能不能不递推，直接”数”出来？

解答公式 C(n+k−1, 2k) 与双射证明（剧透） · 约 3 分钟

第一步：把每条线段 (l, r) 记成两个数 l 和 r − 1，拼成序列 a = (l₁, r₁−1, l₂, r₂−1, …)。因为 l < r 且相邻线段端点可以重合，这个序列满足 a₁ ≤ a₂ < a₃ ≤ a₄ < …：对内有等号，对间严格小于。

第二步：给第 j 个数加上 ⌊j/2⌋，得到 b_j。等号被”撑开”了，b 变成严格递增序列；而它的取值范围是 0 … n+k−2，一共 n+k−1 个位置。

第三步：于是「选 k 条不重叠线段」和「从 n+k−1 个位置里选 2k 个」一一对应 —— 后者就是 C(n+k−1, 2k)。

真例验证：{(0,1),(2,3)} → a = (0, 0, 2, 2) → b = (0, 1, 3, 4)，而 C(5, 4) = 5，正是那 5 种。

六、落地：我的提交代码

下面就是实际提交并通过的那一份（Accepted · 0 ms · 68/68），没有为了文章改过一行。约束是 2 ≤ n ≤ 1000、1 ≤ k ≤ n−1，所以 O(k + log p) 随便跑。

#include <bits/stdc++.h>

class Solution {
    static constexpr long long MOD = 1'000'000'007;

    // 快速幂（费马小定理求逆元）
    static constexpr long long modpow(long long base, long long exp) {
        long long result = 1;
        for (base %= MOD; exp > 0; exp >>= 1) {
            if (exp & 1) result = result * base % MOD;
            base = base * base % MOD;
        }
        return result;
    }

public:
    int numberOfSets(int n, int k) {
        // 结论：方案数 = C(n + k - 1, 2k)
        const long long top = n + k - 1;
        const int bottom = 2 * k;
        if (bottom > top) return 0;

        // C++23：std::ranges::fold_left 对区间做左折叠
        const long long numerator = std::ranges::fold_left(
            std::views::iota(0, bottom), 1LL,
            [top](long long acc, int i) { return acc * ((top - i) % MOD) % MOD; });

        // 分母 = bottom!
        const long long denominator = std::ranges::fold_left(
            std::views::iota(1, bottom + 1), 1LL,
            [](long long acc, int i) { return acc * i % MOD; });

        return static_cast<int>(numerator * modpow(denominator, MOD - 2) % MOD);
    }
};

七、验证：我为什么敢说它是对的

这一节要拿到的东西：一个叫对数器的小习惯 —— 它比任何题解都值钱。

这道题我写了四份实现：暴力 DFS、前缀和 DP、组合公式，以及本机自测用的另一版公式。然后让它们互相对照：对 n ≤ 12 的所有 (n, k) 全跑一遍，四者必须完全一致；再拿官方 5 个示例和边界值兜底。

结果：暴力 × DP × 公式 × 提交版，四方完全一致，ASan/UBSan 也没有任何告警。而在这个过程中，我自己的自测脚本先被这层对照抓出了两个 bug —— 就是前面第三节说的剪枝，以及 DP 前缀和把 f[0][*] 也算进去了（正确的 S 应该从 m = 1 开始）。

八、复盘：今天能带走的东西

迁移卡（剥掉故事壳）：这道题剥掉”点与线段”的外衣，本质是「在一条带等号约束的序列上做计数」 —— 见到”计数 + 相邻可共用边界”的组合，先想双射，再想 DP。同类味道的题以后会收进这个栏目，届时在下面互相链接。

附录 · C++23 小抄（小白版，逐条讲透）

上面那些折叠块是「卡住了才点」；这一节反过来 —— 它不剧透任何东西，所以不折叠。每一条都按同一个套路讲：它是什么 → 为什么有用 → 一段能跑的代码 → 这道题里我用在哪。看完带走的是工具，不是答案。

1. std::ranges::fold_left：把一整个区间「折」成一个数

它是什么：C++23 的新算法。给它一个区间、一个初始值、一条「怎么合并」的规则，它就从左到右一路合并下去，最后返回一个值。

为什么有用：以前要么手写 for 循环（初始值写错、溢出都很难发现），要么用 std::accumulate（只能表达加法语义）。fold_left 能表达任意合并规则，还能配合惰性区间用。

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{1, 2, 3, 4};

    long long sum  = std::ranges::fold_left(v, 0LL, std::plus<>{});       // 1+2+3+4
    long long prod = std::ranges::fold_left(v, 1LL, std::multiplies<>{}); // 1*2*3*4

    std::cout << sum << ' ' << prod << '\n';   // 10 24
}

两个坑：① 累乘的初始值必须是 1LL，写 0 的话结果永远是 0；② 初始值的类型决定返回类型，想避免 int 溢出就写 0LL 而不是 0。

这道题用在哪：分子的连乘、分母的阶乘，各一行。

2. std::views::iota(a, b)：随用随生成的整数区间

它是什么：生成 a, a+1, …, b−1 这一串整数。注意是半开区间，不含 b —— 这是新手最常踩的坑。

为什么有用：它不占内存（用到才生成），却能像容器一样喂给 ranges 算法。写 std::views::iota(0, n) 就等于「从 0 数到 n−1」，不必先造一个 vector。

#include <iostream>
#include <ranges>

int main() {
    for (int i : std::views::iota(0, 5))
        std::cout << i << ' ';        // 0 1 2 3 4（不含 5）
    std::cout << '\n';

    for (int i : std::views::iota(1, 5))
        std::cout << i << ' ';        // 1 2 3 4 —— 阶乘就是它的累乘
}

名字的来历：iota 是希腊字母 ι，来自 APL 语言的整数生成符 ⍳。C++11 就有 std::iota（往容器里填），C++20 才加了惰性版本 std::views::iota。

这道题用在哪：fold_left 的输入就是 std::views::iota(1, bottom + 1) —— 那个 +1 就是为把半开区间补成 1…bottom。

3. 1’000’000’007：写给自己看的数字分隔符

它是什么：C++14 起，数字中间可以插单引号，编译器完全忽略它，纯粹方便人读。

为什么有用：模数 1000000007 有 9 个零，抄题时少写一个零是最冤的 WA。写成 1'000'000'007，一眼就能数清。

int main() {
    long long a = 1'000'000'007;   // 与 1000000007 完全等价
    long long b = 1'000'000'007;
    return a == b ? 0 : 1;         // 返回 0：两者确实相等
}

顺带一句：题面里的「10⁹ + 7」就是这个数，而它是质数 —— 这一点在第 5 条求逆元时会用上。

4. static constexpr 成员函数：能在编译期算的东西

它是什么：constexpr 表示「条件允许时这个函数可以在编译期求值」；static 表示它属于类本身，不用创建对象就能调用。

为什么有用：编译期算完，运行时就不用算；而且把常量与工具函数都收进类里，作用域干净、不容易撞名。

#include <iostream>

class Demo {
    static constexpr long long MOD = 1'000'000'007;      // 编译期常量

    static constexpr long long square(long long x) {      // 编译期可求值
        return x * x % MOD;
    }
public:
    static long long value() { return square(1'000'000'000); }
};

int main() {
    std::cout << Demo::value() << '\n';   // 编译期已算好，运行时零开销
}

陷阱：square 里 x 是 long long，所以 1e9 × 1e9 = 1e18 装得下；要是把参数写成 int，这一行就溢出了（int 上限约 2.1e9）。看到乘法，先问一句：会不会溢出。

5. 组合数取模三件套：分子连乘 → 分母阶乘 → 费马小定理求逆元

要算什么：C(n, r) = n! / (r!(n−r)!) 里有个除法。但在取模的世界里不能直接用 /（整数除法会把余数丢掉）。我们改用乘逆元。

逆元是什么：在模 p（p 为质数）的意义下，a 的逆元是满足 a × x ≡ 1 (mod p) 的那个 x。有了它，a / b 就可以写成 a × inv(b)。

怎么求：费马小定理说 a^(p−1) ≡ 1，两边除以 a 得 a^(p−2) ≡ a⁻¹。于是逆元 = 快速幂求 a^(p−2)。

#include <iostream>

constexpr long long MOD = 1'000'000'007;

// 快速幂：base^exp % MOD，O(log exp)
long long modpow(long long base, long long exp) {
    long long r = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp & 1) r = r * base % MOD;   // 这一位是 1，就乘进去
        base = base * base % MOD;           // 底数平方
        exp >>= 1;                         // 指数右移一位（相当于除以 2）
    }
    return r;
}

// C(n, r) % MOD
long long comb(long long n, long long r) {
    if (r < 0 || r > n) return 0;
    long long num = 1, den = 1;
    for (long long i = 0; i < r; ++i) {
        num = num * ((n - i) % MOD) % MOD;    // 分子：n × (n−1) × … × (n−r+1)
        den = den * (i + 1) % MOD;            // 分母：r!
    }
    return num * modpow(den, MOD - 2) % MOD;  // 乘以分母的逆元，等价于做除法
}

int main() {
    std::cout << comb(5, 4) << '\n';     // 5
    std::cout << comb(36, 14) << '\n';   // 3796297200 % MOD = 796297179（官方示例 3）
}

为什么每一步都要 % MOD：不取模的话，连乘十几项就爆 long long 了。固定写成 a * b % MOD，就不会忘。

这道题用在哪：就是最终提交版本里的那 8 行 —— 分母的逆元一乘，除法就变成了乘法。

6. Lambda 与捕获：把外部变量带进小函数

它是什么：[](参数){ 函数体 } 是匿名函数；方括号里的捕获列表决定它能看见外面哪些变量。

#include <algorithm>
#include <iostream>
#include <ranges>

int main() {
    long long top = 5;

    // [top]：把 top 按值拷进 lambda，函数体里就能用它
    auto mul = [top](long long acc, int i) {
        return acc * ((top - i) % 1000000007) % 1000000007;
    };

    // iota(0,4) 给出 0,1,2,3；累乘 = 5 × 4 × 3 × 2
    std::cout << std::ranges::fold_left(std::views::iota(0, 4), 1LL, mul) << '\n';   // 120
}

三个最常用的写法：[x] 按值拷贝、[&x] 按引用、[&] 全部按引用。陷阱：按值捕获是「快照」，函数体里改它不影响外面；想改外面要写 [&x] 并加 mutable。

7. auto、static_cast 与「溢出」这件小事

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{1, 2, 3};
    auto n = v.size();                  // auto：类型交给编译器推断（这里是 size_t）
    long long acc = 0;
    for (auto x : v) acc += x;          // 范围 for：不用写下标

    int a = 1'000'000'000;
    // int broken = a * a;              // ← 千万别这样写：溢出，结果不可预测
    long long safe = 1LL * a * a;       // 先转成 long long 再乘，安全

    std::cout << safe << ' ' << n << '\n';
    return static_cast<int>(acc % 1000000007);   // 显式转换：明确告诉读者在缩小类型
}

三条经验：① 能用 auto 就别手写类型名（但要知道推出来的是什么）；② 类型转换一律用 static_cast，不要用 C 风格的括号；③ 做乘法前先看会不会溢出 —— 这道题里每一次连乘后面紧跟 % MOD，就是为了这个。

最后，一张能直接抄进你笔记本的对照表：

明天见。如果你也在刷每日一题，欢迎在评论区贴出你的解法 —— 尤其是和上面两条都不一样的那种。