An O(n) solution for two sum problem

_readme.md

Code Challenge: Two Number Sum

Write a function that takes in a non empty array of distinct integers and an integer representing a target sum. If any two numbers in the input array sum up to the target sum, the function should return them in an array. If no two numbers sum up to the target sum, the function should return an empty array. Assume that there will be at most one pair of numbers summing up to the target sum.

Solution: O(n)

def get_pair(array, target):
    hash = {}
    for x in array:
        if ((target-x) in hash) and (target-x) != x:
            return [target-x, x]
        hash[x] = True
    return []

Testcases:

These are in cases.json file, this file containt an array structure

[
    CASE,
    ...
]

Which CASE represent an array with the following values: the values array, the target number and the expected function output, in this order.

[
    [3,5,-4,8,11,1,-1,6],
    10,
    [-1,11]
]

How to run tests:

Just run python test.py

cases.json

[
    [
        [3,5,-4,8,11,1,-1,6],
        10,
        [11, -1]
    ],
    [
        [2,-7,4,8,-11],
        56,
        []
    ],
    [
        [303, 318, 16, 436, 322, 60, 260, 29, 33, 111, 227, 47, 388, 420, 465, 5, 469, 147, 255, 123, 405, 366, 483, 69, 291, 42, 37, 259, 479, 437, 66, 155, 390, 88, 356, 63, 133, 394, 379, 433, 490, 193, 138, 195, 472, 14, 393, 397, 143, 385],
        274,
        [227, 47]
    ],
    [
        [490, 252, 609, 114, 940, 879, 230, 804, 397, 437, 350, 203, 906, 330, 605, 991, 404, 865, 145, 405, 192, 611, 765, 61, 356, 767, 486, 883, 438, 660, 74, 376, 401, 243, 345, 435, 960, 864, 107, 557, 622, 861, 627, 110, 896, 362, 443, 754, 756, 601, 403, 410, 592, 718, 639, 97, 87, 228, 677, 518, 824, 440, 236, 158, 951, 776, 656, 62, 931, 117, 2, 959, 93, 304, 635, 852, 337, 202, 908, 213, 973, 521, 551, 247, 379, 591, 325, 674, 733, 683, 79, 496, 487, 643, 812, 665, 229, 721, 367, 386],
        1112,
        [767, 345]
    ],
    [
        [3558, 8697, 5527, 9035, 3882, 4924, 2836, 4749, 4191, 4025, 3448, 3340, 3682, 95, 127, 873, 4249, 3703, 688, 1424, 8045, 8482, 7232, 3750, 7642, 645, 4453, 7312, 2217, 5797, 5474, 6664, 376, 3186, 8168, 9085, 6359, 8624, 8732, 799, 9878, 8925, 9168, 8784, 879, 1387, 5951, 7563, 4130, 6323, 5151, 558, 829, 8512, 2223, 500, 6918, 4302, 831, 203, 2844, 8037, 3019, 7481, 3879, 3499, 8790, 421, 9028, 5547, 5596, 8390, 5039, 3469, 4198, 3209, 8058, 9086, 6709, 27, 4887, 3226, 8967, 2072, 7233, 7351, 5410, 6484, 9625, 3367, 2911, 7914, 5188, 8585, 8941, 833, 7066, 3168, 5371, 4829, 8606, 1356, 1468, 8184, 5867, 1799, 1266, 5655, 8486, 1322, 9203, 802, 3727, 4097, 5886, 1061, 4533, 9752, 1695, 2013, 2573, 1316, 9199, 5154, 7013, 8564, 6097, 8323, 4395, 8705, 9575, 6789, 2717, 162, 1670, 2553, 4724, 7944, 6126, 251, 3821, 7498, 7525, 1871, 7357, 8771, 4361, 8137, 73, 4192, 5495, 8828, 136, 2700, 599, 3066, 7463, 4581, 8151, 4437, 1377, 5112, 8947, 3147, 5593, 1990, 3859, 3212, 966, 592, 5328, 8965, 9828, 3554, 527, 677, 2672, 1311, 1522, 5501, 3478, 4385, 1390, 2122, 5413, 1422, 7198, 4794, 5455, 7445, 6431, 1415, 2912, 2812, 2500, 8158, 7556, 3029, 4187, 9112, 985, 9320, 6059, 6451, 1278, 3111, 4409, 3139, 6566, 1948, 7077, 931, 3127, 4583, 2133, 8871, 4141, 8082, 7612, 5556, 1668, 4052, 8007, 6, 8628, 582, 2093, 3485, 8873, 9353, 2455, 8304, 4578, 6908, 3069, 7222, 2029, 2618, 4640, 248, 7247, 9726, 9954, 9506, 7208, 8626, 9300, 5827, 9151, 1438, 3174, 50, 901, 9222, 369, 2531, 486, 963, 4393, 1705, 7534, 1649, 1425, 5113, 6970, 7267, 8177, 6802, 4828, 7162, 1782, 1931, 1811, 3284, 8572, 667, 8494, 524, 4371, 2842, 265, 5361, 885, 529, 1981, 2691, 8882, 4140, 3088, 7248, 7149, 3277, 1432, 6401, 7956, 2838, 6309, 4693, 1466, 3023, 8077, 7680, 1335, 2229, 3798, 2308, 7970, 6134, 9868, 9833, 9413, 467, 9527, 4115, 3856, 6394, 2704, 1078, 1617, 734, 5374, 9056, 5634, 2642, 4184, 711, 5064, 1529, 8361, 184, 7308, 1164, 9057, 9034, 1590, 7932, 2630, 1784, 4061, 2886, 6297, 8647, 9906, 226, 7277, 3984, 2707, 2664, 2580, 5313, 2909, 9685, 612, 2042, 555, 6554, 8294, 2076, 8915, 6452, 7168, 3477, 1095, 3230, 9851, 3386, 1052, 7432, 80, 8750, 7885, 5302, 533, 4377, 2882, 624, 2870, 6045, 6501, 2254, 2787, 6138, 7137, 5105, 5058, 8858, 6537, 6809, 2146, 2183, 4994, 8926, 8620, 8423, 3641, 4428, 8201, 4440, 2998, 3460, 4037, 195, 1679, 2096, 6932, 5473, 6567, 1735, 7468, 9063, 8617, 4564, 669, 2584, 6021, 9779, 4468, 7728, 1072, 8754, 5570, 6124, 3512, 4095, 1035, 1975, 1714, 3343, 2414, 1017, 3963, 1870, 3332, 6544, 2451, 9231, 9877, 3578, 4011, 4932, 4131, 5715, 7226, 1404, 9535, 6594, 2733, 9948, 7657, 7390, 9751, 3867, 7669, 7630, 9916, 9003, 1561, 9007, 145, 3329, 4895, 4415, 2698, 1385, 4513, 7424, 8991, 8533, 2527, 587, 3056, 5045, 8349, 8792, 654, 1651, 2819, 6514, 9450, 242, 3598, 1469, 9127, 3650, 9487, 3956, 7542, 5581, 7692, 2561, 1134, 7161, 9091, 6633, 5164, 4632, 1575, 1899, 5120, 5176, 9137, 4782, 2049, 1674, 9354, 6690, 4968, 2596, 7732, 8407, 7420, 5127, 8085, 3986, 4196, 7801, 7823, 8164, 8888, 8854, 5499, 7216, 7696, 196, 8860, 6418, 6063, 761, 887, 7299, 4604, 1188, 6110, 6917, 4647, 8850, 4357, 365, 5087, 4919, 2483, 6890, 512, 4178, 1320, 2446, 4172, 8193, 6332, 7108, 6428, 3192, 1275, 462, 4023, 3085, 2876, 1453, 437, 1887, 8261, 5504, 2811, 7284, 8709, 8872, 8575, 8596, 8291, 435, 7416, 6836, 7043, 5693, 3614, 5159, 5118, 1627, 7071, 1809, 6844, 189, 4276, 8379, 5008, 4608, 4216, 6873, 6482, 2418, 3530, 8046, 4993, 7842, 9391, 4009, 3876, 4404, 6105, 2484, 4354, 6645, 4148, 5356, 6067, 8768, 8404, 7181, 1139, 6723, 3080, 9772, 1177, 3957, 2382, 7599, 447, 254, 6921, 528, 8649, 3159, 4891, 3863, 3519, 6125, 8983, 4557, 8031, 9696, 123, 2220, 8478, 4785, 9293, 5564, 1928, 628, 6358, 1751, 8053, 7435, 3511, 9887, 3884, 4341, 7341, 4432, 1595, 216, 602, 7541, 4680, 7996, 6685, 2463, 5114, 3055, 2932, 6308, 9817, 8267, 9362, 4789, 7007, 8922, 8511, 3497, 1932, 8751, 5945, 618, 9960, 6252, 7021, 1131, 5716, 2617, 3097, 5149, 2091, 7993, 6030, 9309, 888, 741, 5239, 1536, 5640, 5712, 7713, 8287, 9615, 7064, 2402, 7693, 2196, 1119, 4304, 2850, 7377, 5583, 4212, 4910, 98, 7320, 2931, 124, 2713, 5739, 9136, 8614, 4863, 579, 4247, 158, 5314, 1841, 1541, 9160, 2367, 9818, 4345, 1712, 8973, 6203, 6165, 4074, 8508, 1555, 9073, 719, 3151, 641, 279, 7945, 872, 5893, 6821, 2830, 478, 2791, 4816, 6949, 790, 4358, 442, 773, 5163, 6540, 8590, 488, 5507, 1875, 3416, 3621, 4729, 8760, 6423, 5649, 3094, 7257, 380, 9955, 7584, 9226, 6924, 4334, 4379, 1656, 6106, 1409, 7118, 4719, 4521, 4942, 7814, 165, 8794, 7212, 7790, 7769, 3940, 3906, 2641, 6804, 4040, 7919, 7386, 999, 2064, 3050, 7908, 14, 6696, 2175, 9197, 7760, 6147, 26, 2173, 8874, 3422, 8913, 5962, 3206, 132, 7229, 4222, 2453, 9743, 8080, 2693, 3979, 874, 3586, 4258, 6524, 1306, 7955, 7798, 4287, 557, 5293, 9072, 344, 8018, 9842, 5848, 6825, 2250, 4612, 5534, 4261, 1812, 2235, 699, 1867, 5317, 2510, 7638, 5441, 1760, 8838, 5816, 3335, 4771, 7786, 8974, 867, 1693, 1713, 9060, 4412, 8331, 4621, 8153, 5487, 4972, 9518, 5696, 7736, 7509, 6700, 5365, 8708, 8243, 1037, 1564, 3851, 1122, 6689, 8189, 6219, 865, 3716, 4252, 2444, 2199, 7093, 7577, 6099, 794, 6713, 9373, 1344, 3418, 6528, 9786, 866, 2740, 6088, 9548, 3241, 1667, 9287, 7626, 4469, 5160, 3962, 1121, 3637, 1815, 737, 5566, 6601, 7653, 7652, 724, 2721, 5967, 7927, 9554, 4080, 9110, 5419, 7057, 5309, 8963, 1852, 2815, 489, 8502, 8692, 3453, 7200, 4667, 3923, 424, 367, 6002, 3210, 1039, 6107, 6773, 3215, 3228, 2834, 5796, 8448, 8154, 3772, 4595, 5978, 9979, 39, 5692, 1757, 7182, 929, 7392, 9602, 4799, 8387, 4544, 9369, 2086, 3369, 9317, 1669, 7, 2392, 2795, 7366, 6460, 3527, 7448, 1960, 4804, 4531, 357, 6748, 8583, 4166, 9043, 5066, 9863, 8217, 9220, 9520, 8943, 1338, 3814, 9096, 8237, 8141, 4618, 3419, 9246, 267, 5841, 923, 1526, 4776, 9357, 5997, 1636, 3684, 1797, 6569],
        6501,
        [6451, 50]
    ]

]

test.py

import json
import unittest
from two_numbers import get_pair

class TestStringMethods(unittest.TestCase):

    def setUp(self):
        self.cases_file = open ('cases.json')
        self.cases = json.load(self.cases_file)

    def test_valid_pair(self):
        for i, case in enumerate(self.cases):
            array = case[0]
            target = case[1]
            expected = case[2]
            result = get_pair(array, target)

            with self.subTest(f"case {i}"):
                self.assertEqual(expected, result)

if __name__ == '__main__':
    unittest.main()

two_numbers.py

def get_pair(array, target):
    hash = {}
    for x in array: 
        if ((target-x) in hash) and (target-x) != x:
            return [target-x, x]
        hash[x] = True
    return []