前⾔
⼤家好，我是爱学习爱分享的沉默王⼆。微信搜索「沉默王⼆」可以关注我的原创公众号，回复关键字
「1024」就可以拉取离线版的《JavaGuide ⾯试突击》下载地址。
不经意间，在 GitHub 上发现了⼀个 1G 棒的 LeetCode 刷题笔记，重点来了，是纯正的 Java 版。我⻅过很
多⽜逼的刷题笔记，有 Go 版的，有 C++ 版的，唯独没有 Java 版的，所以这次，我感觉找到了宝藏！
题解预览地址：https://leetcode.wang，推荐电脑端打开，⼿机打开的话将⻚⾯滑到最上边，左上⻆
是菜单
leetcode 题⽬地址 https://leetcode.com/problemset/all/
github 项⽬地址：https://github.com/wind-liang/leetcode
01、题⽬描述 （简单难度）
给定⼀个数组和⼀个⽬标和，从数组中找两个数字相加等于⽬标和，输出这两个数字的下标。
解法⼀
简单粗暴些，两重循环，遍历所有情况看相加是否等于⽬标和，如果符合直接输出。
时间复杂度：两层 for 循环，O（n²）
空间复杂度：O（1）
解法⼆
在上边的解法中看下第⼆个 for 循环步骤。
我们换个理解⽅式：
第⼆层 for 循环⽆⾮是遍历所有的元素，看哪个元素等于 sub ，时间复杂度为 O（n）。
有没有⼀种⽅法，不⽤遍历就可以找到元素⾥有没有等于 sub 的？
hash table ！！！
我们可以把数组的每个元素保存为 hash 的 key，下标保存为 hash 的 value 。
这样只需判断 sub 在不在 hash 的 key ⾥就可以了，⽽此时的时间复杂度仅为 O（1）！
需要注意的地⽅是，还需判断找到的元素不是当前元素，因为题⽬⾥讲⼀个元素只能⽤⼀次。
public int[] twoSum(int[] nums, int target) {
int []ans=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){
ans[0]=i;
ans[1]=j;
return ans;
}
}
}
return ans;
}
for(int j=(i+1);j<nums.length;j++){
if(nums[i]+nums[j]==target){
for(int j=(i+1);j<nums.length;j++){
sub=target-nums[i]
if(nums[j]==sub){
时间复杂度：⽐解法⼀少了⼀个 for 循环，降为 O（n）
空间复杂度：所谓的空间换时间，这⾥就能体现出来， 开辟了⼀个 hash table ，空间复杂度变为 O（n）
解法三
看解法⼆中，两个 for 循环，他们⻓的⼀样，我们当然可以把它合起来。复杂度上不会带来什么变化，变化
仅仅是不需要判断是不是当前元素了，因为当前元素还没有添加进 hash ⾥。
总结
题⽬⽐较简单，毕竟暴⼒的⽅法也可以解决。唯⼀闪亮的点就是，时间复杂度从 O（n²）降为 O（n） 的时
候，对 hash 的应⽤，有眼前⼀亮的感觉。
02、题⽬描述（中等难度）
public int[] twoSum(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 sub=target-nums[i];
if(map.containsKey(sub)&&map.get(sub)!=i){
return new int[]{i,map.get(sub)};
}
}
throw new IllegalArgumentException("No two sum solution");
}
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map=new HashMap<>();
for(int i=0;i<nums.length;i++){
int sub=target-nums[i];
if(map.containsKey(sub)){
return new int[]{i,map.get(sub)};
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
就是两个链表表示的数相加，这样就可以实现两个很⼤的数相加了，⽆需考虑数值 int ，float 的限制了。
由于⾃⼰实现的很乱，直接按答案的讲解了。
图示
链表最左边表示个位数，代表 342 + 465 =807 。
思路
⾸先每⼀位相加肯定会产⽣进位，我们⽤ carry 表示。进位最⼤会是 1 ，因为最⼤的情况是⽆⾮是 9 + 9 +
1 = 19 ，也就是两个最⼤的数相加，再加进位，这样最⼤是 19 ，不会产⽣进位 2 。下边是伪代码。
初始化⼀个节点的头，dummy head ，但是这个头不存储数字。并且将 curr 指向它。
初始化进位 carry 为 0 。
初始化 p 和 q 分别为给定的两个链表 l1 和 l2 的头，也就是个位。
循环，直到 l1 和 l2 全部到达 null 。
设置 x 为 p 节点的值，如果 p 已经到达了 null，设置 x 为 0 。
设置 y 为 q 节点的值，如果 q 已经到达了 null，设置 y 为 0 。
设置 sum = x + y + carry 。
更新 carry = sum / 10 。
创建⼀个值为 sum mod 10 的节点，并将 curr 的 next 指向它，同时 curr 指向变为当前的新节
点。
向前移动 p 和 q 。
判断 carry 是否等于 1 ，如果等于 1 ，在链表末尾增加⼀个为 1 的节点。
返回 dummy head 的 next ，也就是个位数开始的地⽅。
初始化的节点 dummy head 没有存储值，最后返回 dummy head 的 next 。这样的好处是不⽤单独对
head 进⾏判断改变值。也就是如果⼀开始的 head 就是代表个位数，那么开始初始化的时候并不知道它的
值是多少，所以还需要在进⼊循环前单独对它进⾏值的更正，不能像现在⼀样只⽤⼀个循环简洁。
代码
时间复杂度：O（max（m，n）），m 和 n 代表 l1 和 l2 的⻓度。
空间复杂度：O（max（m，n）），m 和 n 代表 l1 和 l2 的⻓度。⽽其实新的 List 最⼤⻓度是 O（max
（m，n））+ 1，因为我们的 head 没有存储值。
扩展
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0);
ListNode p = l1, q = l2, curr = dummyHead;
int carry = 0;
while (p != null || q != null) {
int x = (p != null) ? p.val : 0;
int y = (q != null) ? q.val : 0;
int sum = carry + x + y;
carry = sum / 10;
curr.next = new ListNode(sum % 10);
curr = curr.next;
if (p != null) p = p.next;
if (q != null) q = q.next;
}
if (carry > 0) {
curr.next = new ListNode(carry);
}
return dummyHead.next;
}
