leetcode Daily Challenge on March 23th, 2021.
Difficulty : Medium
Related Topics : Two Pointers
Given an integer array
arr
, and an integertarget
, return the number of tuplesi, j, k
such thati < j < k
andarr[i] + arr[j] + arr[k] == target
.As the answer can be very large, return it modulo
10
9
+ 7
.Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8 Output: 20 Explanation: Enumerating by the values (arr[i], arr[j], arr[k]): (1, 2, 5) occurs 8 times; (1, 3, 4) occurs 8 times; (2, 2, 4) occurs 2 times; (2, 3, 3) occurs 2 times.
Input: arr = [1,1,2,2,2,2], target = 5 Output: 12 Explanation: arr[i] = 1, arr[j] = arr[k] = 2 occurs 12 times: We choose one 1 from [1,1] in 2 ways, and two 2s from [2,2,2,2] in 6 ways.
3 <= arr.length <= 3000
0 <= arr[i] <= 100
0 <= target <= 300
- mine
- Java
-
Runtime: 2 ms, faster than 97.14%, Memory Usage: 38.2 MB, less than 97.50% of Java online submissions
// O(N + W^2)time // O(W) space // W = 101 public int threeSumMulti(int[] A, int target) { long[] c = new long[101]; for (int a : A) c[a]++; long res = 0; for (int i = 0; i <= 100; i++) for (int j = i; j <= 100; j++) { int k = target - i - j; if (k > 100 || k < 0) continue; if (i == j && j == k) // 3 //C a res += c[i] * (c[i] - 1) * (c[i] - 2) / 6; else if (i == j && j != k) // 1 2 //C a * C b res += c[i] * (c[i] - 1) / 2 * c[k]; else if (j < k) // 1 1 1 //C a * C b * C c res += c[i] * c[j] * c[k]; } return (int)(res % (1e9 + 7)); }
-
- Java
- the most votes
Runtime: 2 ms, faster than 97.14%, Memory Usage: 38.2 MB, less than 97.50% of Java online submissions
public int threeSumMulti(int[] A, int target) { long[] c = new long[101]; for (int a : A) c[a]++; long res = 0; for (int i = 0; i <= 100; i++) for (int j = i; j <= 100; j++) { int k = target - i - j; if (k > 100 || k < 0) continue; if (i == j && j == k) res += c[i] * (c[i] - 1) * (c[i] - 2) / 6; else if (i == j && j != k) res += c[i] * (c[i] - 1) / 2 * c[k]; else if (j < k) res += c[i] * c[j] * c[k]; } return (int)(res % (1e9 + 7)); }