Brute Force Solution

A naive solution would involve iterating through all possible triplets in the array and checking if their sum equals the target. This approach is straightforward but inefficient.

def threeSumMulti_brute_force(arr, target):
    count = 0
    n = len(arr)
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if arr[i] + arr[j] + arr[k] == target:
                    count += 1
    return count % (10**9 + 7)

• Time Complexity: O(n³), where n is the length of the array.
• Space Complexity: O(1), as we are not using any extra space.

Optimal Solution

To improve efficiency, we can use a counting-based approach. We count the occurrences of each number in the array using a Counter. Then, we iterate through all possible pairs of numbers and check if the third number needed to reach the target exists in the Counter. We handle cases where the numbers are the same carefully to avoid overcounting.

from collections import Counter

def threeSumMulti(arr, target):
    count = Counter(arr)
    ans = 0
    mod = 10**9 + 7

    for i in count:
        for j in count:
            k = target - i - j
            if k not in count:
                continue
            if i == j == k:
                ans += count[i] * (count[i] - 1) * (count[i] - 2) // 6
            elif i == j:
                ans += count[i] * (count[i] - 1) // 2 * count[k]
            elif i < j < k:
                ans += count[i] * count[j] * count[k]

            ans %= mod
    return ans

• Time Complexity: O(n + 101²) = O(1), since the values are bounded by 0 to 100 (inclusive).
• Space Complexity: O(1), as the counter will store at most 101 different values

Edge Cases

• Empty array: The code should handle an empty array gracefully, though the problem statement specifies a minimum array length of 3.
• Target out of range: If the target is significantly smaller or larger than the numbers in the array, the code should efficiently return 0.
• Integer overflow: The intermediate calculations for combinations might result in an integer overflow. We need to use modulo operation to prevent this.