今天开始记录每天学习一道两道的算法题，由简入难。
今天一共学习了两道算法，一道简单一道中等，分别为两数之和、两数相加，下面开始记录题以及自己的分析。
两数之和
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
分析：刚拿到题发现并不是很难，于是很快写出如下算法：
public int[] sumInArray(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
int val = target - nums[i];
for (int j = i; j < nums.length; j++) {
if (nums[j] == val) {
return new int[] { i, j };
} else {
continue;
}
}
}
return null;
}
但是该方法的时间复杂度为O(n^2)；通过查看解析，发现使用哈希表进行处理，通过以空间换取速度的方式，可以将查找时间从 O(n) 降低到 O(1)，但是如果出现冲突，查找时间还是可能会退化到 O(n)。
方法如下：
public static int[] sumInArray(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int val = target - nums[i];
if (map.containsKey(val)) {
return new int[]{map.get(val), i};
}
map.put(nums[i], i);
}
return null;
}
该方法遍历了一次，因此时间复杂度为O(n)，但是作为代价就是空间复杂度为O(n)。
两数相加
给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
除了数字 0 之外，这两个数字都不会以零开头。
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
分析：首先拿到题目很困惑，因为很长时间没有做链表之类的题目，首先自己想到的是如果其中一个链表开头为0，则直接返回另一个链表，然后在循环进行遍历逐位相加，但是手写代码发现写不出来😓，因此去查看官方解析：
类似于纸上计算两个数字的和，首先从最低有效位也就是列表L1 和 L2 的表头开始相加。由于每位数字都应当处于 0…9 的范围内，因此两个数字的和时可能会出现“溢出”。例如，5 + 7 = 12。在这种情况下，将当前位的数值设置为 22，并将进位 carry=1 带入下一次迭代。进位 carry 必定是 0 或 1，这是因为两个数字相加（考虑到进位）可能出现的最大和为 9 + 9 + 1 = 19。
参考代码如下：
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = new ListNode(0);
ListNode p = l1;
ListNode q = l2;
ListNode currentNode = head;
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;
currentNode.next = new ListNode(sum % 10);
currentNode = currentNode.next;
if (p != null) p = p.next;
if (q != null) q = q.next;
}
if (carry > 0) {
currentNode.next = new ListNode(carry);
}
return head.next;
}
public class ListNode {
int val;
ListNode next;
ListNode(int value) {
val = value;
}
}
