每日一题——1995. 统计特殊四元组

1995. 统计特殊四元组

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

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

---

这题之所以是简单题我想应该是暴力算法太过于直接

以至于完全不用动脑直接四个for循环就完事了

不过看了题解我才吓一跳

居然有四种不同的解法

这里就写了一种我能看懂的

public class Solution {
    public int CountQuadruplets(int[] nums) {
        int n = nums.Length;
        int ans = 0;
        Dictionary<int, int> cnt = new Dictionary<int, int>();
        for (int c = n - 2; c >= 2; --c) {
            //逆序遍历 枚举第三个下标c 
            if (!cnt.ContainsKey(nums[c + 1])) 
            {
                cnt.Add(nums[c + 1], 1);
            } //不包含这个d就添加
            else 
            {
                ++cnt[nums[c + 1]];
            }//已经包含这个d就++
            for (int a = 0; a < c; ++a)
            {
                for (int b = a + 1; b < c; ++b)
                {
                    int sum = nums[a] + nums[b] + nums[c];
                    if (cnt.ContainsKey(sum)) 
                    {
                        ans += cnt[sum];
                    }//如果符合a+b+c=d 这个d就是符合要求的 出现的次数就可以加到答案中
                }
            }
        }
        return ans;
    }
}

直接逆序遍历c来统计d的个数

然后判断这个d是否符合a+b+c=d

符合的话 对应的d出现的次数就直接加到答案中

最后返回答案

顺便一提C#这样写比暴力法还慢了4ms

不知道是不是被针对了