leetcode-1995. 统计特殊四元组

简介: leetcode-1995. 统计特殊四元组

题目

题目连接

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

  • nums[a] + nums[b] + nums[c] == nums[d] ,且
  • a < b < c < d

示例 1:

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

示例 2:

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

解题

方法一:暴力

class Solution {
public:
    int countQuadruplets(vector<int>& nums) {
        int n=nums.size();
        int res=0;
        for(int a=0;a<n-3;a++){
            for(int b=a+1;b<n-2;b++){
                for(int c=b+1;c<n-1;c++){
                    for(int d=c+1;d<n;d++){
                        if(nums[a]+nums[b]==nums[d]-nums[c]){
                            res++;
                        }
                    }
                }
            }
        }
        return res;
    }
};

方法二:哈希表

通过i将数组划分为两半,对分割线b进行遍历

遍历的时候c=i+1,但是由于map[nums[a]+nums[b]]++是累计的,因此并不总是b、c粘和的情况。

class Solution {
public:
    int countQuadruplets(vector<int>& nums) {
        int n=nums.size();
        int res=0;
        unordered_map<int,int> map;
        for(int i=1;i<n-2;i++){
            for(int j=0;j<i;j++){
                map[nums[i]+nums[j]]++;
            }
            for(int j=i+2;j<n;j++){
                if(map.count(nums[j]-nums[i+1])){
                    res+=map[nums[j]-nums[i+1]];
                }
            }
        }
        return res;
    }
};

可以通过这个连接进行理解,虽然它是从后向前遍历的

参考连接


相关文章
|
6月前
|
算法 测试技术 C#
区间合并|LeetCode2963:统计好分割方案的数目
区间合并|LeetCode2963:统计好分割方案的数目
|
6月前
|
算法 安全 测试技术
[组合数学]LeetCode:2954:统计感冒序列的数目
[组合数学]LeetCode:2954:统计感冒序列的数目
|
6月前
|
算法 测试技术 C#
【离散差分】LeetCode2953:统计完全子字符串
【离散差分】LeetCode2953:统计完全子字符串
|
6月前
leetcode-1220:统计元音字母序列的数目
leetcode-1220:统计元音字母序列的数目
48 0
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
存储 算法 Java
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
42 0
|
4月前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
6月前
[leetcode~数位动态规划] 2719. 统计整数数目 hard
[leetcode~数位动态规划] 2719. 统计整数数目 hard
|
6月前
leetcode2376. 统计特殊整数
leetcode2376. 统计特殊整数
52 1
|
6月前
leetcode 2520 统计能整除数字的位数
leetcode 2520 统计能整除数字的位数
24 0