题目

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

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

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/count-special-quadruplets

解答

用最暴力的解法，也可以过，for嵌套四层循环。

class Solution {
public:
    int countQuadruplets(vector<int> &nums) {
        int n = nums.size();
        int ret = 0;

        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                for (int k = j + 1; k < n; ++k) {
                    for (int l = k + 1; l < n; ++l) {
                        if (nums[i] + nums[j] + nums[k] == nums[l]) {
                            ret++;
                        }
                    }
                }
            }
        }

        return ret;
    }
};

从降低复杂度来看，无非就是利用哈希表，来降低查找目标数字的时间复杂度，从遍历改为哈希查找。

第一个优化方法是在寻找第四个数字时，通过哈希表进行查找，这里略。

第二个优化方法是根据 A + B + C = D 推导出 A + B = D - C，然后用哈希表存储 D - C 的值完成求解。

具体流程如下：

1. A, B, C, D 四个数，位置也依次是从小到大的，所以从建立 D - C 差值的哈希表上来看，一定是一个逐渐加内容的过程，所以要让差值的数量从小到大进行遍历，怎么让D-C的差值数量最少呢？当然是C, D 取值只能是倒数第二个和倒数第一个。所以，在循环中的判定条件应该是以 B 为基准，即，让B从倒数第三个数开始取值，一直取到第二个值为止，这便是第一层循环。

2. 再来看哈希表的存储，由于 B 是从最右侧取值，循环到最左侧，C和D的取值范围也相应的扩大。第一次循环中，C和D是固定的，因此在哈希表中存储一个（倒数第一减去倒数第二的差值）值即可，当 B 向左走一个单位时，这个多出来的值应该能让 C 取到，而 D 取不到，所以增加的差值可能，应该是b + 1 右侧（不包括b+1）所有的值减去（b + 1）处的值。所以每次通过for循环将这些多出来的差值，存储到哈希表中即可。

3. 基于上面的一次循环，后边的嵌套循环就相对容易理解，即取A的所有可能值，求 A+B 的值，来得到要找的值 D-C，直接通过hash表找即可。如果有，就将返回值加上差值的个数即可。

代码如下：

class Solution {
public:
    int countQuadruplets(vector<int> &nums) {
        int n = nums.size();
        int ret = 0;
        unordered_map<int, int> mp;

 		// 让b作第一层循环，从最大值开始取值，循环到最小值
        for (int b = n - 3; b >= 1; --b) {
          
          	// 在b的循环中，b每往左移动一个位置，就空出来一个位置让c来取值，将每一种与多出来的c差值存储到map中
            for (int d = b + 2; d < n; ++d) {
                mp[nums[d] - nums[b + 1]]++;
            }

            // 内循环，a作为循环内容，来求解
            for (int a = 0; a < b; ++a) {
                int aim = nums[a] + nums[b];
              
              	// 如果哈希表中有该差值，就加上存在的个数
                if (mp[aim]) {
                    ret += mp[aim];
                }
            }
        }

        return ret;
    }
};