Leetcode 1995. 统计特殊四元组 （从四重循环开始优化）

Leetcode 1995. 统计特殊四元组 （从四重循环开始优化）

最原始的四重循环：

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

 由于a，b，c，d有顺序要求，是不能先把nums[d]存到HashMap里面，这里要用一个技巧，在三重循环的时候，把nums[d]记录下来

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

二重循环优化技巧

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