每日一道 LeetCode (1)：两数之和
引言
前段时间看到一篇刷 LeetCode 的文章，感触很深，我本身自己上大学的时候，没怎么研究过算法这一方面，导致自己直到现在算法都不咋地。
一直有心想填补下自己的这个短板，实际上又一直给自己找理由各种推脱。
结果今天晚上吃多了，下定决心要刷一波 LeetCode 的题，刷题的过程顺便写点文章分享下（其实有很好的督促作用）。
LeetCode 的背景啥的我就不多介绍了，我计划只刷简单难度和中等难度的题，据说刷了这两个难度基本上就够了，至于困难这个难度，先等我把前两个部分刷完再说。
大致聊一下刷题的套路，先看题目， 5 分钟左右没思路的直接看答案，这玩意没思路是真没办法，没有基础储备想做题还是有点困难的。
看完答案自己动手写一下代码，这一点很重要，现在面试很多白板代码，一定要自己写，写会有效加深记忆力。
这个系列的文章计划日更，原本以为不是一件很难的事情，结果当我看到了这个：
1700+ 多道题，即使刨除掉困难的部分， 2/3 也有 1000+ 道题，我真的是给自己开了一个非常棒的头，这一下把未来两三年的规划都制定好了，我真是哔了狗了。
不过不管怎么样吧，决心都下好了，那么做还是要做的，对我这个计划感兴趣的同学可以每天在留言区和我一起打卡，预计每篇文章阅读时长在 3 分钟左右，写代码加调试代码总时长不会超过半小时。使用的代码为 Java ，如果使用 Python 写的话有点太取巧了。
做事情，重要的是要坚持。
需要代码朋友可以访问我的 GitHub 和 Gitee 获取，每天的代码我会同步提交至这两个代码仓库：
GitHub：https://github.com/meteor1993/LeetCode
Gitee：https://gitee.com/inwsy/LeetCode
题目：两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
思路
首先整理下思路，虽然题目的目标是要求一个加法，使用程序直接写加法有点不是那么好写，稍微转变一下，使用目标值 target 减去数组 nums 中的一个值，如果得到的结果也在这个数组中，那么我们就解题完成。
暴力破解
我最先想到的也是最简单的方案，就是暴力破解，直接两个循环套一下，暴力去算，得到结果：
public int[] twoSum_1(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
int temp = target - nums[i];
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] == temp) {
return new int[]{i, j};
}
}
}
throw new IllegalArgumentException("No two sum solution");
}
这种方案的缺点是时间复杂度有点高，优点是简单，应该是每个人都能想到的方案。
因为总共有 n 个元素，而对于其中的每个元素来讲，我们都需要遍历整个数组来寻找是否存在它所需要的对应的元素，这将耗费 O(n) 的时间。
时间复杂度： \(O(n^2)\) 。
空间复杂度： O(1) 。
两次哈希表
对暴力破解方案的优化思路是，整个数组，至少需要迭代一次，关键是在这次迭代中，我们要寻找另一种方案，能比套一层循环更快更高效的找到检查在整个数组中，是否含有我们需要的值。
我们可以借助哈希表来进行寻找，它支持以 「近似」 恒定的时间进行快速查找。
public int[] twoSum_2(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement) && map.get(complement) != i) {
return new int[] {i, map.get(complement)};
}
}
throw new IllegalArgumentException("No two sum solution");
}
我们把包含有 n 个元素的列表遍历两次。由于哈希表将查找时间缩短到 O(1) ，所以时间复杂度为 O(n)。
时间复杂度： O(n) 。
空间复杂度： O(n) 。
一次哈希表：
上面我们是先把数组放到哈希表中，然后再进行遍历，实际上我们可以一边放一边进行遍历操作，直到某一个时刻，打成我们的目标，这时我们可以直接返回数据，剩下没有放到哈希表中的数据也不用再往里面放了。
public int[] twoSum_3(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
虽然这种方式看着比前面的两次哈希表更加的高效，实际上时间复杂度和空间复杂度是一致的，同样是：
时间复杂度： O(n) 。
空间复杂度： O(n) 。