Leetcode 1.两数之和

题：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

解一：

fun twoSum(nums: IntArray, target: Int): IntArray {
        val n = nums.size
        var sum: IntArray = intArrayOf(0,0)
        (0 until n).map {
            for (j in it+1 until n){
                if (nums[it]+nums[j] == target){
                    sum[0] = it
                    sum[1] = j
                }
            }
        }
        return sum
}

GG2T75%NM5M66X0B5D%ZSRD.png

分析：可优化，取到值后直接返回
解二：

    fun twoSum(nums: IntArray, target: Int): IntArray {
        val n = nums.size
        var sum: IntArray = intArrayOf(0,0)
        (0 until n).map {
            for (j in it+1 until n){
                if (nums[it]+nums[j] == target){
                    sum[0] = it
                    sum[1] = j
                    return sum
                }
            }
        }
        return sum
    }

分析：性能提升不多，可再优化
解三：

 fun twoSum(nums: IntArray, target: Int): IntArray {
        val map: MutableMap<Int, Int?> = HashMap()
        for (i in nums.indices) {
            val complement = target - nums[i]
            if (map.containsKey(complement)) {
                return intArrayOf(map[complement]!!, i)
            }
            map[nums[i]] = i
        }
        throw IllegalArgumentException("No two sum solution")
    }