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 <= 50
  • 1 <= nums[i] <= 100

解题思路

这道题要求找到满足 nums[a] + nums[b] + nums[c] == nums[d] 且 a < b < c < d 的四元组数量。

思路分析：

  1. 暴力枚举法：由于数组长度最大只有50，可以直接用四层循环枚举所有可能的四元组。时间复杂度为O(n⁴)，但在这个数据规模下完全可以接受。

  2. 哈希表优化：我们可以用哈希表来优化。先枚举前两个数的和，存储在哈希表中，然后枚举后两个数，检查是否存在匹配的前两个数的和。这样可以将复杂度降低到O(n³)。

  3. 进一步优化：固定c和d的位置，然后寻找满足条件的a和b。对于每个c，我们可以维护一个哈希表存储所有在c之前的两数之和的出现次数。

推荐解法：考虑到数据规模较小，暴力枚举法最为直观且效率足够。但为了展示优化思路，我们采用哈希表优化的方法。

核心思路是：

  • 枚举所有可能的c和d位置（c < d）
  • 对于每个(c,d)对，统计在位置c之前有多少个(a,b)对满足 nums[a] + nums[b] + nums[c] == nums[d]
  • 使用哈希表记录每个两数之和出现的次数

代码实现

class Solution {
public:
    int countQuadruplets(vector<int>& nums) {
        int n = nums.size();
        int count = 0;
        
        for (int c = 2; c < n - 1; c++) {
            unordered_map<int, int> sumCount;
            
            // 统计c之前所有两数之和的出现次数
            for (int a = 0; a < c - 1; a++) {
                for (int b = a + 1; b < c; b++) {
                    sumCount[nums[a] + nums[b]]++;
                }
            }
            
            // 枚举d，查找满足条件的(a,b)对
            for (int d = c + 1; d < n; d++) {
                int target = nums[d] - nums[c];
                if (sumCount.count(target)) {
                    count += sumCount[target];
                }
            }
        }
        
        return count;
    }
};

class Solution:
    def countQuadruplets(self, nums: List[int]) -> int:
        n = len(nums)
        count = 0
        
        for c in range(2, n - 1):
            sum_count = {}
            
            # 统计c之前所有两数之和的出现次数
            for a in range(c - 1):
                for b in range(a + 1, c):
                    two_sum = nums[a] + nums[b]
                    sum_count[two_sum] = sum_count.get(two_sum, 0) + 1
            
            # 枚举d，查找满足条件的(a,b)对
            for d in range(c + 1, n):
                target = nums[d] - nums[c]
                if target in sum_count:
                    count += sum_count[target]
        
        return count

public class Solution {
    public int CountQuadruplets(int[] nums) {
        int n = nums.Length;
        int count = 0;
        
        for (int c = 2; c < n - 1; c++) {
            Dictionary<int, int> sumCount = new Dictionary<int, int>();
            
            // 统计c之前所有两数之和的出现次数
            for (int a = 0; a < c - 1; a++) {
                for (int b = a + 1; b < c; b++) {
                    int twoSum = nums[a] + nums[b];
                    if (sumCount.ContainsKey(twoSum)) {
                        sumCount[twoSum]++;
                    } else {
                        sumCount[twoSum] = 1;
                    }
                }
            }
            
            // 枚举d，查找满足条件的(a,b)对
            for (int d = c + 1; d < n; d++) {
                int target = nums[d] - nums[c];
                if (sumCount.ContainsKey(target)) {
                    count += sumCount[target];
                }
            }
        }
        
        return count;
    }
}

var countQuadruplets = function(nums) {
    const n = nums.length;
    let count = 0;
    
    for (let c = 2; c < n - 1; c++) {
        const sumCount = new Map();
        
        // 统计c之前所有两数之和的出现次数
        for (let a = 0; a < c - 1; a++) {
            for (let b = a + 1; b < c; b++) {
                const twoSum = nums[a] + nums[b];
                sumCount.set(twoSum, (sumCount.get(twoSum) || 0) + 1);
            }
        }
        
        // 枚举d，查找满足条件的(a,b)对
        for (let d = c + 1; d < n; d++) {
            const target = nums[d] - nums[c];
            if (sumCount.has(target)) {
                count += sumCount.get(target);
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n³)
空间复杂度O(n²)
  • 时间复杂度：外层循环O(n)，内层计算两数之和需要O(n²)，枚举d需要O(n)，总体为O(n³)
  • 空间复杂度：哈希表最多存储O(n²)个两数之和

相关题目