Two Sum (Medium)
Good morning! Here's our prompt for today.
You may see this problem at Amazon, Autodesk, Vmware, Adobe, Paypal, Snap, Intercom, Tesla, Rubrik, Segment, Automattic, Grammarly, Intel, and Coupa.
This is a classic and very common interview problem. Given an array of integers, return the indices of the two numbers in it that add up to a specific "goal" number.
Suppose we had an array [1, 3, 6, 7, 9], and let's say our "goal" number was 10. Our numbers to sum to it could be 3 and 7, and we would return an array of indices 1 and 3 respectively.
1arr = [1, 3, 6, 7, 9]
2goal = 10
3two_sum(arr, goal)
4# [1, 3]You may assume that each input would have exactly one solution. Additionally, you may not use the same element twice towards the sum. This means if given [1, 3] and a goal of 2, you cannot use 1 twice and return its index twice as [0, 0].
Note that you cannot guarantee the array is sorted.
AlgoDaily partner CodeTips.co.uk has kindly provided a guide on solving Two Sum in Go. Check it out for even deeper coverage of this problem.
Constraints
- Length of the array <=
100000 - The values of the array will be between
-1000000000and1000000000 - The array can be empty
- The target sum will be between
-1000000000and1000000000 - Expected time complexity :
O(n) - Expected space complexity :
O(n)
xxxxxxxxxxdef two_sum(nums, goal): # fill in return []import unittestclass Test(unittest.TestCase): def test_1(self): assert two_sum([1, 9, 13, 20, 47], 10) == [0, 1] print("PASSED: assert two_sum([1, 9, 13, 20, 47], 10) == [0, 1]") def test_2(self): assert two_sum([3, 2, 4, 1, 9], 12) == [0, 4] print("PASSED: assert two_sum([3, 2, 4, 1, 9], 12) == [0, 4]") def test_3(self): assert two_sum([], 10) == [] print("PASSED: assert two_sum([], 10) == []")if __name__ == "__main__": unittest.main(verbosity=2) print("Nice job, 3/3 tests passed!")