LeetCode01两数之和
题目描述：
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
分析：
题意就是让你从数组中找到两个位置他们对应位置的和为target。
本题主要有暴力和哈希两种方法：
法一：暴力法
把所有两两配对的问题全部遍历出来，直到找到满足题意的结果为止，时间复杂度O(n2)
代码：
/* * 时间60ms */ public int[] twoSum(int[] nums, int target) { int a[]=new int[2]; for(int i=0;i<nums.length;i++) { for(int j=i+1;j<nums.length;j++) { if(nums[i]+nums[j]==target) { a[0]=i; a[1]=j; return a; } } } return a; }
法二：借助哈希(一次)
对于上述问题，你可能会疑问：能不能快速的直接知道这个数据是否存在呢？本题得目标是求得两个位置的和为target。这种问题当然可以使用哈希帮忙处理啊：
在第一次遍历你可以用一个HashMap先把各个位置的值-位置当成Key-Value存储，然后进行第二次遍历只需要判断这个HashMap中是否存在(target-a[index])值就可以判断是否存在了。(这种情况要先遍历一遍，n个元素都要)
但是这种情况遇到两个相同的元素，只会储存一个Hash，就会被替代而出现错误！
能不能正确且再简单一点？
答案是可以的，其实我们不需要用hash存储所有，边走边存即可。为什么我们可以这么考虑？因为如果从数的特性来看：
数是一对形式出现的
一对有前后位置之分，在遍历到前的时候不一定会找到后面的元素，但是遍历到后面的元素前面一定被我们存储了。
ac代码为：
/* * 3ms */ public int[] twoSum2(int[] nums, int target) { int a[]=new int[2]; Map<Integer, Integer>map=new HashMap<Integer, Integer>(); for(int i=0;i<nums.length;i++) { if(map.containsKey(target-nums[i])) { a[0]=i; a[1]=map.get(target-nums[i]); return a; } else { map.put(nums[i], i); } } return a; }
LeetCode02两数之加
题目描述：
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例:
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
分析：
本题其实就是用一个链表存储一个数字(逆序存储)，你需要给它计算出结果后在 逆序 存储到一个链表中返回。
所谓加法的运算规则：从两个数的最低位进行计算，进行到下一位的时候需要考虑进位问题。一直到最后，而本题所给的链表刚好可以用来直接计算，因为链表头都是数字最低位可以直接相加，然后一直遍历到结束。可以用一个常数表示进位。
在具体实现(链表)的时候：
创建新的链表，每次将计算的数值插入到链表尾部即可。
需要准确表示进位，并且最后要考虑以下进位
妥善返回正确节点，可以用一个头节点用来使得所有节点都正常操作，而不需要特殊判断。
通过代码第一次比较啰嗦的写法：
当然，如果你遍历链表把各个数字取出来，使用字符串、数字转换然后相加得到一个数字，最后在转成字符串、链表的理论可以，可以自行实现。
第一次比较臃肿但易理解代码为：
public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode node=new ListNode(0);//用一个头节点(不存真实的值) ListNode team=node; int jin=0;//进位 while(l1!=null&&l2!=null)//当可以正常相加时候 { int num=l1.val+l2.val+jin;//该位理论的数字 jin=num/10;//进位0 或 1 num%=10;//实际能表示的数字 team.next=new ListNode(num);//将数字放到下一个节点中 team=team.next;//往下进行 l1=l1.next;l2=l2.next; } //其中一个为null或全为null时候 while (l1!=null) { int num=l1.val+jin; jin=num/10; num%=10; team.next=new ListNode(num); team=team.next; l1=l1.next; } while (l2!=null) { int num=l2.val+jin; jin=num/10; num%=10; team.next=new ListNode(num); team=team.next; l2=l2.next; } if(jin!=0)team.next=new ListNode(jin); return node.next; }
优化后的代码为：
//更简洁的写法 public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode node=new ListNode(0); ListNode team=node; int jin=0;//进位 while(l1!=null||l2!=null) { int num=jin; if(l1!=null) { num+=l1.val;l1=l1.next; } if(l2!=null) { num+=l2.val;l2=l2.next; } jin=num/10; num%=10; team.next=new ListNode(num); team=team.next; } if(jin!=0)team.next=new ListNode(jin); return node.next; }
当然，如果遇到评论区或者其他好的方法也可以，如果我错误还请指正。
欢迎关注微信公众号：bigsai 回复进群即可加入一起刷题。目前已有一百多位战友。
