You've successfully subscribed to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your billing info is updated.
Billing info update failed.

# 923. 三数之和的多种可能 - 3Sum With Multiplicity

【双指针】 【桶排序】

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



### Example:

输入：A = [1,1,2,2,3,3,4,4,5,5], target = 8

(1, 2, 5) 出现 8 次；
(1, 3, 4) 出现 8 次；
(2, 2, 4) 出现 2 次；
(2, 3, 3) 出现 2 次。


输入：A = [1,1,2,2,2,2], target = 5

A[i] = 1，A[j] = A[k] = 2 出现 12 次：



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

## Solutions

### Solution  【桶排序】 ( 9ms)

class Solution {
public int threeSumMulti(int[] A, int target) {
long result = 0;
long[] numbers = new long[101]; // 0 <= A[i] <= 100
for (int i: A) {
numbers[i]++;
}
int min = 0;
while (numbers[min] == 0) {
min++;
}
int max = 100;
while (numbers[max] == 0) {
max--;
}
int i = min;
while (i <= max) {
int j = min;
while (j <= max) {
int key = target - i - j;
if (key >= i && key <= j && numbers[key] > 0) {
if (i == j && i != key) {
result += (numbers[i] * (numbers[i] - 1) / 2) * numbers[key];
}else if (i == key && i != j) {
result += numbers[j] * ((numbers[i] - 1) * numbers[i] / 2);
}else if (j == key && i != j) {
result += numbers[i] * ((numbers[j] - 1) * numbers[j] / 2);
}else if (i == j && j == key) {
result += numbers[i] * (numbers[i] - 1) * (numbers[i] - 2) / 6;
}else{
result += numbers[i] * numbers[j] * numbers[key];
}
}
do {
j++;
} while (j < max && numbers[j] == 0);
}
do {
i++;
} while (i < max && numbers[i] == 0);
}
return (int)(result % 1000000007);
}
}


### Solution  ( 7ms)

class Solution {
public static int threeSumMulti(int[] A, int target) {
long res = 0;
int mod=1000000007;
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
int[] count = new int[101];
for (int i = 0; i < A.length; i++) {
count[A[i]]++;
max = A[i] > max ? A[i] : max;
min = A[i] < min ? A[i] : min;
}
for (int i = min; i <= max; i++) {
if (count[i] == 0)
continue;
for (int j = i; j <= max; j++) {
if (count[j] == 0)
continue;
int temp = target - i - j;
if (temp >= j && temp <= max && count[temp] > 0) {
res += getCount(i, j, temp, count[i], count[j], count[temp]);
}
}
}
return (int) (res % mod);
}

private static long getCount(int a, int b, int c, long i, long j, long k) {
if (a == b) {
if (b == c) {
if (i < 3) {
return 0;
} else {
return i * (i - 1)* (i - 2)  / 6;
}
} else {
if (i < 2) {
return 0;
} else {
return i * (i - 1) / 2 * k;
}
}
} else if (b == c) {
if (j < 2) {
return 0;
} else {
return j * (j - 1) / 2 * i;
}

} else {
return i * j * k;
}
}
}