The 3Sum problem is often asked during technical interviews and the problem at first seems quite tough but it’s got a pretty similar taste to 2Sum problem.

Here is the problem: You are given a sorted array, and you need to find three numbers in the array that can add up to a particular sum which is also given to you. I would strongly urge everyone to first try solving the 2Sum problem where it requires you to find 2 numbers that add up to give you the given sum and similarly practice this problem before continuing to the solution given below. 

So first lets start with function signature:

func threeSumProblem(for array: \[Int\], sum: Int) -> Bool

The function takes in the sorted array of type Int and a Sum integer and returns a Bool.

func threeSumProblem(for array: \[Int\], sum: Int) -> Bool
    {
        var complement = 0
        var lowIndex = 0
        var highIndex = array.count - 1

Firstly, I am initializing three variables - _complement, lowIndex & highIndex._To solve the 3Sum problem here is the method I am using:  If the array is say \[1,4,6,4\] and sum is 11, then we will first hold on to first number which in this case is 1, and then using linear pointer method on the remaining array \[4,6,4\]. Here we will have a pointer which will start from 4 with one index more than the number we holding on to, and the high pointer will start with index of array.count - 1. (The right hand side)

for (index, element) in array.enumerated() {
            lowIndex = index + 1
            complement = sum - element
            while (lowIndex < highIndex)
                { if (array\[lowIndex\] + array\[highIndex\] > complement ) {
                    highIndex -= 1
                }else if (array\[lowIndex\] + array\[highIndex\] < complement) {
                    lowIndex += 1
                }else {
                    print(element, array\[lowIndex\], array\[highIndex\])
                    return true
                }
            }           
             lowIndex = 0
             highIndex = array.count - 1          
        }

Next, we will start a for loop which will give us the element and the _index of that element in the sequence, hence using array.enumerated() Then inside the for loop, I am setting lowIndex to current index + 1. We also set complement by subtracting the current element we are on with the sum passed in the function by the user.

Then we have another loop inside this for loop. This time it’s a while loop. The while loop will keep running until the two pointers cross over.

Inside the while loop, we have three if statements:

 if (array\[lowIndex\] + array\[highIndex\] > complement ) {
                    highIndex -= 1
                }else if (array\[lowIndex\] + array\[highIndex\] < complement) {
                    lowIndex += 1
                }else {
                    print(element, array\[lowIndex\], array\[highIndex\])
                    return true
                }

Now the problem has been converted in to 2sum. We will check if the two numbers sum is greater than complement, if yes, then move the highIndex pointer by 1 to the left. Similarly, if the sum of two numbers is less than the complement, then move the lowIndex pointer by 1 to the right. Else, if the sum of two numbers is equal to complement, then return true.

After this if statement, we are setting the lowIndex and highIndex back to 0 and array.count - 1.

Next call this function:

let array = \[4,3,5,1,5\]
print(threeSumProblem(for: array, sum: 14))

The output for this is:

//output
4 5 5
true

This is how you can solve this algorithm. This particular solution is O(n^2) mainly as we are using two nested loops.