Skip to main content

1. Two Sum

https://leetcode.com/problems/two-sum

Python​

Brute Force​

  • Time: O(N^2)
  • Space: O(1)
def two_sum(self, nums: List[int], target: int) -> List[int]:
    for i in range(0, len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

    return False

Prefix Mapper with dict​

  • Time: O(N)
  • Space: O(N)
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        memory = {num: index for index, num in enumerate(nums)}

        for index, num in enumerate(nums):
            other = target - num
            if other in memory and memory[other] != index:
                return [memory[other], index] if memory[other] < index else [index, memory[other]]

Go​

func twoSum(nums []int, target int) []int {
    for i:=0; i<len(nums)-1; i++ {
        for j:=i+1; j<len(nums); j++ {
            if (nums[i] + nums[j] == target) {
                return []int{i, j}
            }
        }
    }
    return []int{}
}

Rust​

Prefix Mapper​

use std::collections::HashMap;


impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut mapper: HashMap<i32, usize> = HashMap::new();
        for (i, num) in nums.iter().enumerate() {
            mapper.insert(*num, i);
        }

        for (i, num) in nums.iter().enumerate() {
            let other = target - num;
            if mapper.contains_key(&other) && mapper.get(&other).unwrap() != &i {
                return vec![i as i32, *mapper.get(&other).unwrap() as i32];
            }
        }

        panic!("not possible")
    }
}