从今天开始，写一下我在刷 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 中添加元素的时候，是顺序添加的，这个可以自己输入体会一下。
