1. Two Sum

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.

//

var twoSum = function (nums, target) {
  var map = {}
}

//

function twoSum(nums: number[], target: number): number[] {
  var map = {}
}

// Despite the fact we're guaranteed to have at least one pair
// which sums to target, we must hardcode a return type in Dart.

// The Dart compiler will complain if we don't.
// "A non-null value must be returned since the return type 'List<int>'
// doesn't allow null"

class Solution {
  List<int> twoSum(List<int> nums, int target) {
    var hm = {};
    return [0, 0]
  }
}

// In Java we must declare and return a Array, result in this case.
// This is because of Java being strongly typed.

class Solution {
  public int[] twoSum(int[] nums, int target) {
    int[] result = new int[2];
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();

    return result;
  }
}

# Python depends on indentation.
# Python doesn't use curly braces for it's codeblocks like all the other languages.

class Solution:
  def twoSum(self, nums: List[int], target: int) -> List[int]:
    hashMap = {}

//

func twoSum(nums []int, target int) []int {
  dict := make(map[int]int)
  return make([]int, 0, 0)
}

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.

var twoSum = function (nums, target) {
  var map = {}
  for(let i = 0; i < nums.length; i++) {
    let num = nums[i]
    let diff = target - num

    map.set(num, i)
  }
}

//

function twoSum(nums: number[], target: number): number[] {
  var map = {}
  for (let i = 0; i < nums.length; i++) {
    const num = nums[i]
    const diff = target - num
    if (map.has(num)){
      return [map.get(num), i]
    }
    map.set(diff, i)
  }
}

class Solution {
  List<int> twoSum(List<int> nums, int target) {
    var hm = {};

    for (var i = 0; i < nums.length; i++) {
        var num = nums[i];
        var diff = target - num;

        hm[num] = i;
    }
    return [];
  }
}

class Solution {
  public int[] twoSum(int[] nums, int target) {
    int[] result = new int[2];
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int i = 0; i < nums.length; i++) {

      map.put(nums[i], i);
    }
    return result;
  }
}

class Solution:
  def twoSum(self, nums: List[int], target: int) -> List[int]:
    hashMap = {}

    for i, num in enumerate(nums):
      diff = target - num

      hashMap[num] = i

//

func twoSum(nums []int, target int) []int {
  dict := make(map[int]int)
  for idx, num := range nums {
    diff := target - num

    dict[num] = idx
  }
  return make([]int, 0, 0)
}

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.

var twoSum = function (nums, target) {
  var map = {}
  for(let i = 0; i < nums.length; i++) {
    let num = nums[i]
    let diff = target - num
    if (map.has(diff)) {
      return [i, map.get(diff)]
    }
    map.set(num, i)
  }
}

//

function twoSum(nums: number[], target: number): number[] {
  var map = {}
  for (let i = 0; i < nums.length; i++) {
    const num = nums[i]
    const diff = target - num
    if (map.has(num)){
      return [map.get(num), i]
    }
    map.set(diff, i)
  }
}

class Solution {
  List<int> twoSum(List<int> nums, int target) {
    var hm = {};

    for (var i = 0; i < nums.length; i++) {
        var num = nums[i];
        var diff = target - num;
        if (hm[diff] != null) return [i, hm[diff]];
        hm[num] = i;
    }
    return [];
  }
}

class Solution {
  public int[] twoSum(int[] nums, int target) {
    int[] result = new int[2];
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int i = 0; i < nums.length; i++) {
      if (map.containsKey(target - nums[i])) {
        result[0] = map.get(target - nums[i]);
        result[1] = i;
        return result;
      }
      map.put(nums[i], i);
    }
    return result;
  }
}

class Solution:
  def twoSum(self, nums: List[int], target: int) -> List[int]:
    hashMap = {}

    for i, num in enumerate(nums):
      diff = target - num

      if diff in hashMap:
        return [hashMap[diff], i]

      hashMap[num] = i

//

func twoSum(nums []int, target int) []int {
  dict := make(map[int]int)
  for idx, num := range nums {
    diff := target - num
    if _, ok := dict[diff]; ok {
      return []int{dict[diff], idx}
    }
    dict[num] = idx
  }
  return make([]int, 0, 0)
}

Questions? Concerns?

Please comment a better solution if you have one.