企业官网建设流程全解析

• 教程
• 文档

本文基于「宫水三叶的刷题日记」刷穿 LeetCode 系列题解仓库 LogicStack-LeetCode 中的 1995. 统计特殊四元组（简单） 一文展开，围绕等式nums[a] + nums[b] + nums[c] = nums[d]的统计问题，完整覆盖「四重循环模拟 → 逆序枚举 + 哈希表 → 移项哈希表 → 多维背包 → 背包维度优化」五套解法，并给出每套解法的 Java / C++ 实现、边界细节与复杂度对比。读完本文，你将掌握一类「等式约束下的下标有序四元组计数」问题的通用分析套路：先按数据范围决定能否暴力，再通过固定某一下标 + 逆序枚举让哈希表增量维护可行集合，最后将「数值 + 个数」双约束抽象为二维费用背包求方案数。

题目回顾：统计满足a < b < c < d且三数之和等于第四数的四元组

题目给一个下标从0开始计数的整数数组nums，要求返回满足下述条件的不同四元组(a, b, c, d)的数目：

nums[a] + nums[b] + nums[c] = nums[d]

且四个下标严格递增：a < b < c < d。

示例 1：

输入：nums = [1,2,3,6] 输出：1 解释：满足要求的唯一一个四元组是 (0, 1, 2, 3) 因为 1 + 2 + 3 == 6 。

示例 2：

输入：nums = [3,3,6,4,5] 输出：0 解释：[3,3,6,4,5] 中不存在满足要求的四元组。

示例 3：

输入：nums = [1,1,1,3,5] 输出：4 解释：满足要求的 4 个四元组如下： - (0, 1, 2, 3): 1 + 1 + 1 == 3 - (0, 1, 3, 4): 1 + 1 + 3 == 5 - (0, 2, 3, 4): 1 + 1 + 3 == 5 - (1, 2, 3, 4): 1 + 1 + 3 == 5

数据提示（决定算法选型的关键）：

4 <= nums.length <= 50 1 <= nums[i] <= 100

• n最大只有50，这意味着暴力枚举全部四元组是可行的（组合数C(50,4) ≈ 23 万级别）；
• 数值范围[1, 100]，三个数之和最大不超过300，说明「计数数组」的规模完全可控，可以用定长数组代替哈希表，常数极小。

该题在仓库中同时被收录进 Index/模拟.md、Index/哈希表.md 与 Index/背包 DP.md 三个专题索引，正好对应本文即将展开的三条主线：模拟、哈希表、背包 DP。这也体现了仓库「一题多解、按 Tag 归类」的组织方式。

解法一：四重循环模拟（O(n⁴)）

思路

利用数据范围只有n <= 50的约束，直接按题意模拟：用四层循环分别枚举下标a、b、c、d，保证a < b < c < d，一旦满足nums[a] + nums[b] + nums[c] == nums[d]即累加答案。这是最直观、最不可能出错的做法，也是理解后续所有优化的「基准解」。

实现

Java 代码：

class Solution { public int countQuadruplets(int[] nums) { int n = nums.length, ans = 0; for (int a = 0; a < n; a++) { for (int b = a + 1; b < n; b++) { for (int c = b + 1; c < n; c++) { for (int d = c + 1; d < n; d++) { if (nums[a] + nums[b] + nums[c] == nums[d]) ans++; } } } } return ans; } }

C++ 代码：

class Solution { public: int countQuadruplets(vector<int>& nums) { int n = nums.size(), ans = 0; for (int a = 0; a < n; a++) { for (int b = a + 1; b < n; b++) { for (int c = b + 1; c < n; c++) { for (int d = c + 1; d < n; d++) { if (nums[a] + nums[b] + nums[c] == nums[d]) ans++; } } } } return ans; } };

复杂度与点评

• 时间复杂度：O(n⁴)，四层循环每层最坏遍历n个位置；
• 空间复杂度：O(1)，仅使用常数个变量。

这套代码正确性毋庸置疑，但n = 50时最坏仍需执行约C(50,4) ≈ 23 万次判断，对本题完全够用。然而它暴露了一个明显浪费：对于固定的(a, b, c)，我们真正关心的是「数组里有多少个下标d > c满足nums[d] = nums[a] + nums[b] + nums[c]」，而四重循环却把每一个候选d都单独比较一次。这正是下一节哈希表优化的切入点。

解法二：逆序枚举 c + 计数数组（O(n³)）

思路

保持对a、b的两层枚举不变，将「寻找d」这一步从循环改为查表。

关键技巧是逆序枚举c：当c从大到小移动时，d的可取下标范围（即[c+1, n)）会不断「扩大一个位置」。具体来说：

