题目描述

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

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

题目分析

• 暴力枚举：两层循环，时间复杂度O(n^2)
• 哈希表：存储前面遇到过的数字及其下标，时间复杂度O(n)

Java

public int[] twoSum(int[] nums, int target) {
    HashMap<Integer, Integer> m = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int current = nums[i];
        if (m.get(target - current) != null) {
            return new int[]{i, m.get(target - current)};
        }
        m.put(current, i);
    }
    return new int[]{};
}

Kotlin

fun twoSum(nums: IntArray, target: Int): IntArray {
    val map = HashMap<Int, Int>()
    for (i in nums.indices) {
        val cur = nums[i]
        if (map[target - cur] != null) {
            return intArrayOf(i, map[target - cur]!!)
        }
        map[cur] = i
    }
    return intArrayOf()
}