今天開(kāi)始記錄每天學(xué)習(xí)一道兩道的算法題，由簡(jiǎn)入難。
今天一共學(xué)習(xí)了兩道算法，一道簡(jiǎn)單一道中等，分別為兩數(shù)之和、兩數(shù)相加，下面開(kāi)始記錄題以及自己的分析。

兩數(shù)之和

給定一個(gè)整數(shù)數(shù)組和一個(gè)目標(biāo)值，找出數(shù)組中和為目標(biāo)值的兩個(gè)數(shù)。
你可以假設(shè)每個(gè)輸入只對(duì)應(yīng)一種答案，且同樣的元素不能被重復(fù)利用。

給定 nums = [2, 7, 11, 15], target = 9 
因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1] 

分析：剛拿到題發(fā)現(xiàn)并不是很難，于是很快寫(xiě)出如下算法：

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;
    }

但是該方法的時(shí)間復(fù)雜度為O(n^2)；通過(guò)查看解析，發(fā)現(xiàn)使用哈希表進(jìn)行處理，通過(guò)以空間換取速度的方式，可以將查找時(shí)間從 O(n) 降低到 O(1)，但是如果出現(xiàn)沖突，查找時(shí)間還是可能會(huì)退化到 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;
    }

該方法遍歷了一次，因此時(shí)間復(fù)雜度為O(n)，但是作為代價(jià)就是空間復(fù)雜度為O(n)。

兩數(shù)相加

給定兩個(gè)非空鏈表來(lái)表示兩個(gè)非負(fù)整數(shù)。位數(shù)按照逆序方式存儲(chǔ)，它們的每個(gè)節(jié)點(diǎn)只存儲(chǔ)單個(gè)數(shù)字。將兩數(shù)相加返回一個(gè)新的鏈表。
除了數(shù)字 0 之外，這兩個(gè)數(shù)字都不會(huì)以零開(kāi)頭。

輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807

分析：首先拿到題目很困惑，因?yàn)楹荛L(zhǎng)時(shí)間沒(méi)有做鏈表之類(lèi)的題目，首先自己想到的是如果其中一個(gè)鏈表開(kāi)頭為0，則直接返回另一個(gè)鏈表，然后在循環(huán)進(jìn)行遍歷逐位相加，但是手寫(xiě)代碼發(fā)現(xiàn)寫(xiě)不出來(lái)??，因此去查看官方解析：

類(lèi)似于紙上計(jì)算兩個(gè)數(shù)字的和，首先從最低有效位也就是列表L1 和 L2 的表頭開(kāi)始相加。由于每位數(shù)字都應(yīng)當(dāng)處于 0…9 的范圍內(nèi)，因此兩個(gè)數(shù)字的和時(shí)可能會(huì)出現(xiàn)“溢出”。例如，5 + 7 = 12。在這種情況下，將當(dāng)前位的數(shù)值設(shè)置為 22，并將進(jìn)位 carry=1 帶入下一次迭代。進(jìn)位 carry 必定是 0 或 1，這是因?yàn)閮蓚€(gè)數(shù)字相加（考慮到進(jìn)位）可能出現(xiàn)的最大和為 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;
        }
    }

今天學(xué)習(xí)了兩個(gè)算法，再次記錄自己的學(xué)習(xí)狀態(tài)，以敦促自己繼續(xù)去學(xué)習(xí)
Blog
Github