摘要：因為被乘數每一位數字和乘數相乘的結果是依次錯開的，所以就沒問題。判斷兩個數的大小的方法，是先判斷其長度，如果長度不一樣，則較長的較大，如果長度一樣，則需要比較每一位。

Given two numbers represented as strings, return multiplication of the numbers as a string.
Note: The numbers can be arbitrarily large and are non-negative.

時間 O(NM) 空間 O(N+M)

這題的技巧在于復用同一個結果數組存放上次的計算結果。因為被乘數每一位數字和乘數相乘的結果是依次錯開的，所以就沒問題。

轉換回String前要先把前面的0去掉，但第一位的0不去掉

public class Solution {
    public String multiply(String num1, String num2) {
        if(num1 == null || num2 == null) return null;
        int len1 = num1.length(), len2 = num2.length();
        // 結果的位數最多可能是兩個乘數位數之和
        int len3 = len1 + len2;
        int[] res = new int[len3];
        int carry = 0, i = 0, j = 0;
        for(i = len1 - 1; i >= 0; i--){
            // 先置carry位為0
            carry = 0;
            for(j = len2 - 1; j >= 0; j--){
                // 每一位的乘積，等于之前這一位的結果，加上carry，再加上這一位和乘數的乘積
                int product = carry + res[i + j + 1] + (num1.charAt(i) - "0")*(num2.charAt(j) - "0");
                res[i + j + 1] = product % 10;
                carry = product / 10;
            }
            // 把最后的carry位加上
            res[i + j + 1] = carry;
        }
        StringBuilder resstr = new StringBuilder();
        i = 0;
        // 跳過前面無用的0
        while(i < len3 - 1 && res[i] == 0){
            i++;
        }
        for(; i < len3; i++){
            resstr.append(res[i]);
        }
        return resstr.toString();
    }
}

時間 O(N) 空間 O(N)

從后向前模擬加法

private String addString(String num1, String num2){
    int i = num1.length() - 1, j = num2.length() - 1;
    int k = Math.max(i, j);
    int[] num3 = new int[k + 1];
    int sum = 0, carry = 0;
    while(i >= 0 || j >= 0){
        // 加數的位
        int d1 = i >= 0 ? (num1.charAt(i) - "0") : 0; 
        // 被加數的位
        int d2 = j >= 0 ? (num2.charAt(j) - "0") : 0;
        sum = d1 + d2 + carry;
        num3[k] = sum % 10;
        carry = sum / 10;
        k--;
        i--;
        j--;
    }
    StringBuilder sb = new StringBuilder();
    // 如果最后還有進位要加上
    if(carry != 0) sb.append(carry);
    for(int digit : num3){
        sb.append(digit);
    }
    return sb.toString();
}

有符號的話，就要根據符合判斷具體的操作

如果都是負數，則結果是兩個絕對值相加再取負

如果一個是負數一個正數，則結果是（正數）減去（負數的絕對值），這里要用到減法

如果都是正數則直接相加

private static String addSignedString(String num1, String num2){
    int sign1 = 1, sign2 = 1;
    if(num1.charAt(0) == "-"){
        sign1 = -1;
        num1 = num1.substring(1);
    }
    if(num2.charAt(0) == "-"){
        sign2 = -1;
        num2 = num2.substring(1);
    }
    if(sign1 == sign2){
        String res = addString(num1, num2);
        return sign1 == -1 ? "-" + res : res;
    } else {
        if(sign1 == 1){
            return subString(num1, num2);
        } else {
            return subString(num2, num1);
        }
    }
}

時間 O(N) 空間 O(N)

從后向前模擬減法，計算每一位的值時，用減數的位減去被減數，再加上10，再減去借位，結果模上10就行了。借位則是看之前的結果是否小于10，如果小于10說明借位了。不過要注意的是，我們要用較大的數減去較小的數，如果減數反而較大，我們要用減數減去被減數，然后結果加上負號。判斷兩個數的大小的方法，是先判斷其長度，如果長度不一樣，則較長的較大，如果長度一樣，則需要比較每一位。

private static String subString(String num1, String num2){
    int len1 = num1.length(), len2 = num2.length();
    // 根據兩數的大小關系，決定是直接相減，還是反過來相減取負
    if(len1 > len2){
        return coreSub(num1, num2);
    } else if (len1 < len2){
        return "-"+coreSub(num2, num1);
    } else {
        int compare = num1.compareTo(num2);
        if(compare > 0){
            return coreSub(num1, num2);
        } else if(compare < 0){
            return "-"+coreSub(num2, num1);
        } else {
            return "0";
        }
    }
}

private static String coreSub(String num1, String num2){
    int i = num1.length() - 1, j = num2.length() - 1;
    int[] num3 = new int[i + 1];
    int diff = 0, borrow = 0;
    while(i >= 0){
        int d1 = num1.charAt(i) - "0";
        int d2 = j >= 0? num2.charAt(j) - "0": 0;
        // 計算差值時要先加上10
        diff = d1 + 10 - borrow - d2;
        num3[i] = diff % 10;
        borrow = diff < 10 ? 1 : 0;
        i--;
        j--;
    }
    i = 0;
    while(num3[i] == 0){
        i++;
    }
    StringBuilder sb = new StringBuilder();
    while(i < num3.length){
        sb.append(num3[i]);
        i++;
    }
    return sb.toString();
}

private static String subSignedString(String num1, String num2){
    int sign1 = 1, sign2 = 1;
    if(num1.charAt(0) == "-"){
        sign1 = -1;
        num1 = num1.substring(1);
    }
    if(num2.charAt(0) == "-"){
        sign2 = -1;
        num2 = num2.substring(1);
    }
    if(sign1 == sign2){
        // 都是正數則直接相減
        if(sign1 == 1){
            return subString(num1, num2);
        // 都是負數則后面減去前面
        } else {
            return subString(num2, num1);
        }
    } else {
        // 前正后負則相加
        if(sign1 == 1){
            return addString(num1, num2);
        // 前負后正則相加后取負
        } else {
            return "-"+addString(num1, num2);
        }
    }
}