Three Number Sum

Problem

Given an array of distinct integers sums and an integer representing the target sum.

Find all triple numbers in the array sums that adds up to the target sum.

We cannot add a number to itself to get the target sum.

Example 1:

Input: nums = [-8, -6, 1, 2, 3, 6, 7, 15], target = 1

Output: [[-8, -6, 15], [-8, 2, 7], [-8, 3, 6], [-6, 1, 6]]

Explanation:
-8 – 6 + 15 = 1
-8 + 2 + 7 = 1
-8 + 3 + 6 = 1
-6 + 1 + 6 = 1

We sort the input array in ascending order and use two pointers to find out two other numbers that sum with current number to be target number.

Example

Input: nums = [15, -6, 2, 1, 6, 7, 3, -8], target = 1

Output: [[-8, -6, 15], [-8, 2, 7], [-8, 3, 6], [-6, 1, 6]]

Explanation

sorted num = [-8, -6, 1, 2, 3, 6, 7, 15]

currentNumber = -8
LP = -6
RP = 15
-8 – 6 + 15 = 1
-8 + 1 + 7 = 0
-8 + 2 + 7 = 1
-8 + 3 + 6 = 1

currentNumber = -6
LP = 1
RP = 15
-6 + 1 + 15 = 10
-6 + 1 + 7 = 2
-6 + 1 + 6 = 1
-6 + 2 + 3 = -1

currentNumber = 1
LP = 2
RP = 15
1 + 2 + 15 = 18
1 + 2 + 7 = 10
1 + 2 + 6 = 9
1 + 2 + 3 = 6

currentNumber = 2
LP = 3
RP = 15
2 + 3 + 15 = 20
2 + 3 + 7 = 12
2 + 3 + 6 = 11

currentNumber = 3
LP = 7
RP = 15
3 + 6 + 15 = 24
3 + 6 + 7 = 16

currentNumber = 6
LP = 6
RP = 15
3 + 6 + 15 = 24

Complexity Analysis:

• Time Complexity: O(n^2), where N is the length of the input array. It is double loop because:

  • We traverse through array for each number – O(n)
  • In each number, we have LP and RP that traverse through the rest of the element in the array – O(n)

• Space Complexity: O(n) – we create array list to store triplet (array of three numbers)

Kotlin