算法

两数之和

题目如下图：

我的答案如下图：

我采用的是最笨的思路，直接暴力的两次循环，第一次外循环是取数组的第一个元素，然后内循环会遍历数组后面除第一个的所有元素，然后和第一个元素相加，看看结果是否为目标值，如果是的话，就证明i和j就是我们所求的下标，接下来，我们就直接把i和j放到数组里面就行了。直接return。
我循环是从第一个元素取到倒数第二个元素，比如我们一共有max个元素，当前外循环取的是第n个元素，那么内循环就要循环从n+1到max的所有元素，都和第n个元素加一遍。

但是我用的方法太过于暴力了，时间复杂度为O(n^2)。那么有没有高效一点的，时间复杂度低一点的解法，有的，可以使用哈希映射这是我在评论区看到的解法，确实比我的解法要好，代码如下图：

可以发现这种解法循环的时间复杂度为O(n)，要比上面的那种暴力解法有效率的多。所以解题的时候有时候借助map哈希映射会变得非常有效率。

注意怎么看时间复杂度，其实就是看你循环的层数的乘积，比如你是两层循环那么你就是O(n^2)。这里其实是使用map哈希映射代替了一层内循环。非常nice。

两数相加

题目如下：


解题代码如下图：


三个测试用例如下图：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode result = null;
        ListNode head = null;
        int jinWei= 0;
        while(l1 != null || l2 != null) {
            int value1 = l1 != null ? l1.val : 0;
            int value2 = l2 != null ? l2.val : 0;
            int sum = value1 + value2;
            int mod = (sum + jinWei) % 10;
            if(head == null) {
                head = new ListNode(mod);
            } else {
                head.next = new ListNode(mod);
                head = head.next;
            }
            
            if(result == null) {
                result = head;
            }

            jinWei = (sum + jinWei) / 10;

            if(l1 != null) {
                l1 = l1.next;
            }
            if(l2 != null) {
                l2 = l2.next;
            }

        }

        if(jinWei > 0) {
            head.next = new ListNode(jinWei);
        }
        return result;
    }
}

几个要点：

• 第一个要点是这个题与我们常规的逻辑是相反的，比如说我们常规两数相加的时候，都是两个数的右边对齐，也即是从两个数的最后一位开始相加，然后进位的时候也是从右边往左边进位；但是你可以发现，本题中的两数相加是倒着我们的真实情况来的，也就是两个数会让他们左对齐，从左边开始相加，并且进位的时候也是从左边进位到右边的。
• 第二个要点是，当结束for循环之后，可能虽然我们把数都加完了，但是可能有进位，比如说9999 + 99的时候，当四次while循环之后，会进1，因此我们最后如果有进位，则需要往链表末尾添加一个链表节点。
• 第三个要点是，用result存储链表的第一个节点的地址；而使用head存储当前循环的链表节点的地址。
• 第四个要点是，可以把本次的两数相加，类比成正常的两数相加，只不过逻辑倒着来就可以了。