菜鸟的每日力扣系列——1995. 统计特殊四元组

这个题首先可以使用两数之和的思想，以[1, 1, 1, 3, 5]为例，由于要统计四元组，我们可以把它划分成两部分，枚举左边两数之和，枚举右边两数之差，如果相等，统计结果加一。

和昨天的题目有些类似，我们用一个哈希表存储两边枚举后的和（差）的结果，可以用Counter()，在python中也可以使用collections库下的defaultdict，它与普通字典的区别在于如果查不到对应的key，不会返回KeyError，而是返回一个默认的空值，例如list是[]，str对应""，set对应set()，int对应0。

from typing import List
from collections import defaultdict

def count_special_quadruplets(nums: List[int]) -> int:
    cache = defaultdict(int)
    res = 0
    for i in range(1, len(nums)-2):  # 除去最后一个元素
        for j in range(i):  
            cache[nums[i]+nums[j]] += 1  # 左半边计算和
        for j in range(i+2, len(nums)):
            res += cache[nums[j] - nums[i+1]]
    return res

nums = [1,1,1,3,5]
print(count_special_quadruplets(nums))  # 4

第一层for i in range(1, len(nums)-2):统计了到目前为止统计了所有0到i的两坐标和；

在cache[nums[i]+nums[j]] += 1之后，我们得到第三个元素下标是i+1，然后枚举第四个元素下标j范围是第三个元素之后 i+2到数组末尾。

res += cache[nums[j] - nums[i+1]]在左边之和的结果上叠加右边之差的结果，最终返回。

END