1995.统计特殊四元组

链接：1995.统计特殊四元组
难度：Easy
标签：数组、哈希表、枚举
简介：给你一个 下标从 0 开始 的整数数组 nums ，返回满足下述条件的 不同 四元组 (a, b, c, d) 的 数目。

题解 1 - cpp

• 编辑时间：2021-12-29
• 执行用时：60ms
• 内存消耗：10.6MB
• 编程语言：cpp
• 解法介绍：背包问题，前 i 个数能和为 j 的所使用的个数为 k。

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

题解 2 - cpp

• 编辑时间：2021-12-29
• 执行用时：56ms
• 内存消耗：13.9MB
• 编程语言：cpp
• 解法介绍：内嵌三循环。

class Solution {
   public:
    int countQuadruplets(vector<int>& nums) {
        unordered_map<int, int> m;
        int n = nums.size(), ans = 0;
        for (int i3 = n - 1; i3 >= 0; i3--) {
            m.clear();
            for (int i4 = i3 + 1; i4 < n; i4++) {
                int key = nums[i4] - nums[i3];
                if (m.count(key))
                    m[key]++;
                else
                    m[key] = 1;
            }
            for (int i1 = 0; i1 < i3; i1++) {
                for (int i2 = i1 + 1; i2 < i3; i2++) {
                    int key = nums[i1] + nums[i2];
                    if (m.count(key)) {
                        ans += m[key];
                    }
                }
            }
        }
        return ans;
    }
};

题解 3 - cpp

• 编辑时间：2021-12-29
• 执行用时：136ms
• 内存消耗：10.2MB
• 编程语言：cpp
• 解法介绍：内嵌四循环。

class Solution {
   public:
    int countQuadruplets(vector<int>& nums) {
        int n = nums.size(), ans = 0;
        for (int i1 = 0; i1 < n; i1++) {
            for (int i2 = i1 + 1; i2 < n; i2++) {
                for (int i3 = i2 + 1; i3 < n; i3++) {
                    for (int i4 = i3 + 1; i4 < n; i4++) {
                        if (nums[i1] + nums[i2] + nums[i3] == nums[i4]) ans++;
                    }
                }
            }
        }
        return ans;
    }
};