lc1995. 统计特殊四元组(哈希&二维背包）

给你一个 下标从 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

class Solution {
    /**
    nums[a] + nums[b] = nums[d] - nums[c]
    我们枚举b，然后b+1当坐c，只需再枚举d，然后将d-c存入哈希表
    再枚举a，将哈希表中a + 个数加入答案即可
    细节：d-c可能为负数 我们用数组时需要加上偏移量
     */
    public int countQuadruplets(int[] nums) {
        int n = nums.length;
        int res = 0;
        int[] cnt = new int[5110];
        for (int b = n - 3; b >= 1; --b) {
            for (int d = b + 2; d < n; ++d) cnt[nums[d] - nums[b+1] + 100]++;
            for (int a = 0; a < b; ++a) res += cnt[nums[a] + nums[b] + 100];
        }
        return res;
    }
}

二维背包

class Solution {
    /**
    状态表示：f[i,j,k] 表示只考虑前i个数，凑成数值为j，个数恰好是k的集合
    属性：count
    状态转移：选当前物品f[i-1,j,k],不选f[i-1,j-t,k-1]
    f[i,j,k] += f[i-1,j,k],当j > t时 + f[i-1,j-t,k-1]
    当然我们可以优化掉i这个维度
     */
    public int countQuadruplets(int[] nums) {
        int n = nums.length;
        int[][] f = new int[110][4];
        int res = 0;
        f[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            int t = nums[i-1];
            res += f[t][3];
            for (int j = 109; j >= t; --j) 
                for (int k = 3; k - 1 >= 0; --k) {
                    f[j][k] += f[j-t][k-1];
                }
        }
        return res;
    }
}