LeetCode923-三数之和的多种可能

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/3sum-with-multiplicity/

中文链接：https://leetcode-cn.com/problems/3sum-with-multiplicity/

题目详述

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

由于结果会非常大，请返回 结果除以 10^9 + 7 的余数。

示例 1：

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

示例 2：

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

提示：

  1. 3 <= A.length <= 3000
  2. 0 <= A[i] <= 100
  3. 0 <= target <= 300

题目详解

类似于 LeetCode15-三数之和，LeetCode15-三数之和 是求不重复的三元组，而本题是满足要求的三元组数量，可以重复。

方法一：双指针。

  • 先对数组进行排序。
  • 遍历数组，固定第一个数，对剩下的两个数运用双指针进行扫描。
  • 注意计数的计算方法。
  • 时间复杂度为 O(n^2)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class LeetCode_00923 {

    public int threeSumMulti(int[] A, int target) {
        final int MOD = (int) (1e9 + 7);
        Arrays.sort(A);
        int n = A.length;
        int res = 0;
        for (int i = 0; i < n; ++i) {
            int l = i + 1, r = n - 1;
            while (l < r) {
                int sum = A[i] + A[l] + A[r];
                if (sum < target) {
                    ++l;
                } else if (sum > target) {
                    --r;
                } else {
                    if (A[l] == A[r]) {
                        int cnt = r - l + 1;
                        res  = (res + cnt * (cnt - 1) / 2) % MOD;
                        break;
                    } else {
                        int left = 1;
                        while (l + 1 < r && A[l + 1] == A[l]) {
                            ++left;
                            ++l;
                        }
                        int right = 1;
                        while (l < r - 1 && A[r - 1] == A[r]) {
                            ++right;
                            --r;
                        }
                        res = (res + left * right) % MOD;
                        ++l;
                        --r;
                    }
                }
            }
        }
        return res;
    }
}
  • 由于数据范围在 0~100 之间，我们可以先对每个数出现次数进行统计。
  • 再运用 i、j 代表前两个数，求得第三个数 k = targer - i -j， i、j 、k 三个数满足 i <= j <= k <= 100。
  • 若 i = j = k，则结果加上 cnt[i] * (cnt[i] - 1) * (cnt[i] - 2) / 6。
  • 若 i = j < k，则结果加上 cnt[i] * (cnt[i] - 1) / 2 * cnt[k]。
  • 若 i < j = k，则结果加上 cnt[i] * cnt[j] * (cnt[j] - 1) / 2。
  • 若 i < j < k，则结果加上 cnt[i] * cnt[j] * cnt[k]。
  • 注意，需要在计算过程中防止溢出，可以转为 long 型计算。
  • 时间复杂度为 O(n + w^2)，w 代表数据范围最大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class LeetCode_00923 {

    public int threeSumMulti(int[] A, int target) {
        final int MOD = (int) (1e9 + 7);
        int[] cnt = new int[101];
        for (int a : A) {
            ++cnt[a];
        }
        int res = 0;
        // i、j、k 满足 i <= j <= k <= 100
        for (int i = 0; i <= 100; ++i) {
            for (int j = i; j <= 100; ++j) {
                int k = target - i - j;
                if (k < j) {
                    break;
                }
                if (k > 100) {
                    continue;
                }
                if (i == j && j == k) {
                    res += 1L * cnt[i] * (cnt[i] - 1) * (cnt[i] - 2) / 6 % MOD;
                } else if (i == j && j < k) {
                    res += 1L * cnt[i] * (cnt[i] - 1) / 2 * cnt[k] % MOD;
                } else if (i < j && j == k) {
                    res += 1L * cnt[i] * cnt[j] * (cnt[j] - 1) / 2 % MOD;
                } else {
                    res += 1L * cnt[i] * cnt[j] * cnt[k] % MOD;
                }
                res %= MOD;
            }
        }
        return res;
    }
}