Question:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

1
2
3
4

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Analysis:
This one is a very classical quiz. You can do an O(n) runtime complexity to solve this problem with an O(n) space complexity. Let’s see how to do it:

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
  fun twoSum(nums: IntArray, target: Int): IntArray {
    val result = hashMapOf<Int, Int>()
    nums.forEachIndexed { index, number ->
      if (result.containsKey(target - number)) {
        return intArrayOf(index, result.get(target - number)!!)
      }
    }
    result.put(number, index)
    return intArrayOf()
  }
}

We can create a hash map to put all numbers and their indices. If there is a number that exists in the hash map and it equals target minus current iterated number, then we found the possible pair in the integer array.

Can we solve this problem without any data structure? Yes, we can. We need to have two indices and sort this array in ascending order. You can think about how to solve it :)