Link to LeetCode Problem

S1: 逐位相加

将数字逐位相加，从低位到高位。

class Solution {
public:
    vector<int> addToArrayForm(vector<int>& num, int k) {
        vector<int> ans;
        int i = num.size() - 1;
        int carry = 0;
        while (i >= 0 || k > 0 || carry > 0) {
            int a = i >= 0 ? num[i--] : 0;
            int b = k > 0 ? k % 10 : 0;
            k /= 10;
            int sum = a + b + carry;
            ans.push_back(sum % 10);
            carry = sum / 10;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

• Time: $O(max(N,logk))$，N 是 num 的长度，logk 是 k 的位数。进行逐位相加以及最后 reverse 数组的时间分别都是 $O(max(N,logk))$。
• *Space: $O(1)$，*除返回值外，使用的是常数空间。

S2: 相加

将 k 从低位到高位直接加到数组的每一位。

class Solution {
public:
    vector<int> addToArrayForm(vector<int>& num, int k) {
        vector<int> ans;
        int i = num.size() - 1;
        while (i >= 0 || k > 0) {
            k += i >= 0 ? num[i--] : 0;
            ans.push_back(k % 10);
            k /= 10;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* addToArrayForm(int* num, int numSize, int k, int* returnSize){
    int resLen = fmax(numSize + 1, 5); // k 的取值范围 [1, 10^4]，加上进位最多是 5 位数
    int* res = malloc(sizeof(int) * resLen);
    int r, w;

    w = resLen - 1;
    r = numSize - 1;

    while (k || r >= 0) {
        if (r >= 0) k += num[r--];
        res[w--] = k % 10;
        k /= 10;
    }

    int realStart = w + 1;
    *returnSize = resLen - realStart;
    return res + realStart;
}

• Time: $O(max(N,logk))$
• Space: $O(1)$