LeetCode 923. 3Sum With Multiplicity

题目链接 3Sum With Multiplicity

题意类似3Sum,但是我没有把这题和NSum那篇日志放在一起,这道题使用3Sum那种类似思路去解的话时间复杂度很高,只beat 了很少的人,3Sum那种思路可以用三指针法或者 map,我用 map写了一个 version.

还有一种解法效率高了很多,数学的解法,由于0<=A[i]<=100,所以其实范围是很小的,首先我们用一个数组记录所有数组中的数的出现次数,接着从0开始到100做一个双层遍历.因为构成 target 的3个数必定是3个0到100的数,用这种方法实际上是穷举构成 target 的三个数(假设叫 i,j,k)中的任意两个(不妨就是 i 和 j),那么 k = target - i - j.

然后只需要分3种情况即可

1. i== j == k
2. i == j != k
3. i < k && j < k

条件2和3的限制是为了排除重复情况

这里又是参考lee215大神的思路,感谢大佬

3Sum map code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static int threeSumMulti(int[] A, int target) {
if (A.length == 0) {
return 0;
} else if (A.length == 1) {
return A[0] == target ? 1 : 0;
}
int modulo = 1000000007;
long result = 0;
for (int i = 0; i < A.length; i++) {
int cur = A[i];
int sum = target - cur;
Map<Integer, Integer> map = new HashMap<>();
for (int j = i + 1; j < A.length; j++) {
Integer cnt = map.get(sum - A[j]);
if (cnt != null) {
result += cnt;
}
map.put(A[j], map.get(A[j]) == null ? 1 : map.get(A[j]) + 1);
}
}
return (int) (result % modulo);
}

math code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static int threeSumMulti(int[] A, int target) {
long[] bucket = new long[101];
int modulo = 1000000007;
for (int item : A) {
bucket[item]++;
}
long result = 0;
for (int i = 0; i <= 100; i++) {
for (int j = i; j <= 100; j++) {
int k = target - i - j;
if (k < 0 || k > 100) continue;
if (i == j && j == k) result += bucket[i] * (bucket[i] - 1) * (bucket[i] - 2) / 6;
else if (i == j) result += bucket[i] * (bucket[i] - 1) / 2 * bucket[k];
else if (j < k) result += bucket[i] * bucket[j] * bucket[k];
}
}
return (int) (result % modulo);
}
月月说要给我打赏,就还是放了二维码,😝