统计特殊四元组

力扣 1995. 统计特殊四元组

题目说明

给你一个下标从 0 开始的整数数组 nums ，返回满足下述条件的不同四元组 (a, b, c, d) 的数目：

nums[a] + nums[b] + nums[c] == nums[d] ，且
a < b < c < d

提示：

4 <= nums.length <= 50
1 <= nums[i] <= 100

示例

示例 1:

1
2
3

输入：nums = [1,2,3,6]
输出：1
解释：满足要求的唯一一个四元组是 (0, 1, 2, 3) 因为 1 + 2 + 3 == 6 。

示例 2:

1
2
3

输入：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

笔者理解

此题是一道数组算法问题，在力扣题库中被定义为简单题。

解法

当笔者阅读完此题后，发现此题简单在数据范围，可以直接用多重for循环暴力求解，我们在这里采用哈希表+双重for循环的形式，让我们来看看具体如何实现的吧。

实现

class Solution {
    /**
     * 哈希表
     */
    // 本题中看似是四个数的查找，其实我们将等式移动一下不难发现
    // a + b = d - c
    // 这样我们就可以利用哈希表从后向前记录 d - c 的可能
    // 同时利用 b 当中轴，如何向前遍历 a
    // 这样原来的四重 for 循环就变成双重循环了
    public int countQuadruplets(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int n = nums.length;
        int result = 0;

        // 此处将 b 作为中轴向前寻找 a，向后寻找 d - c
        for (int b = n - 3; b >= 1; b--) {
            int temp;
            for (int d = b + 2; d < n; d++) {
                temp = nums[d] - nums[b + 1];
                map.put(temp, map.getOrDefault(temp, 0) + 1);
            }
            for (int a = 0; a < b; a++) {
                temp = nums[a] + nums[b];
                result += map.getOrDefault(temp, 0);
            }
        }

        return result;
    }
}