LeetCode 1. Two Sum

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:

Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,return [0,1].

翻译：

给定一个整数数组，返回两个数的索引，使它们的和为一个目标值。
你可以假设每个输入都只有一个答案，且一个元素只能使用一次。

Solution 1: 双重循环

使用双重循环，遍历所有的情况，时间复杂度为 O(n^2) 。
在内层的循环中，索引从 i + 1 开始。

//Kotlin
class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        for (i in 0..(nums.size - 1))
            for (j in (i + 1)..(nums.size - 1))
                if (nums[i] + nums[j] == target)
                    return intArrayOf(i, j)
        return intArrayOf()
    }
}

Solution 1.1:

对上面的代码做一些小小的优化，在第一重循环中计算另一个数的值，可以减少加减计算次数。时间复杂度仍为 O(n^2) 。

//Kotlin
class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        for (i in 0..(nums.size - 1)) {
            val remain = target - nums[i]
            for (j in (i + 1)..(nums.size - 1))
                if (nums[j] == remain)
                    return intArrayOf(i, j)
        }
        return intArrayOf()
    }
}

Solution 2:

另一种方法是对于已经排序的数组，从两端向中间查找。
将数组从小到大排序，两个索引分别为数组的第一个和最后一个元素，如果两个值的大于目标值，第二个索引减1，反之第一个索引加1，直到两个数的和为目标值。

//Kotlin
class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val ns = nums.mapIndexed { index, i -> Pair(index, i) }.sortedBy { p -> p.second }
        var a = 0
        var b = ns.size - 1
        while (a != b) {
            val sum = ns[a].second + ns[b].second
            when {
                sum == target -> return intArrayOf(ns[a].first, ns[b].first)
                sum > target -> b--
                sum < target -> a++
            }
        }
        return intArrayOf()
    }
}

Solution 3: 使用HashMap

遍历数组，每个循环中，尝试在HashMap中找第二个数的期望值，如果找到，返回结果，否则把当前数字放入HashMap，用于下次查找。时间复杂度为O(n)。

//Kotlin
class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val map = HashMap<Int, Int>()
        nums.forEachIndexed { index, i ->
            val a = map.get(target - i)
            if (a != null) {
                return intArrayOf(a, index)
            }
            map.put(i, index)
        }
        return intArrayOf()
    }
}