This notebook was prepared by Donne Martin. Source and license info is on GitHub.
Complexity:
* Loop through each num in nums * Calculate the cache_target = target - num target = 7 index = 0 1 2 3 4 nums = [1, 3, 2, -7, 5] ^ cache_target = 7 - 1 = 6 cache 6 -> 0 1 not in cache index = 0 1 2 3 4 nums = [1, 3, 2, -7, 5] ^ cache_target = 7 - 3 = 4 cache 6 -> 0 4 -> 1 3 not in cache index = 0 1 2 3 4 nums = [1, 3, 2, -7, 5] ^ cache_target = 7 - 2 = 5 cache 6 -> 0 4 -> 1 5 -> 2 2 not in cache index = 0 1 2 3 4 nums = [1, 3, 2, -7, 5] ^ cache_target = 7 + 7 = 14 cache 6 -> 0 4 -> 1 5 -> 2 14 -> 3 -7 not in cache index = 0 1 2 3 4 nums = [1, 3, 2, -7, 5] ^ cache_target = 7 - 5 = 2 cache 6 -> 0 4 -> 1 5 -> 2 14 -> 3 5 in cache, success, output matching indices: cache[num] and current iteration index output = [2, 4]
Complexity:
class Solution(object):
def two_sum(self, nums, target):
if nums is None or target is None:
raise TypeError('nums or target cannot be None')
if not nums:
raise ValueError('nums cannot be empty')
cache = {}
for index, num in enumerate(nums):
cache_target = target - num
if num in cache:
return [cache[num], index]
else:
cache[cache_target] = index
return None
%%writefile test_two_sum.py
import unittest
class TestTwoSum(unittest.TestCase):
def test_two_sum(self):
solution = Solution()
self.assertRaises(TypeError, solution.two_sum, None, None)
self.assertRaises(ValueError, solution.two_sum, [], 0)
target = 7
nums = [1, 3, 2, -7, 5]
expected = [2, 4]
self.assertEqual(solution.two_sum(nums, target), expected)
print('Success: test_two_sum')
def main():
test = TestTwoSum()
test.test_two_sum()
if __name__ == '__main__':
main()
Overwriting test_two_sum.py
%run -i test_two_sum.py
Success: test_two_sum