Two Sum

-----problem-----


Given an array of numbers `arr` and a number `target`, return whether any 2 numbers in the array sum to the target.

The array will contain at least 2 elements.



-----solution-----



To solve this problem, you have to check if two numbers in the array add to the target.

$$
\texttt{a + b = target}
$$


To solve problems like this efficiently, you should always solve for one of the variables using the other variables. We can do this by subtracting `a` from both sides of the equation:


$$
\texttt{b = target - a}
$$

This equation means that the value of `b`  is completely determined by the values of `a` and `target`, because `b = target - a`. This means that you don't have to loop over b. Here's the code to solve the problem:


```
def twoSum(arr, target):

    for a in arr: # only loop over `a`

        b = target - a
        
        # if `b` exists in the array
        # then we know that `a + b = target`
        if b in arr:
            return True

    return False
```

This code is 99% there, but it's slightly broken - this code allows elements to be added with themselves. \detail{For example, if nums=[1, 2] and target=4, the result would be True (since 2+2=4), even though the answer should really be False.}



To fix this, you can make it so that b is always a different element from a. To do this, you can keep track of all the elements you've seen so far as you walk, and only search for `b` in all the previous elements you've seen. Here's a visual of this:

\image{1, 140}


Here's the code for this. We're using a Set so that looking up elements is fast.
\answer


\tc $O(n)$. The for loop takes $O(n)$ time. 


\sc $O(n)$. We have to store a set with all the numbers in it.





Here's the brute-force solution you might have started with, although it's suboptimal:

\spoiler{


To solve this problem, you could loop over all possible numbers `a` and `b` and check if they add to the target, but this is very inefficient. Here's the code:


```

def twoSum(arr, target):
    for i in range(len(arr)):
        for j in range(i+1, len(arr)): # j greater than i

            # return True if numbers add to target
            if arr[i] + arr[j] == target:
                return True

    return False

```

\tc $O(n^2)$. We have a double for-loop, which takes $O(n^2)$.

\sc $O(1)$.


}







Iteration

Two Sum