• 从c = n - 2开始，逆序往左遍历；
• 每轮循环开始时，c + 1这个位置恰好是新进入d可取范围的唯一新下标，于是执行cnt[nums[c + 1]]++完成增量统计；
• 此时cnt中记录的就是「所有下标大于当前c的nums[d]的出现次数」，直接查cnt[nums[a] + nums[b] + nums[c]]即可得到能与当前(a, b, c)配对的d的数量。

由于nums[i] <= 100、三数和最大300，计数数组开10010大小绰绰有余（这是原题解中int[] cnt = new int[10010]的由来），用数组替代哈希表既避免了哈希开销，也让空间复杂度变成可控的O(C)。

实现

Java 代码：

class Solution { public int countQuadruplets(int[] nums) { int n = nums.length, ans = 0; int[] cnt = new int[10010]; for (int c = n - 2; c >= 2; c--) { cnt[nums[c + 1]]++; for (int a = 0; a < n; a++) { for (int b = a + 1; b < c; b++) { ans += cnt[nums[a] + nums[b] + nums[c]]; } } } return ans; } }

C++ 代码：

class Solution { public: int countQuadruplets(vector<int>& nums) { int n = nums.size(), ans = 0; vector<int> cnt(10010, 0); for (int c = n - 2; c >= 2; c--) { cnt[nums[c + 1]]++; for (int a = 0; a < n; a++) { for (int b = a + 1; b < c; b++) { ans += cnt[nums[a] + nums[b] + nums[c]]; } } } return ans; } };

边界说明

• 内层b的循环上限是b < c，从而天然保证a < b < c；
• c的循环下限取2，因为c前面至少要留出a、b两个位置；
• 外层a虽然也从0开始，但受b < c约束，实际有效组合依然满足a < b < c < d，不会产生重复计数。

复杂度与点评

• 时间复杂度：O(n³)，枚举(c, a, b)三层；
• 空间复杂度：O(C)，C为计数数组的规模（10010）。

相比解法一，本解法把「对每个d的比较」压缩为「一次数组查询」，复杂度从O(n⁴)降到了O(n³)。但这里仍然枚举了a、b两个变量，还有没有继续压缩的空间？答案是肯定的——把等号两边都改写成「二元表达式」，就能再砍掉一层循环。

解法三：移项 + 逆序枚举 b 的哈希表（O(n²)）

思路

对等式移项，得到：

nums[a] + nums[b] = nums[d] - nums[c]

此时等式两边各含两个下标：左边是(a, b)，右边是(c, d)，且满足a < b < c < d。

于是可以逆序枚举b，让c的可取范围（即[b+1, n)）随b左移而扩大：

• 从b = n - 3开始逆序遍历（b后面至少要留出c、d两个位置）；
• 每轮先把b + 1作为新的c，枚举所有d ∈ [b+2, n)，将nums[d] - nums[c]的取值计数cnt[nums[d] - nums[b + 1] + 200]++写入计数数组；
• 再枚举所有a ∈ [0, b)，直接查表累加ans += cnt[nums[a] + nums[b] + 200]。

值偏移细节：由于nums[d] - nums[c]可能为负（例如nums = [1, 100]时差值为-99），直接作为数组下标会越界。利用1 <= nums[i] <= 100的范围限制，将差值整体加上偏移量200映射到非负下标；nums[a] + nums[b]最大为200，同样加200偏移后下标范围为[201, 400]，与差值一侧的映射区间互不冲突，可安全复用同一个cnt数组（容量10010足够容纳全部映射结果）。

实现

Java 代码：

class Solution { public int countQuadruplets(int[] nums) { int n = nums.length, ans = 0; int[] cnt = new int[10010]; for (int b = n - 3; b >= 1; b--) { for (int d = b + 2; d < n; d++) cnt[nums[d] - nums[b + 1] + 200]++; for (int a = 0; a < b; a++) ans += cnt[nums[a] + nums[b] + 200]; } return ans; } }

C++ 代码：

class Solution { public: int countQuadruplets(vector<int>& nums) { int n = nums.size(), ans = 0; vector<int> cnt(10010, 0); for (int b = n - 3; b >= 1; b--) { for (int d = b + 2; d < n; d++) cnt[nums[d] - nums[b + 1] + 200]++; for (int a = 0; a < b; a++) ans += cnt[nums[a] + nums[b] + 200]; } return ans; } };

正确性要点

