What is 3Sum With Multiplicity?

It is a problem where you count all triplets in an array whose sum equals a target, considering repeated numbers and returning modulo 10^9 + 7.

How do repeated elements affect the solution?

Repeated elements require combinatorial counting like C(freq,2) or C(freq,3) to account for multiplicity without overcounting.

Can I use a two-pointer approach here?

Yes, after sorting, fix one element and use two pointers on the remaining array, adjusting counts when elements are equal.

What is the best way to handle large arrays efficiently?

Use a hash map to count element frequencies and compute triplet contributions without enumerating all index combinations.

Why modulo 10^9 + 7 is required?

Because the number of triplets can be very large, taking modulo prevents integer overflow and matches problem constraints.

#923

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

三数之和的多种可能

给定一个整数数组 arr ，以及一个整数 target 作为目标值，返回满足 i 且 arr[i] + arr[j] + arr[k] == target 的元组 i, j, k 的数量。由于结果会非常大，请返回 10 9 + 7 的模。示例 1：输入： arr = [1,1,2,2,3,3,…

数组哈希表双指针排序计数

题目描述

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

由于结果会非常大，请返回 10⁹ + 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.length <= 3000
0 <= arr[i] <= 100
0 <= target <= 300

lightbulb

解题思路

方法一：计数 + 枚举

我们可以用一个哈希表或者一个长度为 $101$ 的数组 $cnt$ 统计数组 $arr$ 中每个元素的出现次数。

然后，我们枚举数组 $arr$ 中的每个元素 $arr[j]$ ，先将 $cnt[arr[j]]$ 减一，然后再枚举 $arr[j]$ 之前的元素 $arr[i]$ ，计算 $c = target - arr[i] - arr[j]$ ，如果 $c$ 在 $[0, 100]$ 的范围内，那么答案就加上 $cnt[c]$ ，最后返回答案。

注意，这里的答案可能会超过 ${10}^9 + 7$ ，所以在每次加法操作后都要取模。

时间复杂度 $O(n^2)$ ，其中 $n$ 为数组 $arr$ 的长度。空间复杂度 $O(C)$ ，其中 $C$ 为数组 $arr$ 中元素的最大值，本题中 $C = 100$ 。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def threeSumMulti(self, arr: List[int], target: int) -> int:
        mod = 10**9 + 7
        cnt = Counter(arr)
        ans = 0
        for j, b in enumerate(arr):
            cnt[b] -= 1
            for a in arr[:j]:
                c = target - a - b
                ans = (ans + cnt[c]) % mod
        return ans

speed

复杂度分析

指标	值
时间	complexity varies: sorting takes O(n log n), scanning with two pointers is O(n^2), and hash counting may reduce repeated computations. Space complexity is O(101) for the hash map due to the value constraint 0 <= arr[i] <= 100.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Interviewer may ask how to handle repeated numbers without overcounting.
question_mark
Interviewer may check if hash counting correctly respects index order i<j<k.
question_mark
Interviewer may probe understanding of combinatorial counting with multiplicities.

warning

常见陷阱

外企场景

error
Failing to account for duplicate elements leading to incorrect counts.
error
Incorrectly applying two-pointer logic without adjusting for identical values.
error
Returning raw counts without modulo 10^9 + 7 causing overflow.

swap_horiz

进阶变体

外企场景

arrow_right_alt
4Sum With Multiplicity extending the pattern to quadruplets.
arrow_right_alt
Targeted Pair Sum With Multiplicity using the same hash counting for pairs.
arrow_right_alt
Subset sum variants with multiplicity constraints on array elements.

help

常见问题

外企场景

继续练习

#1782 统计点对的数目 #1048 最长字符串链 #1054 距离相等的条形码