LeetCode 解题报告 - 1. Two Sum

从今天开始，写一下我在刷 LeetCode 时的心得体会，包括自己的思路和别人的优秀思路，欢迎各种监督啊！ 2016/10/9
编程语言是 Java，代码托管在我的 GitHub 上，包括测试用例。欢迎各种批评指正！

<br />

题目 —— 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.

Example:

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

<br >

解答

• 题目大意
  给出一个整型数组，给出一个特定的数 target，返回和等于 target 的两数下标，假设每次输入只有一组解。

• 解题思路

  • 首先，我能想到最简单的思路就是两个 for 循环，遍历整个数组，n 平方的时间复杂度，这个思路就不再写了，很容易。

• 看了一下标签，发现是 Array 和 Hash Table，结合讨论区的朋友们解答，理解了如下思路：

  • 创建一个 int 数组 result 存放需要返回的下标，因为只需要返回两个，所以数组大小为 2。
  • 创建一个 HashMap<Integer, Integer> 类型的变量 map，key 存放数值，value 存放下标。
  • 循环遍历数组 nums，判断在 map 中是否存在 target-nums[i]：若存在，直接将两个下标存入 result 数组，并返回；若不存在，将 nums[i] 的值和下标放入 map，进入下一次循环。

• 代码实现

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        Map<Integer, Integer> map = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                result[1] = i;
                result[0] = map.get(target - nums[i]);
                return result;
            }
            map.put(nums[i], i);
        }
        return result;
    }
}

• 小结
  用 HashMap 解决问题的好处是，只需要遍历一次数组，时间复杂度为 O(n)。但难点在于，不容易想到这种方法。我们考虑从 每次输入只有一组解 这句话入手，所以数组中肯定没有重复的值，从而使问题迎刃而解。
  另外有个小细节，如果想顺序输出下标的话，需要把 i 赋值给 result[1]，因为我们在向 map 中添加元素的时候，是顺序添加的，这个可以自己输入体会一下。