Solution
Approach Notes
The approaches described below assume some familiarity with the two pointer technique that can be used to solve the LeetCode problem "Two Sum".
In the problem, we have a sorted array A
of unique elements, and want to know how many i < j
with A[i] + A[j] == target
.
The idea that does it in linear time, is that for each i
in increasing order, the j
's that satisfy the equation A[i] + A[j] == target
are decreasing.
def solve(A, target): # Assume A already sorted i, j = 0, len(A)  1 ans = 0 while i < j: if A[i] + A[j] < target: i += 1 elif A[i] + A[j] > target: j = 1 else: ans += 1 i += 1 j = 1 return ans
This is not a complete explanation. For more on this problem, please review the LeetCode problem "Two Sum".
Approach 1: Three Pointer
Intuition and Algorithm
Sort the array. For each i
, set T = target  A[i]
, the remaining target. We can try using a twopointer technique to find A[j] + A[k] == T
. This approach is the natural continuation of trying to make the twopointer technique we know from previous problems, work on this problem.
Because some elements are duplicated, we have to be careful. In a typical case, the target is say, 8
, and we have a remaining array (A[i+1:]
) of [2,2,2,2,3,3,4,4,4,5,5,5,6,6]
. We can analyze this situation with cases.
Whenever A[j] + A[k] == T
, we should count the multiplicity of A[j]
and A[k]
. In this example, if A[j] == 2
and A[k] == 6
, the multiplicities are 4
and 2
, and the total number of pairs is 4 * 2 = 8
. We then move to the remaining window A[j:k+1]
of [3,3,4,4,4,5,5,5]
.
As a special case, if A[j] == A[k]
, then our manner of counting would be incorrect. If for example the remaining window is [4,4,4]
, there are only 3 such pairs. In general, when A[j] == A[k]
, we have pairs (j,k)
(with j < k
) that satisfy A[j] + A[k] == T
, where is the multiplicity of A[j]
(in this case ).
For more details, please see the inline comments.
Complexity Analysis

Time Complexity: , where is the length of
A
. 
Space Complexity: .
Approach 2: Counting with Cases
Intuition and Algorithm
Let count[x]
be the number of times that x
occurs in A
. For every x+y+z == target
, we can try to count the correct contribution to the answer. There are a few cases:

If
x
,y
, andz
are all different, then the contribution iscount[x] * count[y] * count[z]
. 
If
x == y != z
, the contribution is . 
If
x != y == z
, the contribution is . 
If
x == y == z
, the contribution is .
(Here, denotes the binomial coefficient .)
Each case is commented in the implementations below.
Complexity Analysis

Time Complexity: , where is the length of
A
, and is the maximum possible value ofA[i]
. (Note that this solution can be adapted to be even in the case that is very large.) 
Space Complexity: .
Approach 3: Adapt from Three Sum
Intuition and Algorithm
As in Approach 2, let count[x]
be the number of times that x
occurs in A
. Also, let keys
be a sorted list of unique values of A
. We will try to adapt a 3Sum algorithm to work on keys
, but add the correct answer contributions.
For example, if A = [1,1,2,2,3,3,4,4,5,5]
and target = 8
, then keys = [1,2,3,4,5]
. When doing 3Sum on keys
(with i <= j <= k
), we will encounter some tuples that sum to the target, like (x,y,z) = (1,2,5), (1,3,4), (2,2,4), (2,3,3)
. We can then use count
to calculate how many such tuples there are in each case.
This approach assumes familiarity with 3Sum. For more, please visit the associated LeetCode problem here https://leetcode.com/problems/3sum.
Complexity Analysis

Time Complexity: , where is the length of
A
. 
Space Complexity: .
Analysis written by: @awice.