1. 两数之和
题目来源：力扣（LeetCode）
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]补全代码：
class Solution {
public int[] twoSum(int[] nums, int target) {
}
}不论是学习，刷题，考试，面试。其实都有一个定律，无答案 < 复杂答案 < 简单正确答案。
我们刷LeetCode时也可以根据这个套路走。没有一口吃成胖子的人，所有的东西都是一步步进化而来。
简单思路
看到题目，我们脑子里大概有了些思路，看到结果我们知道一定要返回一个新数组，那。。。
int[] newNums= new int[2];
//TODO
return newNums;这个两行代码坑定是有的。也就是最后得到的两个值要放到这个新的newNums数组中。现在要做的是求这个两个数。
我们就按我们自己的思路来，我拿nums第一个数和剩余的所有数各自相加如果等于target，那不就找到了吗？如果没有，那就走第二步，拿第二个数和剩余的数各自相加。。。直到找到，或者走完所有的数。
代码实现:
public int[] twoSum(int[] nums, int target) {
int[] newNums= new int[2];
//第一次拿的数
for (int i = 0; i < nums.length; i++) {
//第二次拿的数
for (int j = i + 1; j < nums.length; j++) {
//如果两个相等则向newNums赋值退出
if (nums[i] + nums[j] == target){
newNums[0] = i;
newNums[1] = j;
break;
}
}
}
return newNums;
}
这就是现实了，那开始改进吧！
进阶
我们可不可以用java里现成的工具类呢？list里面好像有个contains()方法可以帮我们找元素，我们那就不用遍历了好像。
思路：我们用target减去第一个元素得到一个结果，然后在剩余的list里面查找是否包含这个结果那不就对了吗？不包含就往下走。额。。。好像需要创建好多list,有什么好办法吗？
有了！
我把的到的结果放到list里面只要在循环开始的时候判断元素是不是在结果里面，在的话不就找到了吗？结果所在的位置就是开始的元素。
代码实现:
public int[] twoSum1(int[] nums, int target) {
int[] newNums= new int[2];
List<Integer> list = new ArrayList<>();
//第一次拿的数
for (int i = 0; i < nums.length; i++) {
//看看是否包含
if (list.contains(nums[i])) {
newNums[0] = list.indexOf(nums[i]);
newNums[1] = i;
break;
}
//不包含把结果放到list里面
list.add(target - nums[i]);
}
return newNums;
}
实现是实现了，但是这效率。。。进阶失败。为什么呢？
分析原因:
这地方好像是用来list的contains和indexOf方法了，我们看下源码怎么实现的。
源码 contains
public boolean contains(Object o) {
return indexOf(o) >= 0;
}indexOf
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}。。。 找到原因了，我里外里循环了三次，肯定比第一次慢多了。那没有好的办法了吗？
再次进阶
list的contains不行，那hashMap的contains，这个方法的时间复杂度应该是O(1)，试试吧。思路和list思路相同，只是把key的的位置放结果，value的位置放元素的位置。
代码实现:
public static int[] twoSum2(int[] nums, int target) {
int[] newNums= new int[2];
HashMap<Integer, Integer> hashMap = new HashMap<>();
//第一次拿的数
for (int i = 0; i < nums.length; i++) {
//看看是否包含
if (hashMap.containsKey(nums[i])) {
newNums[0] = hashMap.get(nums[i]);
newNums[1] = i;
break;
}
//不包含把结果放到list里面
hashMap.put(target - nums[i], i);
}
return newNums;
}
哇，这个速度，应该应该可以完结撒花了吧，🎉🎉🎉。
