top1
给定一个数组和一个目标和，从数组中找两个数字相加等于目标和，输出这两个数字的下标。
1. 解法一
简单粗暴些，两重循环，遍历所有情况看相加是否等于目标和，如果符合直接输出。
publicint[] twoSum(int[] nums, inttarget) { int []ans=newint[2]; for(inti=0;i<nums.length;i++){ for(intj=(i+1);j<nums.length;j++){ if(nums[i]+nums[j]==target){ ans[0]=i; ans[1]=j; returnans; } } } returnans; }
2. 解法二
在上边的解法中看下第二个 for 循环步骤。
publicint[] twoSum(int[] nums, inttarget) { Map<Integer,Integer>map=newHashMap<>(); for(inti=0;i<nums.length;i++){ map.put(nums[i],i); } for(inti=0;i<nums.length;i++){ intsub=target-nums[i]; if(map.containsKey(sub)&&map.get(sub)!=i){ returnnewint[]{i,map.get(sub)}; } } thrownewIllegalArgumentException("No two sum solution"); }
top2
就是两个链表表示的数相加，这样就可以实现两个很大的数相加了，无需考虑数值 int ，float 的限制了。
由于自己实现的很乱，直接按答案的讲解了。
首先每一位相加肯定会产生进位，我们用 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 就是代表个位数，那么开始初始化的时候并不知道它的值是多少，所以还需要在进入循环前单独对它进行值的更正，不能像现在一样只用一个循环简洁。
1.解法一
classListNode { intval; ListNodenext; ListNode(intx) { val=x; } } publicListNodeaddTwoNumbers(ListNodel1, ListNodel2) { ListNodedummyHead=newListNode(0); ListNodep=l1, q=l2, curr=dummyHead; intcarry=0; while (p!=null||q!=null) { intx= (p!=null) ?p.val : 0; inty= (q!=null) ?q.val : 0; intsum=carry+x+y; carry=sum/10; curr.next=newListNode(sum%10); curr=curr.next; if (p!=null) p=p.next; if (q!=null) q=q.next; } if (carry>0) { curr.next=newListNode(carry); } returndummyHead.next; }
