1. Two Sum 两数之和

1. 题目详情

• leetcode题目地址 (opens new window)

• leetcode-cn 题目地址 (opens new window)

📗difficulty：Easy

🎯Tags：Array (opens new window)，HashTable (opens new window)

题目描述：

给定一个数组，返回 2 个数组的下标，使得这 2 个数组相加之和为一个特定的数。

假定每组输入有只有一个唯一的解，你不会使用数组中的一个数字 2 次。

样例：

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

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

2. 解题思路

枚举法，时间复杂度极高。

Version 1：

public int[] twoSum(int[] nums, int target) {
    int[] ans = new int[2];
    for (int i = 0;i < nums.length;i++) {
        for (int j = i + 1;j < nums.length;j++) {
            if (nums[i] + nums[j] == target) {
                ans[0] = i;
                ans[1] = j;
            }
        }
    }
    return ans;
}

Complexity analysis:

• Time complexity: $O(n^2)$.
• Space complexity: $O( 1 )$.

3. 优秀解答

3.1 使用 HashTable

定义一个 HashMap map ，遍历给定的 nums 数组，每次查询 map 中是否含有 target - nums[i] ，如果不包含则将当前遍历到的数 nums[i] 存入 map 中，如果含有，则返回 index 。

这样的设计，使得哈希表的 key 存储了 nums[i] 的值，而 value 存储的是对应的 nums[i] 在数组中的index。

核心代码：

public int[] twoSum(int[] nums, int target) {
    HashMap<Integer,Integer> map = new HashMap<>();
    for (int i = 0;i < nums.length;i++){
        // map 的 key 为 nums 数组中的数
        if (map.containsKey(target - nums[i])) { 
            ans[0] = map.get(target - nums[i]);
            ans[1] = i;
        } else {
            map.put(nums[i],i);
        }
    }
    return ans; 
}

Complexity analysis:

• Time complexity: $O(n)$.
  • 遍历数组 nums[i] 的时间复杂度是 $O(n)$ , HashMap 的查找和 add 的时间复杂度是 $O(1)$
• Space complexity: $O(n)$.
  • HashMap 最坏情况下存放 n 个元素。

additional

object LeetcodeNumberOne {
    @JvmStatic
    fun main(args: Array<String>) {
        var result = twoSum(intArrayOf(2, 7, 11, 15), 9)
        println(result.toList())
        result = twoSum(intArrayOf(3, 2, 4), 6)
        println(result.toList())
    }

    private fun twoSum(nums: IntArray, target: Int): IntArray {
        val resultArray = mutableListOf<Int>()
        val map = mutableMapOf<Int, Int>()
        for (i in nums.indices) {
            // map 的 key 为 nums 数组中的数
            if (map.containsKey(target - nums[i])) {
                map[target - nums[i]]?.let { resultArray.add(it) }
                resultArray.add(i)
            } else {
                map[nums[i]] = i
            }
        }
        return resultArray.toIntArray()
    }
}