# Three Sum

Given an array of integers arr and a target number target, return whether 3 of the numbers in the array sum to the target.

The array will contain at least 3 elements.

First Few Test Cases:

This problem asks you to find 3 numbers that sum to the target.

$\notag \large \texttt{a + b + c = target}$

To do this, you can loop over all possible indexes in the array, and check if they add to the target. To avoid duplicate values, you can make sure the indexes you use are in increasing order i < j < k:

Here's the code:

This solution works, but it's very inefficient. To optimize solutions like this, you should write one of the variables using the other variables. You can subtract a and b from both sides of the equation, like this:

$\notag \large \texttt{c = target - a - b}$

This equation tells you that the value of c is completely determined by the values of a and b. This is because c = target - a - b. This means you can eliminate the for-loop over $\tt c$, since you already know what $\tt c$ is equal to. Here's the code for this:

This code is 99% there, but it's slightly broken - it allows elements to be added with themselves. For example, if nums=[1, 2, 10] and target=3, the result would be True (since 1+1+2=4), even though the answer should really be False. When we look up c in arr we need to make sure c is different from a and b.

To fix this, you can make it so that you only lookup values of c that are to the left of a and b. This makes it so that c is not equal to a or b.

Here's how you code this up:

Time Complexity $O(n^2)$. The loop takes O(n) * O(n) * O(1) = O(n$^2$) time.

Time Complexity $O(n)$, we store a Set with $n$ elements.

Mark as Completed:
Submits:
threeSum
Test your code to get an output here!
threeSum(
)
Test your code to get an output here!