title: "Leecode1"
date: 2019-08-29T15:27:37+08:00
draft: true
本章内容为：《LeeCode算法题1》
作者：nuoccc
今天准备开始做一些LeeCode的算法题，每天都会更新一篇文章来代表我做的题，并给上解题方案
第一题:两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
这题除了常规的暴力破解，进行循环判断，最优的方案应该是用HashMap进行存值
接下来进行解题:
首先我们来看题目要求:
由于我们的返回值是一个下标值，但求目标值却是用的本身值，所以我们需要一个map存放当前下 标，以及当前下标的本身值，并把所有map放到一个集合中
当存放完毕之后，我们再次便历数组，找出每个值应该对应的值，并判断hash表内是否存在这个值
当然这是特殊情况，一次便找到，我们再来延伸普通情况，如果不存在，数组继续便历，直到找到数组结束如果都没找到，我们就弹出不存在这样的值
然后题目分析完毕，进行代码的编写
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap();//创建一个hashmap表
for(int i=0;i<nums.length;i++){
map.put(nums[i],i);//把数组的值以及下标放入map中
}
for(int i=0;i<nums.length;i++){
int complement=target-nums[i];//找出对应的值
if(map.containsKey(complement)&&map.get(complement!=i)){
//如果hashmap表中存在这个对应值，并且它不是当前的这个数
return new int[] {i,map.get(complement)};
//那就说明找到了这两个数，并进行结果返回
}
}
throw new IllegalArgumentException("No two sum solution");
//遍历完数组还没找到这样的两个数，说明不存在，抛出异常说明不存在
}
}
这个代码一共进行了两遍查找，其实还是有点麻烦，我们可以边放边找
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap();//创建一个hashmap表
for(int i=0;i<nums.length;i++){
int complement = target-nums[i];//找出当前的对应值
if(map.containsKey(complement)){
//从hashmap里面去找存在这个值没，是往前找跟之前不一样，所以也不用跟i进行比较，肯定不可能是当前值
return new int[]={i,map.get(complement)};
//如果找到了就返回
}else{
map.put(nums[i],i);
//这就是跟上面一点不同的地方，之前是先放再找，这个是先找，没有我再放，节省了一次遍历集合的时间
}
}
throw new IllegalArgumentException("No two sum solution");
//遍历完数组还没找到这样的两个数，说明不存在，抛出异常说明不存在
}
}
这就是leecode的第一题两数之和的解法
第二题:两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers
