1995. Count Special Quadruplets 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int countQuadruplets(int[] nums) {
        int n = nums.length;
        int count = 0;

        Map<Integer, Integer> cdDiffToCountMap = new HashMap<>();
        for (int b = n - 3; b >= 1; b--) {
            for (int d = b + 2; d < n; d++) { // 该循环将 num[b + 1] 即 c 之后的 c 与 d 的差都进行了计算并缓存
                int cdDiff = nums[d] - nums[b + 1];
                cdDiffToCountMap.put(cdDiff, cdDiffToCountMap.getOrDefault(cdDiff, 0) + 1);
            }

            for (int a = 0; a < b; a++) {
                int target = nums[a] + nums[b];
                count += cdDiffToCountMap.getOrDefault(target, 0);
            }
        }

        return count;
    }
}

注意题目要求了四元组中元素保持原顺序，所以不能排序。

References

1995. Count Special Quadruplets