/**
 * Given an array of integers, find two numbers such that they add up to a specific target numbers.
 * The function twoSum should return indices of the two numbers such that they add up to the target,
 * where index1 must be less than index2. Please note that your returned answers(both index1 and index2)
 * are not zero-based.
 *
 * You may assume that each input would have exactly one solution.
 *
 * Input: 2, 7, 11, 15     9
 * Output: 1, 2
 * Idea: (1) 方法1，两个循环，复杂度O(n2)
 *       (2) 方法2，空间换时间，用hashmap来缓存数据，复杂度O(n)
 */
fun twoSum(array: Array<Int>, target: Int) : Array<Int> {
    if (array.size < 2) {
        return arrayOf(0, 0)
    }

    val map = hashMapOf<Int, Int>()
    for (i in 0 until array.size) {
        if (map.contains(array[i])) {
            return arrayOf(map[array[i]]!! + 1, i + 1)
        } else {
            map[target - array[i]] = i
        }
    }
    return arrayOf(0, 0)
}