- 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)
Another approach is the variant of 3 sum, it counts the combinations of 3 unique numbers that sum up to target. In this approach, we don't need to iterate all actual numbers, we just need to count combinations of uniques values that sum to target, and multiply their frequencies.
For example, [1, 1, 2, 2, 3, 3, 4, 4, 5, 5] and target = 8, we just iterate all unique triplets a <= b <= c such that a + b + c == target, then use count of a, b, c to calculate the number of combinations.
Implementation steps:
- Count all the numbers using hash map.
- Find all the unique keys as
aandbby sorting the keys in the map. Sort keys to prevent counting(2, 1, 3)and(1, 2, 3)as different. - For each unique pair
(a, b), calculate thecbyc = target - a - b. We have to skip any triplet that is NOTa <= b <= c. - Next we have to ensure
cexists in the map because all numbers must come from the input array. - Then we can calculate the number of combinations by the formula:
| Case | Condition | Formula |
|---|---|---|
| 1. All same | a == b == c |
Comb(freq[a], 3) |
| 2. Two same | a == b ≠ c |
Comb(freq[a], 2) × freq[c] |
| 3. Two same | a ≠ b == c |
freq[a] × Comb(freq[b], 2) |
| 4. All distinct | a ≠ b ≠ c |
freq[a] × freq[b] × freq[c] |
Use [1, 1, 2, 2, 3, 3, 4, 4, 5, 5] and target = 8 as an example:
Valid triplet values:
(1, 2, 5)→2 × 2 × 2 = 8// Case 4(1, 3, 4)→2 × 2 × 2 = 8// Case 4(2, 2, 4)→Comb(2, 2) × 2 = 1 × 2 = 2// Case 2(2, 3, 3)→2 × Comb(2, 2) = 2 × 1 = 2// Case 3 Total =8 + 8 + 2 + 2 = 20
fun threeSumMulti(arr: IntArray, target: Int): Int {
var count = 0L
val countMap = HashMap<Int, Int>()
for (num in arr) {
countMap[num] = (countMap[num] ?: 0) + 1
}
val keys = countMap.keys.sorted()
for (i in keys.indices) {
for (j in i until keys.size) {
val a = keys[i]
val b = keys[j]
val c = target - a - b
// Ensure a <= b <= c
if (a > b || b > c) continue
// We have to ensure c exists in the map because all numbers must come from the input array
if (c !in keys) continue
val countA = countMap[a]!!.toLong()
val countB = countMap[b]!!.toLong()
val countC = countMap[c]!!.toLong()
// Now, a, b, c all are in keys
count += when {
// Comb(countA, 3)
a == b && b == c -> countA * (countA - 1) * (countA - 2) / 6
// Comb(countA, 2) * countC
a == b && b != c -> countA * (countA - 1) / 2 * countC
// countA * Comb(countB, 2)
a != b && b == c -> countA * countB * (countB - 1) / 2
a != b && b != c -> countA * countB * countC
else -> 0L
}
}
}
return (count % mod).toInt()
}We can use the same approach as 1. Two Sum, we iterate the array as the third element, and we store the sum of the first and second elements in the map.
This approach fixes arr[i] as the 3rd number, and asking:
"How many pairs
(j, k)have occurred before such thatarr[j] + arr[k] == target - arr[i]?"
So we use a map to record all pairs sums arr[j] + arr[k] and their counts. And iterate each arr[i], check if there is any pair whose sum + arr[i] == target. (That is looking for arr[j] + arr[k] == target - arr[i])
- 我们可以给他做一个变形:
arr[i] + arr[j] == target − arr[k],相当于我们仅仅只需要有多少个(i,j)满足等于target − arr[k]即可。- Use a map to count all sums of two numbers. Then, iteate
ito check iftarget - arr[i]is in map, it means we have a 3 sum if it's in map.
fun threeSumMulti(arr: IntArray, target: Int): Int {
val map = HashMap<Int, Int>()
var count = 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) {
count = (count + (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 count.toInt()
}// ---- Example 1 ----
[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}
// ---- Example 2 ----
[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}Or equivalently, we fix arr[i] as the first element, then we have a new target = target - arr[i], and we can use two sum approach to find arr[j] + arr[k] == new target.
Why updating
map[first]? In this approach, themapstores "the count of numbers we've seen so far": fromarr[0]toarr[i].
- We are fixing
arr[i]as the 1st number. - Then for all future
i < j, we pairarr[i]andarr[j], then look forarr[k]such that:
// Key idea:
arr[i] + arr[j] + arr[i] == target
→ arr[k] = target - arr[i] - arr[j]
// In our implementation:
twoSum = target - arr[i]
→ complement = twoSum - arr[j]
= arr[k]If the complement (arr[k]) has been seen before, we can pair to be a valid triplet.
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? No
j 3 - 2 = 1 in map? No
// map[3] = 1
map = {3: 1}
// Second iteration
[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 += 2