• 逆序枚举b的每一轮中，cnt恰好维护了「所有满足c > b且d > c的nums[d] - nums[c]计数」；
• 当b左移到新位置时，b + 1是唯一新增的合法c，此时为它枚举全部d ∈ [b+2, n)并增量统计，即可保证后续a的查询始终覆盖完整的(c, d)组合；
• a枚举范围[0, b)保证a < b，最终a < b < c < d的次序约束被完整满足，且每个四元组只在b取到其对应值时被统计一次，不会重复。

复杂度与点评

• 时间复杂度：O(n²)，外层b、内层d与a各一层；
• 空间复杂度：O(C)，C为计数数组规模。

到这里，枚举维度已从四层压缩到两层，达到「枚举一半 + 哈希表维护另一半」的经典形态。这与仓库 Index/哈希表.md 中收录的诸多题目（如 1. 两数之和、15. 三数之和）的思路一脉相承：用哈希表把「暴力查找」转化为「O(1) 查询」。

解法四：多维背包（二维费用背包求方案数，O(n × 110 × 4)）

为什么可以用背包

观察等式nums[a] + nums[b] + nums[c] = nums[d]，它同时约束了「数值」与「个数」两个维度：

• 数值维度：左边三个数的和恰好等于某个nums[d]；
• 个数维度：参与求和的元素个数恰好为3。

「恰好」性质的组合优化问题，正是背包 DP 的经典适用场景。本解法把问题抽象为：从前i个元素中选出恰好k个、使其数值和恰好为j，有多少种方案——也就是一个标准的二维费用背包求方案数问题。仓库 Index/背包 DP.md 中收录的 494. 目标和（中等）、474. 一和零（中等） 均是同一类「恰好型二维背包」的姊妹题，可对照学习。

状态定义与转移

定义f[i][j][k]为考虑前i个物品（下标从1开始计，对应nums[0..i-1]），凑成数值恰好为j、使用个数恰好为k的方案数。

• 起始状态：f[0][0][0] = 1，代表不考虑任何物品时，用0个元素凑出数值0的方案数为1；
• 转移时，根据nums[i-1]（记为t）是否参与组合分情况讨论：
  • 不参与：方案数为f[i-1][j][k]；
  • 参与：方案数为f[i-1][j-t][k-1]，前提是j - t >= 0且k - 1 >= 0；
  • 两者相加即得f[i][j][k]。

最终答案：对每个下标d（在物品视角下为第i个元素，i从3开始，保证前面至少有 3 个元素可作a、b、c），累加f[i][nums[i]][3]，即「从前i个元素中恰好选出 3 个、数值和恰好等于nums[i]」的方案数：

ans = sum_{i = 3}^{n-1} f[i][nums[i]][3]

数值上界取110的原因：nums[i] <= 100，为容纳「恰好等于某个nums[d]」的查询，j的枚举上界覆盖到100即可，原题解取110留出余量；个数维度只有0、1、2、3四种取值，故第三维大小为4。

实现

Java 代码：

class Solution { public int countQuadruplets(int[] nums) { int n = nums.length, ans = 0; int[][][] f = new int[n + 1][110][4]; f[0][0][0] = 1; for (int i = 1; i <= n; i++) { int t = nums[i - 1]; for (int j = 0; j < 110; j++) { for (int k = 0; k < 4; k++) { f[i][j][k] += f[i - 1][j][k]; if (j - t >= 0 && k - 1 >= 0) f[i][j][k] += f[i - 1][j - t][k - 1]; } } } for (int i = 3; i < n; i++) ans += f[i][nums[i]][3]; return ans; } }

C++ 代码：

class Solution { public: int countQuadruplets(vector<int>& nums) { int n = nums.size(), ans = 0; vector<vector<vector<int>>> f(n + 1, vector<vector<int>>(110, vector<int>(4, 0))); f[0][0][0] = 1; for (int i = 1; i <= n; i++) { int t = nums[i - 1]; for (int j = 0; j < 110; j++) { for (int k = 0; k < 4; k++) { f[i][j][k] += f[i - 1][j][k]; if (j >= t && k >= 1) f[i][j][k] += f[i - 1][j - t][k - 1]; } } } for (int i = 3; i < n; i++) ans += f[i][nums[i]][3]; return ans; } };

复杂度与点评

• 时间复杂度：O(n × 110 × 4)，即O(n)轮 × 两个容量维度；
• 空间复杂度：O(n × 110 × 4)，完整保留了每一层的三维 DP 表。

注意这里的时间复杂度写法是「物品数 × 容量 × 个数」，虽然从大 O 记号看仍含常数因子110 × 4，但实际运算量远小于O(n²)哈希表解法的常数，且思路与「模拟 / 哈希表」完全不同——它把问题彻底转换成了「组合方案数」的视角。这一视角本身就有价值：它把计数问题的解法空间打开，让我们意识到「恰好 k 个元素凑成数值 j」是一类可复用的子问题。

