Two Sum

1# runtime O(n^2)
2# def two_sum(nums: list[int], target: int):
3#     for i in range(0, len(nums) - 1):
4#         for j in range(i + 1, len(nums)):
5#             a = nums[i]
6#             b = nums[j]
7#             if a + b == target:
8#                 return [i, j]
9
10# time O(n)
11# space O(n)  
12def two_sum(nums: list[int], target: int):
13    seen = {}
14    for i in range(len(nums)):
15        difference = target - nums[i]
16        if difference in seen:
17            return [seen[difference], i]
18        seen[nums[i]] = i
19    return [-1, -1]
20
21def test():
22    testcase1 = two_sum([2, 7, 11, 15], 9)
23    assert testcase1[0] == 0
24    assert testcase1[1] == 1
25    assert len(testcase1) == 2
26
27    testcase2 = two_sum([3, 2, 4], 6)
28    assert testcase2[0] == 1
29    assert testcase2[1] == 2
30
31    testcase3 = two_sum([3, 3], 6)
32    assert testcase3[0] == 0
33    assert testcase3[1] == 1
34
35if __name__ == '__main__':
36    test()

1#include <vector>
2#include <cassert>
3#include <map>
4
5using namespace std;
6
7// time O(n^2)
8// space O(1)
9// vector<int> twoSum(vector<int>& nums, int target)
10// {
11//     vector<int> indices = {-1, -1};
12
13//     for (int i = 0; i < nums.size() - 1; i++) {
14//         for (int j = i + 1; j < nums.size(); j++) {
15//             if (nums.at(i) + nums.at(j) == target) {
16//                 indices.at(0) = i;
17//                 indices.at(1) = j;
18//                 return indices;
19//             }
20//         }
21//     }
22
23//     return indices;
24// }
25
26// time O(n)
27// space O(n)
28vector<int> twoSum(vector<int>& nums, int target)
29{
30    vector<int> indices = {-1, -1};
31    map<int, int> seen;
32
33    for (int i = 0; i < nums.size(); i++)
34    {
35        int difference = target - nums.at(i);
36        map<int, int>::iterator it = seen.find(difference);
37        if (it != seen.end()) {
38            indices.at(0) = it->second;
39            indices.at(1) = i;
40            return indices;
41        }
42
43        seen.insert({nums.at(i), i});
44    }
45
46    return indices;
47}
48
49void test()
50{
51    vector<int> nums = {2, 7, 11, 15};
52    auto testcase1 = twoSum(nums, 9);
53    assert(testcase1[0] == 0);
54    assert(testcase1[1] == 1);
55
56    nums.assign({3, 2, 4});
57    auto testcase2 = twoSum(nums, 6);
58    assert(testcase2[0] == 1);
59    assert(testcase2[1] == 2);
60
61    nums.assign({3, 3});
62    auto testcase3 = twoSum(nums, 6);
63    assert(testcase3[0] == 0);
64    assert(testcase3[1] == 1);
65}
66
67int main()
68{
69    test();
70    return 0;
71}

1func twoSum(nums []int, target int) []int {
2	ans := []int{-1, -1}
3	var hashMap map[int]int = make(map[int]int)
4
5	for i, num := range nums {
6		var difference int = target - num
7
8		if index, ok := hashMap[difference]; ok {
9			ans[0] = index
10			ans[1] = i
11			return ans
12		} else {
13			hashMap[num] = i
14		}
15	}
16
17	return ans
18}

1class Solution {
2    public int[] twoSum(int[] nums, int target) {
3        int[] indices = new int[] { -1, -1 };
4        HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
5
6        for (int i = 0; i < nums.length; i++) {
7            int difference = target - nums[i];
8            if (hashMap.containsKey(difference)) {
9                indices[0] = hashMap.get(difference);
10                indices[1] = i;
11                return indices; // or break;
12            }
13            else {
14                hashMap.put(nums[i], i);
15            }
16        }
17
18        return indices;
19    }
20}

1use std::collections::HashMap;
2
3impl Solution {
4    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
5        let mut hashMap = HashMap::new();
6        let mut indices = vec![-1, -1];
7
8        for (i, num) in nums.iter().enumerate() {
9            let diff = target - num;
10            if let Some(&value) = hashMap.get(&diff) {
11                indices[0] = value;
12                indices[1] = i as i32;
13                return indices;
14            }
15            else {
16                hashMap.insert(num, i as i32);
17            }
18        }
19
20        return indices;
21    }
22}

1public class Solution {
2    public int[] TwoSum(int[] nums, int target) {
3        int[] indices = new int[] { -1, -1 };
4        Dictionary<int, int> hashMap = new Dictionary<int, int>();
5
6        for (int i = 0; i < nums.Length; i++) {
7            int difference = target - nums[i];
8            if (hashMap.ContainsKey(difference)) {
9                indices[0] = hashMap[difference];
10                indices[1] = i;
11                break;
12            }
13            else if (!hashMap.ContainsKey(nums[i])) {
14                hashMap.Add(nums[i], i);
15            }
16        }
17
18        return indices;
19    }
20}