923. 3Sum With Multiplicity
Last updated
Last updated
/**
* Time complexity :
* Space complexity :
*/
// Time Limit Exceeded
class Solution {
public int threeSumMulti(int[] arr, int target) {
int n = arr.length;
long result = 0;
Arrays.sort(arr);
for(int i = 0; i < n-2; i++) {
int t = target - arr[i];
int left = i + 1, right = n-1;
while(left < right) {
int sum = arr[left] + arr[right];
if(sum < t) {
left++;
} else if(sum > t) {
right--;
} else {
int tempRight = right;
while(left < right && arr[left] + arr[right] == t) {
result++;
right--;
}
right = tempRight;
left++;
}
}
}
return (int) (result%1000000007);
}
}/**
* Time complexity :
* Space complexity :
*/
class Solution {
private final int MOD = 1000000007;
public int threeSumMulti(int[] arr, int target) {
int result = 0;
Map<Integer, Integer> map = new HashMap();
for(int i = 0; i < arr.length; i++) {
result = (result + map.getOrDefault(target-arr[i], 0)) % MOD;
for(int j = 0; j < i; j++) {
map.put(arr[i]+arr[j], map.getOrDefault(arr[i]+arr[j], 0) + 1);
}
}
return result;
}
}/**
* Time complexity : O(N^2), where N is the length of array.
* Space complexity : O(N)
*/
class Solution {
private final int MOD = 1000000007;
public int threeSumMulti(int[] arr, int target) {
int result = 0;
for(int i = 0; i < arr.length; i++) {
int[] count = new int[101];
for(int j = i+1; j < arr.length; j++) {
int k = target - arr[i] - arr[j];
if(k >= 0 && k <= 100 && count[k] > 0) {
result = (result + count[k]) % MOD;
}
count[arr[j]]++;
}
}
return result;
}
}/**
* Time complexity : O(N + 100*100) => O(N)
* Space complexity : O(100) => O(1)
*/
class Solution {
private final int MOD = 1_000_000_007;
public int threeSumMulti(int[] arr, int target) {
long result = 0;
long[] count = new long[101];
for(int val: arr) {
count[val]++;
}
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 += (count[i] * (count[i]-1) * (count[i]-2) / 6);
} else if(i == j && j != k) {
result += ((count[i] * (count[i]-1)/2) * count[k]);
} else if(i < j && j < k) {
result += (count[i] * count[j] * count[k]);
}
}
}
return (int) (result%MOD);
}
}