LeetCode: 1. Two Sum

Description

Given an array of numbers and a target, return the indices of two numbers such that they sum to target.

Solution

Use a hashmap to store the values we're looking for. We can identify which numbers we're looking for by subtracting target - num iteratively as we loop over the numbers we're given.

Declare Hashmap

We'll add keys to this hashmap as we loop over the items in our numbers array. Each key will be a number which we're looking for and it's value will be it's index.

1var twoSum = function (nums, target) {
2  var map = {}
3}
1function twoSum(nums: number[], target: number): number[] {
2  var map = {}
3}
1class Solution {
2  List<int> twoSum(List<int> nums, int target) {
3    var hm = {};
4    return [0, 0]
5  }
6}
1class Solution {
2  public int[] twoSum(int[] nums, int target) {
3    int[] result = new int[2];
4    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
5 
6    return result;
7  }
8}
1class Solution:
2  def twoSum(self, nums: List[int], target: int) -> List[int]:
3    hashMap = {}
1func twoSum(nums []int, target int) []int {
2  dict := make(map[int]int)
3  return make([]int, 0, 0)
4}

Loop over numbers

We loop over the input nums and use the current item to calculate sought numbers, the difference between target and current number.

The formula target - num determines which number we need next, the pair to this number which would sum to target.

Store this number, diff in the hashmap and the current index as it's value.

1var twoSum = function (nums, target) {
2  var map = {}
3  for(let i = 0; i < nums.length; i++) {
4    let num = nums[i]
5    let diff = target - num
6 
7    map.set(num, i)
8  }
9}
1function twoSum(nums: number[], target: number): number[] {
2  var map = {}
3  for (let i = 0; i < nums.length; i++) {
4    const num = nums[i]
5    const diff = target - num
6    if (map.has(num)){
7      return [map.get(num), i]
8    }
9    map.set(diff, i)
10  }
11}
1class Solution {
2  List<int> twoSum(List<int> nums, int target) {
3    var hm = {};
4 
5    for (var i = 0; i < nums.length; i++) {
6        var num = nums[i];
7        var diff = target - num;
8 
9        hm[num] = i;
10    }
11    return [];
12  }
13}
1class Solution {
2  public int[] twoSum(int[] nums, int target) {
3    int[] result = new int[2];
4    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
5    for (int i = 0; i < nums.length; i++) {
6 
7      map.put(nums[i], i);
8    }
9    return result;
10  }
11}
1class Solution:
2  def twoSum(self, nums: List[int], target: int) -> List[int]:
3    hashMap = {}
4 
5    for i, num in enumerate(nums):
6      diff = target - num
7 
8      hashMap[num] = i
1func twoSum(nums []int, target int) []int {
2  dict := make(map[int]int)
3  for idx, num := range nums {
4    diff := target - num
5 
6    dict[num] = idx
7  }
8  return make([]int, 0, 0)
9}

Check for diff in hashmap

To complete the algorithm we check if the difference exists in the hashmap. If it does, we return the current index, and the value of that key in the hashmap.

1var twoSum = function (nums, target) {
2  var map = {}
3  for(let i = 0; i < nums.length; i++) {
4    let num = nums[i]
5    let diff = target - num
6    if (map.has(diff)) {
7      return [i, map.get(diff)]
8    }
9    map.set(num, i)
10  }
11}
1function twoSum(nums: number[], target: number): number[] {
2  var map = {}
3  for (let i = 0; i < nums.length; i++) {
4    const num = nums[i]
5    const diff = target - num
6    if (map.has(num)){
7      return [map.get(num), i]
8    }
9    map.set(diff, i)
10  }
11}
1class Solution {
2  List<int> twoSum(List<int> nums, int target) {
3    var hm = {};
4 
5    for (var i = 0; i < nums.length; i++) {
6        var num = nums[i];
7        var diff = target - num;
8        if (hm[diff] != null) return [i, hm[diff]];
9        hm[num] = i;
10    }
11    return [];
12  }
13}
1class Solution {
2  public int[] twoSum(int[] nums, int target) {
3    int[] result = new int[2];
4    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
5    for (int i = 0; i < nums.length; i++) {
6      if (map.containsKey(target - nums[i])) {
7        result[0] = map.get(target - nums[i]);
8        result[1] = i;
9        return result;
10      }
11      map.put(nums[i], i);
12    }
13    return result;
14  }
15}
1class Solution:
2  def twoSum(self, nums: List[int], target: int) -> List[int]:
3    hashMap = {}
4 
5    for i, num in enumerate(nums):
6      diff = target - num
7 
8      if diff in hashMap:
9        return [hashMap[diff], i]
10 
11      hashMap[num] = i
1func twoSum(nums []int, target int) []int {
2  dict := make(map[int]int)
3  for idx, num := range nums {
4    diff := target - num
5    if _, ok := dict[diff]; ok {
6      return []int{dict[diff], idx}
7    }
8    dict[num] = idx
9  }
10  return make([]int, 0, 0)
11}

Questions? Concerns?

Please comment a better solution if you have one.