题目描述
这是 LeetCode 上的 1995. 统计特殊四元组 ，难度为 简单。
Tag : 「枚举」、「哈希表」、「背包 DP」
给你一个 下标从 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 <= 504<=nums.length<=50
- 1 <= nums[i] <= 1001<=nums[i]<=100
朴素解法
利用数据范围只有 5050，可直接根据题意进行模拟。
代码：
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; } } 复制代码
- 时间复杂度：O(n^4)O(n4)
- 空间复杂度：O(1)O(1)
哈希表
利用等式关系 nums[a] + nums[b] + nums[c] = nums[d]nums[a]+nums[b]+nums[c]=nums[d]，可以调整枚举 cc 的顺序为「逆序」，每次 cc 往左移动一个单位，dd 的可取下标范围增加一个（即 c + 1c+1 位置)，使用数组代替哈希表对 nums[d]nums[d] 的个数进行统计，可使复杂度下降到 O(n^3)O(n3)。
代码：
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; } } 复制代码
- 时间复杂度：O(n^3)O(n3)
- 空间复杂度：O(C)O(C)
哈希表
更进一步，根据等式关系进行移项可得：nums[a] + nums[b] = nums[d] - nums[c]nums[a]+nums[b]=nums[d]−nums[c]，其中各下标满足 a < b < c < da<b<c<d。
我们可在「逆序」枚举 bb 时，将新产生的 cc（即 b + 1b+1 位置）所能产生的新 nums[d] - nums[c]nums[d]−nums[c] 的值存入哈希表（即 从 [b + 2, n)[b+2,n) 范围内枚举 dd），最后通过枚举 aa 来统计答案。
一些细节：由于 nums[d] - nums[c]nums[d]−nums[c] 可能为负，在使用数组代替哈希表时，可利用 1 <= nums[i] <= 1001<=nums[i]<=100 做一个值偏移。
代码：
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; } } 复制代码
- 时间复杂度：O(n^2)O(n2)
- 空间复杂度：O(C)O(C)
多维背包
利用等式关系 nums[a] + nums[b] + nums[c] = nums[d]nums[a]+nums[b]+nums[c]=nums[d]，具有明确的「数值」和「个数」关系，可将问题抽象为组合优化问题求方案数。
限制组合个数的维度有两个，均为「恰好」限制，转换为「二维费用背包问题求方案数」问题。
定义 f[i][j][k]f[i][j][k] 为考虑前 ii 个物品（下标从 11 开始），凑成数值恰好 jj，使用个数恰好为 kk 的方案数。
最终答案为 \sum_{i = 3}^{n - 1}(f[i][nums[i]][3])∑i=3n−1(f[i][nums[i]][3])，起始状态 f[0][0][0] = 1f[0][0][0]=1 代表不考虑任何物品时，所用个数为 00，凑成数值为 00 的方案数为 11。
不失一般性考虑 f[i][j][k]f[i][j][k] 该如何转移，根据 nums[i - 1]nums[i−1] 是否参与组合进行分情况讨论：
- nums[i - 1]nums[i−1] 不参与组成，此时有：f[i - 1][j][k]f[i−1][j][k];
- nums[i - 1]nums[i−1] 参与组成，此时有：f[i - 1][j - t][k - 1]f[i−1][j−t][k−1];
最终 f[i][j][k]f[i][j][k] 为上述两种情况之和，最终统计 \sum_{i = 3}^{n - 1}(f[i][nums[i]][3])∑i=3n−1(f[i][nums[i]][3]) 即是答案。
利用 f[i][j][k]f[i][j][k] 仅依赖于 f[i - 1][j][k]f[i−1][j][k] 和
jk维度值更小的 f[i - 1][X][X]f[i−1][X][X]，可进行维度优化，并在转移过程中统计答案。
代码（维度优化见 P2P2）：
class Solution { public int countQuadruplets(int[] nums) { int n = nums.length; 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]; } } } int ans = 0; for (int i = 3; i < n; i++) ans += f[i][nums[i]][3]; return ans; } } 复制代码
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; } } 复制代码
- 时间复杂度：O(n * 110 * 4)O(n∗110∗4)
- 空间复杂度：O(n * 110 * 4)O(n∗110∗4)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1995 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
