Easy

题目描述

整数的 数组形式 num 是按照从左到右的顺序表示其数字的数组。

  • 例如，对于 num = 1321，数组形式是 [1,3,2,1]。

给定 num，整数的数组形式，和整数 k，返回 整数 num + k 的数组形式。

示例 1：

输入：num = [1,2,0,0], k = 34
输出：[1,2,3,4]
解释：1200 + 34 = 1234

示例 2：

输入：num = [2,7,4], k = 181
输出：[4,5,5]
解释：274 + 181 = 455

示例 3：

输入：num = [2,1,5], k = 806
输出：[1,0,2,1]
解释：215 + 806 = 1021

提示：

  • 1 <= num.length <= 10^4
  • 0 <= num[i] <= 9
  • num 不包含任何前导零，除了零本身。
  • 1 <= k <= 10^4

解题思路

这道题要求我们将一个以数组形式表示的整数与一个普通整数相加，并返回结果的数组形式。

方法一：模拟加法（推荐） 我们可以模拟手工加法的过程，从数组的最后一位开始向前逐位相加：

  1. 从 num 的最后一位开始，将当前位与 k 的个位数相加
  2. 处理进位：如果和大于等于10，则进位为1，当前位为 sum % 10
  3. 更新 k：k = k / 10 + carry，这样下一轮循环时 k 的个位就是原来的十位数加上进位
  4. 重复直到处理完所有位数且 k 为0

这个方法的巧妙之处在于直接使用 k 来处理进位和剩余的数字，避免了复杂的进位逻辑。当 num 的所有位都处理完后，如果 k 还有剩余，继续处理即可。

方法二：转换为字符串 另一种思路是将数组转换为整数，相加后再转回数组，但这种方法在处理大数时可能溢出，不够通用。

时间复杂度主要取决于数组长度和 k 的位数，空间复杂度为常数（不考虑输出数组）。

代码实现

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

class Solution:
    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        result = []
        i = len(num) - 1
        
        while i >= 0 or k > 0:
            if i >= 0:
                k += num[i]
                i -= 1
            result.append(k % 10)
            k //= 10
        
        return result[::-1]

public class Solution {
    public IList<int> AddToArrayForm(int[] num, int k) {
        List<int> result = new List<int>();
        int i = num.Length - 1;
        
        while (i >= 0 || k > 0) {
            if (i >= 0) {
                k += num[i];
                i--;
            }
            result.Add(k % 10);
            k /= 10;
        }
        
        result.Reverse();
        return result;
    }
}

var addToArrayForm = function(num, k) {
    const result = [];
    let i = num.length - 1;
    
    while (i >= 0 || k > 0) {
        if (i >= 0) {
            k += num[i];
            i--;
        }
        result.push(k % 10);
        k = Math.floor(k / 10);
    }
    
    return result.reverse();
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(max(n, log k))，其中 n 是数组长度，log k 是 k 的位数
空间复杂度O(1)，不考虑输出数组的空间

相关题目