Medium

题目描述

给你一个整数数组 arr ，以及一个整数 target ，请你返回有多少个三元组 i, j, k 满足 i < j < k 且 arr[i] + arr[j] + arr[k] == target 。

由于答案会很大，请返回答案对 10^9 + 7 取余的结果。

示例 1：

输入：arr = [1,1,2,2,3,3,4,4,5,5], target = 8
输出：20
解释：
按值枚举 (arr[i], arr[j], arr[k])：
(1, 2, 5) 出现 8 次；
(1, 3, 4) 出现 8 次；
(2, 2, 4) 出现 2 次；
(2, 3, 3) 出现 2 次。

示例 2：

输入：arr = [1,1,2,2,2,2], target = 5
输出：12
解释：
arr[i] = 1, arr[j] = arr[k] = 2 出现 12 次：
我们从 [1,1] 中选择一个 1，有 2 种方法，
从 [2,2,2,2] 中选择两个 2，有 6 种方法。

示例 3：

输入：arr = [2,1,3], target = 6
输出：1
解释：(1, 2, 3) 在数组中出现一次，所以我们返回 1。

提示：

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

解题思路

这道题要求统计满足三数之和等于目标值的三元组数量。由于数组中可能有重复元素，我们需要考虑组合数学的方法。

方法一：计数 + 组合数学（推荐）

核心思路是先统计每个数字的出现次数，然后枚举所有可能的三个数字的组合。对于每种组合 (a, b, c)，如果 a + b + c == target，我们需要计算有多少种方式选择这三个数字。

根据三个数字的关系，分为三种情况：

  1. 三个数字都相同 (a == b == c)：需要从 count[a] 个数字中选择 3 个，方案数为 C(count[a], 3)
  2. 两个数字相同 (a == b != c 或其他情况)：需要从 count[a] 中选 2 个，从 count[c] 中选 1 个，方案数为 C(count[a], 2) * C(count[c], 1)
  3. 三个数字都不同 (a != b != c)：方案数为 count[a] * count[b] * count[c]

方法二：排序 + 双指针

先对数组排序，然后固定第一个数字，用双指针寻找后两个数字。但由于有重复元素，需要特别处理重复情况的计数。

推荐使用方法一，因为它在处理重复元素时更加直观且高效。

代码实现

class Solution {
public:
    int threeSumMulti(vector<int>& arr, int target) {
        const int MOD = 1e9 + 7;
        map<int, int> count;
        
        // 统计每个数字的出现次数
        for (int num : arr) {
            count[num]++;
        }
        
        long long result = 0;
        
        // 枚举所有可能的三个数字组合
        for (auto& [i, ci] : count) {
            for (auto& [j, cj] : count) {
                if (i > j) continue;
                
                int k = target - i - j;
                if (j > k) continue;
                
                if (count.find(k) != count.end()) {
                    int ck = count[k];
                    
                    if (i == j && j == k) {
                        // 三个数字都相同：C(ci, 3)
                        result += (long long)ci * (ci - 1) * (ci - 2) / 6;
                    } else if (i == j && j != k) {
                        // i == j != k：C(ci, 2) * C(ck, 1)
                        result += (long long)ci * (ci - 1) / 2 * ck;
                    } else if (j == k && i != j) {
                        // i != j == k：C(ci, 1) * C(cj, 2)
                        result += (long long)ci * cj * (cj - 1) / 2;
                    } else if (i != j && j != k && i != k) {
                        // 三个数字都不同
                        result += (long long)ci * cj * ck;
                    }
                    
                    result %= MOD;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def threeSumMulti(self, arr: List[int], target: int) -> int:
        MOD = 10**9 + 7
        count = {}
        
        # 统计每个数字的出现次数
        for num in arr:
            count[num] = count.get(num, 0) + 1
        
        result = 0
        
        # 枚举所有可能的三个数字组合
        for i in count:
            for j in count:
                if i > j:
                    continue
                
                k = target - i - j
                if j > k:
                    continue
                
                if k in count:
                    ci, cj, ck = count[i], count[j], count[k]
                    
                    if i == j == k:
                        # 三个数字都相同：C(ci, 3)
                        result += ci * (ci - 1) * (ci - 2) // 6
                    elif i == j != k:
                        # i == j != k：C(ci, 2) * C(ck, 1)
                        result += ci * (ci - 1) // 2 * ck
                    elif j == k != i:
                        # i != j == k：C(ci, 1) * C(cj, 2)
                        result += ci * cj * (cj - 1) // 2
                    elif i != j != k != i:
                        # 三个数字都不同
                        result += ci * cj * ck
                    
                    result %= MOD
        
        return result

public class Solution {
    public int ThreeSumMulti(int[] arr, int target) {
        const int MOD = 1000000007;
        var count = new Dictionary<int, int>();
        
        // 统计每个数字的出现次数
        foreach (int num in arr) {
            count[num] = count.GetValueOrDefault(num, 0) + 1;
        }
        
        long result = 0;
        
        // 枚举所有可能的三个数字组合
        foreach (var kvp1 in count) {
            int i = kvp1.Key;
            int ci = kvp1.Value;
            
            foreach (var kvp2 in count) {
                int j = kvp2.Key;
                int cj = kvp2.Value;
                
                if (i > j) continue;
                
                int k = target - i - j;
                if (j > k) continue;
                
                if (count.ContainsKey(k)) {
                    int ck = count[k];
                    
                    if (i == j && j == k) {
                        // 三个数字都相同：C(ci, 3)
                        result += (long)ci * (ci - 1) * (ci - 2) / 6;
                    } else if (i == j && j != k) {
                        // i == j != k：C(ci, 2) * C(ck, 1)
                        result += (long)ci * (ci - 1) / 2 * ck;
                    } else if (j == k && i != j) {
                        // i != j == k：C(ci, 1) * C(cj, 2)
                        result += (long)ci * cj * (cj - 1) / 2;
                    } else if (i != j && j != k && i != k) {
                        // 三个数字都不同
                        result += (long)ci * cj * ck;
                    }
                    
                    result %= MOD;
                }
            }
        }
        
        return (int)result;
    }
}

/**
 * @param {number[]} arr
 * @param {number} target
 * @return {number}
 */
var threeSumMulti = function(arr, target) {
    const MOD = 1000000007;
    const count = new Array(101).fill(0);
    
    for (let num of arr) {
        count[num]++;
    }
    
    let result = 0;
    
    for (let i = 0; i <= 100; i++) {
        for (let j = i; j <= 100; j++) {
            let k = target - i - j;
            if (k < 0 || k > 100) continue;
            
            if (i === j && j === k) {
                result = (result + Math.floor(count[i] * (count[i] - 1) * (count[i] - 2) / 6)) % MOD;
            } else if (i === j && j !== k) {
                if (k > j) {
                    result = (result + Math.floor(count[i] * (count[i] - 1) / 2) * count[k]) % MOD;
                }
            } else if (i !== j && j === k) {
                if (j > i) {
                    result = (result + count[i] * Math.floor(count[j] * (count[j] - 1) / 2)) % MOD;
                }
            } else {
                if (k > j) {
                    result = (result + count[i] * count[j] * count[k]) % MOD;
                }
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型计数方法排序+双指针
时间复杂度O(U²)O(n²)
空间复杂度O(U)O(1)

其中 U 表示数组中不同元素的个数，n 表示数组长度。由于题目限制 0 <= arr[i] <= 100，所以 U 最大为 101，因此计数方法的时间复杂度实际上是常数级别的。