难度: Easy
给你一个 下标从 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 <= 501 <= nums[i] <= 100运行时间: 43 ms
内存: 16.0 MB
class Solution:
def countQuadruplets(self, nums: List[int]) -> int:
result = 0
max_num = 100
dp_result_1 = [0 for _ in range(max_num + 1)]
dp_result_2 = [0 for _ in range(max_num + 1)]
dp_result_3 = [0 for _ in range(max_num + 1)]
for num in nums:
for num_sum in range(num, max_num + 1):
dp_result_3[num_sum] = dp_result_3[num_sum] + dp_result_2[num_sum - num]
for num_sum in range(num, max_num + 1):
dp_result_2[num_sum] = dp_result_2[num_sum] + dp_result_1[num_sum - num]
dp_result_1[num] += 1
result += dp_result_3[num]
return result
此题解利用动态规划的概念来统计符合条件的四元组数量。我们定义三个动态数组 dp_result_1, dp_result_2, 和 dp_result_3，分别用来计算满足条件的一元组、二元组和三元组的数量。我们遍历数组 nums，对于每个元素 num，更新 dp_result_3 来累加前面可能存在的二元组数量，同理，更新 dp_result_2 来累加前面的一元组数量。dp_result_1 直接记录当前元素 num 的出现次数。通过这样的方式，我们可以在每一步有效地更新可能的二元组和三元组的数量，最后通过累加 dp_result_3 中与当前 num 值相等的位置的值来计算最终的四元组数量。
时间复杂度: O(n * max_num)
空间复杂度: O(max_num)
class Solution:
def countQuadruplets(self, nums: List[int]) -> int:
result = 0
max_num = 100
dp_result_1 = [0 for _ in range(max_num + 1)] # 初始化记录单个元素出现次数的数组
dp_result_2 = [0 for _ in range(max_num + 1)] # 初始化记录二元组和的数组
dp_result_3 = [0 for _ in range(max_num + 1)] # 初始化记录三元组和的数组
for num in nums:
for num_sum in range(num, max_num + 1):
dp_result_3[num_sum] = dp_result_3[num_sum] + dp_result_2[num_sum - num] # 更新三元组数量
for num_sum in range(num, max_num + 1):
dp_result_2[num_sum] = dp_result_2[num_sum] + dp_result_1[num_sum - num] # 更新二元组数量
dp_result_1[num] += 1 # 更新单个元素数量
result += dp_result_3[num] # 根据当前元素值，累加符合条件的四元组数量
return result
动态规划方法在这种问题中非常适用，因为它涉及到将一个复杂问题分解成多个子问题，并且通过逐步构建解决方案的方式解决这些子问题。问题的特性包括：有重叠的子问题（多个四元组可能共享相同的二元组或三元组组件），以及最优子结构（四元组的构建可以基于三元组，三元组可以基于二元组，依此类推）。这允许我们通过先计算小规模问题的解决方案，然后逐步构建更大规模问题的解决方案来有效地解决问题。
使用三个动态数组来分别存储一元组、二元组和三元组的数量可以让我们在不同的阶段分别跟踪和更新这些子问题的解决方案。这种分层的优势在于可以避免重复计算和存储不必要的状态，从而提高算法的效率和准确性。每个数组独立记录特定组合的数量，这样在更新更高维组合时可以直接引用下层已计算的结果，有效降低了问题的复杂度和执行时间。
题解中的 max_num + 1 是为了确保动态数组能够容纳从0到数组 nums 中的最大值的所有可能的和。这里的 max_num 通常是基于问题的约束或输入数据的预期范围来设定的。在这个特定的题解中，max_num 设置为100，这可能是基于对输入数组 nums 中元素值的一般假设或预定义的限制。如果 nums 中的实际最大值超过100，则需要相应地调整 max_num 的值以避免数组越界错误。
更新 dp_result_3 和 dp_result_2 的过程涉及到逐步累加可能的组合数量。从 num 到 max_num + 1 范围内遍历 num_sum 是为了确保我们能够正确地更新所有可能达到的和的数量。例如，当处理一个特定的 num 时，我们需要更新所有可能包含该 num 作为其中一个组成部分的组合的和。这样的遍历范围确保了每个可能的和都被正确更新，从而能够在后续的步骤中使用这些和来形成更大的组合，最终得到正确的四元组数量。