解法五：背包维度优化（滚动数组，边转移边统计）

优化原理

观察三维 DP 的转移方程：

f[i][j][k] = f[i-1][j][k] + f[i-1][j-t][k-1]

当前层i只依赖上一层i-1，且依赖的是「数值更小、个数更少」的状态f[i-1][j-t][k-1]。这意味着：

1. 可以滚掉物品维度，只用二维数组f[j][k]原地滚动更新；
2. 为保证「用到的f[j-t][k-1]是上一层的旧值」，j和k必须逆序枚举（从大到小），否则同一层内新写入的值会被重复使用，导致一个元素被多次选取，破坏「每个下标最多参与一次」的约束——这是 0/1 背包类问题滚动的标准写法；
3. 答案统计时机前置：在处理第i个物品（值为t）时，f[t][3]恰好表示「从前i-1个元素中选出 3 个、和为t」的方案数，这正是以nums[i]为d时所需的计数，因此可以在更新f之前先执行ans += f[t][3]，从而省去最后单独遍历累加答案的步骤。

实现

Java 代码：

class Solution { public int countQuadruplets(int[] nums) { int n = nums.length, ans = 0; int[][] f = new int[110][4]; f[0][0] = 1; for (int i = 1; i <= n; i++) { int t = nums[i - 1]; ans += f[t][3]; for (int j = 109; j >= 0; j--) { for (int k = 3; k >= 0; k--) { if (j - t >= 0 && k - 1 >= 0) f[j][k] += f[j - t][k - 1]; } } } return ans; } }

C++ 代码：

class Solution { public: int countQuadruplets(vector<int>& nums) { int n = nums.size(), ans = 0; vector<vector<int>> f(110, vector<int>(4, 0)); f[0][0] = 1; for (int i = 1; i <= n; i++) { int t = nums[i - 1]; ans += f[t][3]; for (int j = 109; j >= 0; j--) { for (int k = 3; k >= 0; k--) { if (j - t >= 0 && k - 1 >= 0) f[j][k] += f[j - t][k - 1]; } } } return ans; } };

复杂度与点评

• 时间复杂度：O(n × 110 × 4)，与三维版本同阶；
• 空间复杂度：O(110 × 4)，物品维度被彻底滚掉。

这里原题解注释的空间复杂度写作O(n × 110 × 4)，若按滚动数组实际使用量严格衡量应为O(110 × 4)的常数级二维表——两种表述分别对应「完整保留每层结果」与「仅保留当前层」两种视角，不影响正确性。无论哪种解读，本解法都是五套方案中实现最紧凑的一版：一次遍历同时完成 DP 更新与答案统计，代码量比解法四少了近一半。

五套解法复杂度总览与选型建议

选型建议：面试或刷题时，先看数据范围——n很小就直接模拟（解法一）；n稍大但可接受O(n³)用解法二；追求最优复杂度用解法三的O(n²)哈希表；而解法四、五的价值更多在于展示「组合计数问题与多维背包」的联系，是理解 Index/背包 DP.md 专题、向 494. 目标和、474. 一和零、1155. 掷骰子的N种方法 等题目迁移的桥梁。

仓库视角：这道题在 LogicStack-LeetCode 中的位置

本仓库是「宫水三叶的刷题日记」刷穿 LeetCode 系列文章的源码库，按题目编号分目录存放每题题解。本题的完整题解位于 LeetCode/1991-2000/1995. 统计特殊四元组（简单）.md，同时被归入三个 Tag 索引：

• Index/模拟.md：收录「按题意直接模拟」的一类题目，对应解法一；
• Index/哈希表.md：收录「用哈希表/计数数组把查找变查询」的一类题目，对应解法二、三；该表中还包含 1. 两数之和、15. 三数之和、18. 四数之和 等「n 数之和」系列的姊妹题（另见 Index/n 数之和.md）；
• Index/背包 DP.md：收录「恰好型/费用型背包」题目，对应解法四、五。

当你需要查阅更多同 Tag 题目或验证其他题解时，可直接浏览上述索引文件，索引中每行都带有原题链接与题解链接，便于按专题系统复习。整篇题解的核心结论可以浓缩为一句话：面对「等式 + 下标有序」的计数题，先暴力兜底，再用「固定一端、逆序枚举、哈希表增量维护另一端」压缩复杂度，最后若能抽象出「数值 + 个数」双约束，则多维背包是另一条完备的解法路径。

• 教程
• 文档