923.md

923. 3Sum With Multiplicity

Leetcode link

解题思路

• TC: $$O(N * M)$$， M 是数组 arr 中最大的数
• SC: $$O(M)$$，M 是数组 arr 中最大的数

题目要求我们找出三个数之和为 target 的多种可能，且数组 arr 可能存在重复数字

我们可以观察一下题目给出的范围：

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

可能出现的数字范围 arr[i] 从 0 到 100，那么我们可以用 count[x] 来保存数字 x 在数组中出现的次数，对于每一个 x + y + z = target 组合，我们用数学方法来分析几种可能性的组合：

• x != y != z：有 $$count[x] \times count[y] \times count[z]$$ 种组合
• x == y != z：有 $$\tbinom{count[x]}{2} \times count[z]$$ 种组合
• x == y == z：有 $$count[x] \times \tbinom{count[y]}{2}$$ 种组合
• x == y == z：有 $$\tbinom{count[x]}{3}$$ 种组合

最后把上述所有可能加总取模就好了。

C++

class Solution {
 public:
  int threeSumMulti(vector<int>& arr, int target) {
    int MOD = 1e9 + 7;
    long res = 0;
    long count[101] = {0};
    for (int num : arr) {
      count[num]++;
    }

    // x != y != z
    for (int x = 0; x <= 100; x++) {
      for (int y = x + 1; y <= 100; y++) {
        int z = target - x - y;
        if (y < z && z <= 100) {
          res += (count[x] * count[y] * count[z]) % MOD;
        }
      }
    }

    // x == y != z
    for (int x = 0; x <= 100; x++) {
      int z = target - x * 2;
      if (x < z && z <= 100) {
        res += ((count[x] * (count[x] - 1)) / 2 * count[z]) % MOD;
      }
    }

    // x != y == z
    for (int x = 0; x <= 100; x++) {
      // 想要 target - x 之后还能被 2 整除，必须是 target 跟 x 的奇偶相同
      if (target % 2 == x % 2) {
        int y = (target - x) / 2;
        if (x < y && y <= 100) {
          res += (count[x] * (count[y] * (count[y] - 1)) / 2) % MOD;
        }
      }
    }

    // x == y == z
    if (target % 3 == 0) {
      int x = target / 3;
      if (x >= 0 && x <= 100) {
        res += (count[x] * (count[x] - 1) * (count[x] - 2) / 6) % MOD;
      }
    }

    return (int)res;
  }
};

Javascript

/**
 * @param {number[]} arr
 * @param {number} target
 * @return {number}
 */
var threeSumMulti = function(arr, target) {
    const MOD = 1e9 + 7;
    let res = 0;
    let count = new Array(101).fill(0);
    for (let num of arr) {
      count[num]++;
    }

    // x != y != z
    for (let x = 0; x <= 100; x++) {
      for (let y = x + 1; y <= 100; y++) {
        let z = target - x - y;
        if (y < z && z <= 100) {
          res += (count[x] * count[y] * count[z]) % MOD;
        }
      }
    }

    // x == y != z
    for (let x = 0; x <= 100; x++) {
      let z = target - x * 2;
      if (x < z && z <= 100) {
        res += (Math.floor((count[x] * (count[x] - 1)) / 2) * count[z]) % MOD;
      }
    }

    // x != y == z
    for (let x = 0; x <= 100; x++) {
      // 想要 target - x 之后还能被 2 整除，必须是 target 跟 x 的奇偶相同
      if (target % 2 == x % 2) {
        let y = (target - x) / 2;
        if (x < y && y <= 100) {
          res += Math.floor((count[x] * (count[y] * (count[y] - 1)) )/ 2) % MOD;
        }
      }
    }

    // x == y == z
    if (target % 3 == 0) {
      let x = target / 3;
      if (x >= 0 && x <= 100) {
        res += Math.floor(count[x] * (count[x] - 1) * (count[x] - 2) / 6) % MOD;
      }
    }

    return res;
};