<jupyter_start><jupyter_text>This notebook was prepared by [<NAME>](https://github.com/donnemartin). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges).  Solution Notebook  Problem: Given an array, find the two indices that sum to a specific value.* [Constraints](Constraints)* [Test Cases](Test-Cases)* [Algorithm](Algorithm)* [Code](Code)* [Unit Test](Unit-Test)  Constraints* Is there exactly one solution?    * Yes* Is there always a solution?    * Yes* Is the array an array of ints?    * Yes* Is the array sorted?    No* Are negative values possible?    * Yes* Can we assume the inputs are valid?    * No* Can we assume this fits memory?    * Yes  Test Cases* None input -> TypeError* [] -> ValueError* [1, 3, 2, -7, 5], 7 -> [2, 4]  Algorithm Brute force* For i in range(len(input)):    * For j in range(i+1, len(input)):        * if i + j == target return True* return FalseComplexity:* Time: O(n^2)* Space: O(1) Optimized* Loop through each num in nums    * Calculate the cache_target = target - numtarget = 7index  =  0  1  2   3  4nums   = [1, 3, 2, -7, 5]          ^cache_target = 7 - 1 = 6cache6 -> 01 not in cacheindex  =  0  1  2   3  4nums   = [1, 3, 2, -7, 5]             ^cache_target = 7 - 3 = 4cache6 -> 04 -> 13 not in cacheindex  =  0  1  2   3  4nums   = [1, 3, 2, -7, 5]                ^cache_target = 7 - 2 = 5cache6 -> 04 -> 15 -> 22 not in cacheindex  =  0  1  2   3  4nums   = [1, 3, 2, -7, 5]                    ^cache_target = 7 + 7 = 14cache6  -> 04  -> 15  -> 214 -> 3-7 not in cacheindex  =  0  1  2   3  4nums   = [1, 3, 2, -7, 5]                       ^cache_target = 7 - 5 = 2cache6  -> 04  -> 15  -> 214 -> 35 in cache, success, output matching indices: cache[num] and current iteration indexoutput = [2, 4]Complexity:* Time: O(n)* Space: O(n)  Code<jupyter_code>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<jupyter_output><empty_output><jupyter_text>Unit Test<jupyter_code>%%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()
%run -i test_two_sum.py<jupyter_output>Success: test_two_sum
{'fraction_non_alphanumeric': 0.12248266754704523, 'fraction_numerical': 0.040937603169362825, 'mean_word_length': 2.51508120649652, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 26, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '103012', 'license': 'Apache-2.0', 'n_tokens_mistral': 1079, 'n_tokens_neox': 984, 'n_words': 344, 'path': 'arrays_strings/two_sum/two_sum_solution.ipynb', 'repo_name': 'rampup01/interactive-coding-challenges', 'size': '3035'}