Cinte's Leetcode Record
0%

1995. 统计特殊四元组

Posted on Edited on In Disqus:
Symbols count in article: 1.2k Reading time ≈ 1 mins.

1995. 统计特殊四元组

暴力法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int countQuadruplets(vector<int>& nums) {
        int ret = 0;
        int n = nums.size();
        for(int i = 0; i < n; ++i)
        {
            int a = nums[i];
            for(int j = i + 1; j < n; ++j)
            {
                int t = nums[j] + a;
                unordered_map<int, int> map;
                for(int k = j + 1; k < n; ++k)
                {
                    ret += map[nums[k]];
                    ++map[t + nums[k]];
                }
            }
        }
        return ret;
    }
};

O(n^3)

优化1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int countQuadruplets(vector<int>& nums) {
        int ret = 0;
        int n = nums.size();
        unordered_map<int, int> map;
        for(int c = n - 2; c >= 2; --c) // 从后往前遍历的过程中，hash记录下了所有的值，一旦前面和会等于记录的值，就为一个四元组
        {
            ++map[nums[c + 1]];
            for(int a = 0; a < c; ++a)
                for(int b = a + 1; b < c; ++b)
                    if(int sum = nums[c] + nums[a] + nums[b]; map.count(sum))
                        ret += map[sum];
        }
        return ret;
    }
};

O(n^3)

优化2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int countQuadruplets(vector<int>& nums) {
        int ret = 0;
        int n = nums.size();
        unordered_map<int, int> map;
        for(int b = n - 3; b >= 1; --b) // b+1表示c，往回退时候，c会逐渐遍历到，这样就有所有的d和所有的c
        {
            for(int d = b + 2; d < n; ++d)
                ++map[nums[d] - nums[b + 1]];
            for(int a = 0; a < b; ++a)
                if(int sum = nums[a] + nums[b]; map.count(sum))
                    ret += map[sum];
        }
        return ret;
    }
};