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.
To solve this problem, you have to check if two numbers in the array add to the 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:
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:
This code is 99% there, but it's slightly broken - this code allows elements to be added with themselves. *
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:
Here's the code for this. We're using a Set so that looking up elements is fast.
Time Complexity O(n). The for loop takes O(n) time.
Space Complexity 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:
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:
Time Complexity O(n2). We have a double for-loop, which takes O(n2).
Space Complexity O(1).
TreeNode.of
function can be used to create an entire binary tree using 1 line of code. The input is a BFS traversal of the tree including nulls, and the output is the root node of the tree.TreeNode.of([1, None, 2, None, 3])
ListNode.of
function lets you create an entire Linked List using 1 line of code. The input is an array, and the output is the head of the Linked List.ListNode.of([1, 2, 3])
ListNode.of([1, 2, 3], 1)
GraphNode.of
function lets you create an entire Graph using 1 line of code. The input is an Adjacency Matrix, and the output is the first node in the matrix.GraphNode.of([ ['A', 1, 2], ['B', 2], ['C', 0] ])
[['__init__', 15], ['add', 16], ['get']]
c = MyClass(15) c.add(16) c.get()
TreeNode.of
function can be used to create an entire binary tree using 1 line of code. The input is a BFS traversal of the tree including nulls, and the output is the root node of the tree.TreeNode.of([1, None, 2, None, 3])
ListNode.of
function lets you create an entire Linked List using 1 line of code. The input is an array, and the output is the head of the Linked List.ListNode.of([1, 2, 3])
ListNode.of([1, 2, 3], 1)
GraphNode.of
function lets you create an entire Graph using 1 line of code. The input is an Adjacency Matrix, and the output is the first node in the matrix.GraphNode.of([ ['A', 1, 2], ['B', 2], ['C', 0] ])
[['__init__', 15], ['add', 16], ['get']]
c = MyClass(15) c.add(16) c.get()