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
不知道是不是被针对了