- All the elements are the same.
- No valid triplets.
- Some numbers appear multiple times.
- How to check if
arr[i] + arr[j] + arr[k] == target? (3 sum)
Same approach as 15. 3Sum
- How to count the number of valid pairs of
arr[i] + arr[j] == target? (Count of 2 sum)
Same approach as 1. Two Sum, but we store the count of each number.
fun countTwoSum(nums: IntArray, target: Int): Int {
val map = HashMap<Int, Int>()
var count = 0
for (num in nums) {
val complement = target - num
if (complement in map) {
count += map[complement] ?: 0
}
map[num] = (map[num] ?: 0) + 1
}
return count
}
target = 4
1a, 1b, 3a, 3b, 3c
2 x 3 = 6
(1a, 3a)
(1a, 3b)
(1a, 3c)
(1b, 3a)
(1b, 3b)
(1b, 3c)
- For the input array is
[1, 3, 3, 3](Not necessarily sorted) and target is7, I find the tuple1 + 3 + 3 == 7, then how to count the number of tuples?
There is one 1 and three 3s, and we can choose any two 3s to form a tuple. So the number of tuples is comb(3, 2) = 3 * (3 - 1) / 2 = 3. Why? Because we can choose any two 3s from three 3s.
3, 3, 3
* *
* *
* *We can use the similar approach of 15. 3Sum to solve this problem. We can sort the array first, then use two pointers to find the pairs.
// After sorting
target = 7
1, 1, 3, 3, 3, 3
i
L R
L R
// 1 + 3 + 3 == 7, and arr[L] = arr[R], there are all 3's between L and R
// We need to choose 2 from 3's => count += comb(3, 2) = 3
// Another example
target = 8
1, 3, 3, 3, 4, 4
i
L L L R R
// 1 + 3 + 4 == 8, arr[L] != arr[R], we need to count how many 3's and 4's between L and R by moving L and R
// len(L) = 3, len(R) = 2, count += len(L) * len(R) = 6private val mod = 1_000_000_007
fun threeSumMulti(arr: IntArray, target: Int): Int {
val n = arr.size
arr.sort()
var count = 0L
for (i in arr.indices) {
var left = i + 1
var right = n - 1
while (left < right) {
val sum = arr[i] + arr[left] + arr[right]
if (sum == target) {
// All elements between left and right are equal, we calculate the number of combinations
if (arr[left] == arr[right]) {
val combinations = (right - left + 1).toLong() * (right - left) / 2
count += combinations
count %= mod
break
}
// arr[left] != arr[right], we need to count how many same value of arr[left] and arr[right] between left and right
var leftCount = 1
var rightCount = 1
while (left + 1 < right && arr[left] == arr[left + 1]) {
left++
leftCount++
}
while (left < right - 1 && arr[right - 1] == arr[right]) {
right--
rightCount++
}
count += leftCount.toLong() * rightCount
count %= mod
left++
right--
} else if (sum < target) {
left++
} else {
right--
}
}
}
return count.toInt()
}- Time Complexity:
O(n^2) - Space Complexity:
O(1)
We can use the same approach as 1. Two Sum, we iterate the first element, and use two sum approach to find the second + third elements == complement.
fun threeSumMulti(arr: IntArray, target: Int): Int {
val map = HashMap<Int, Int>()
var count = 0L
// Iterate the array as the first element
for (i in arr.indices) {
val first = arr[i]
val twoSum = target - first
// Given a new target (twoSum), we iterate the array as the second element to find the third element
for (j in i + 1 until arr.size) {
val complement = twoSum - arr[j]
if (complement in map) {
count = (count + map[complement]!!) % mod
}
}
map[first] = (map[first] ?: 0) + 1
}
return count.toInt()
}[3, 1, 2] target = 6, answer = 1
i twoSum = 6 - 3 = 3
j 3 - 1 = 2 in map?
j 3 - 2 = 1 in map?
map = {3: 1}
[3, 1, 2]
i twoSum = 6 - 1 = 5
j 5 - 2 = 3 in map? Yes, count += 1
// ----------------------------
[1, 1, 2, 2, 2] target = 5, answer = 6
i twoSum = 5 - 1 = 4
j 4 - 1 = 3 in map?
j 4 - 3 = 2 in map?
j 4 - 2 = 2 in map?
j 4 - 2 = 2 in map?
map = {1: 1}
[1, 1, 2, 2, 2]
i twoSum = 5 - 1 = 4
j 4 - 2 = 2 in map?
j 4 - 2 = 2 in map?
j 4 - 2 = 2 in map?
map = {1: 2}
[1, 1, 2, 2, 2]
i twoSum = 5 - 2 = 3
j 3 - 2 = 1 in map? Yes, count += 2
j 3 - 2 = 1 in map? Yes, count += 2
map = {1: 2, 2: 1}
[1, 1, 2, 2, 2]
i twoSum = 5 - 2 = 3
j 3 - 2 = 1 in map? Yes, count += 2Or equivalently, we iterate the array as the third element, and we store the sum of the first and second elements in the map.
我们可以给他做一个变形:
arr[i] + arr[j] == target − arr[k],相当于我们仅仅只需要有多少个(i,j)满足等于target − arr[k]即可。
fun threeSumMulti(arr: IntArray, target: Int): Int {
val map = HashMap<Int, Int>()
var result = 0L
// Iterate through the array as the third element
for (i in arr.indices) {
val complement = target - arr[i] // We check if first + second == complement
if (complement in map) {
result = (result + (map[complement] ?: 0).toLong()) % mod
}
// Iterate from 0 to i - 1 as the sum of first + second
// We have seen all the elements before arr[i], so we add all sum of first + second pairs to the map
for (j in 0 until i) {
val sum = arr[i] + arr[j]
map[sum] = (map[sum] ?: 0) + 1
}
}
return result.toInt()
}[3, 1, 2] target = 6, answer = 1
i complement = 6 - 3 = 3, 3 in map? No
[3, 1, 2]
i complement = 6 - 1 = 5, 5 in map? No
j map = {4: 1}
[3, 1, 2]
i complement = 6 - 2 = 4, 4 in map? Yes, count += 1
j--| map = {4: 1, 5: 1, 3: 1}
// ----------------------------
[1, 1, 2, 2, 2] target = 5, answer = 6
i complement = 5 - 1 = 4, 4 in map? No
[1, 1, 2, 2, 2]
i complement = 5 - 1 = 4, 4 in map? No
j map = {2: 1}
[1, 1, 2, 2, 2]
i complement = 5 - 2 = 3, 3 in map? No
j--| map = {2: 1, 3: 2}
[1, 1, 2, 2, 2]
i complement = 5 - 2 = 3, 3 in map? Yes, count += 2
j-----| map = {2: 1, 3: 4, 4: 1}
[1, 1, 2, 2, 2]
i complement = 5 - 2 = 3, 3 in map? Yes, count += 4
j--------| map = {2: 1, 3: 6, 4: 3}