923.三数之和的多种可能

三数之和的多种可能

给定一个整数数组 arr，以及一个整数 target 作为目标值，返回满足 i < j < k 且 arr[i] + arr[j] + arr[k] == target 的元组 i, j, k 的数量。

由于结果会非常大，请返回 10^9 + 7 的模。

示例 1:

输入：arr = [1,1,2,2,3,3,4,4,5,5], target = 8
输出：20

示例 2:

输入：arr = [1,1,2,2,2,2], target = 5
输出：12

提示:

• 3 <= arr.length <= 3000
• 0 <= arr[i] <= 100
• 0 <= target <= 300

解析

先统计每个数字出现的次数，然后遍历所有可能的两个数字组合，计算第三个数字的值，根据三个数的关系计算组合数。

var threeSumMulti = function (arr, target) {
  const MOD = 10 ** 9 + 7;
  const count = new Map();
  for (const num of arr) {
    count.set(num, (count.get(num) || 0) + 1);
  }

  const keys = [...count.keys()].sort((a, b) => a - b);
  let result = 0;

  for (let i = 0; i < keys.length; i++) {
    const x = keys[i];
    for (let j = i; j < keys.length; j++) {
      const y = keys[j];
      const z = target - x - y;
      if (z < y) continue;

      if (count.has(z)) {
        const cx = count.get(x);
        const cy = count.get(y);
        const cz = count.get(z);

        if (x === y && y === z) {
          result = (result + (cx * (cx - 1) * (cx - 2)) / 6) % MOD;
        } else if (x === y && y !== z) {
          result = (result + ((cx * (cx - 1)) / 2) * cz) % MOD;
        } else if (x !== y && y === z) {
          result = (result + cx * ((cy * (cy - 1)) / 2)) % MOD;
        } else {
          result = (result + cx * cy * cz) % MOD;
        }
      }
    }
  }

  return result;
};

时间复杂度 O(n²)，空间复杂度 O(n)。