# 三数之和的多种可能 - 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)

 `````` 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 42 43 44 45 `````` ``````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)

 `````` 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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 `````` ``````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; } } } ``````