⭐ 题目日期：

快手 - 2024/12/2

🌳 题目描述：

在不使用处理大整数的库，不能直接将输入的字符串转换为整数形式的情况下，将以字符串形式输入的数字进行相加计算出它们的和，并以字符串形式进行返回。

示例 1：
输入：num1 = "17", num2 = "118"
输出："135"

🕵🏽‍♂️ 面试评估：

这道题主要考察候选人是否能通过字符串操作模拟加法过程，是否能通过遍历来高效处理数字相加与进位。

🧗难度系数：

⭐️ ⭐️

📝思路分析：

这道题我们运用双指针来实现字符串加法模拟。

1. 构建结果字符串：
   使用 StringBuilder（Java）、列表（Python）或字符串（C++）来存储结果，从低位到高位逐位相加，最终需要反转结果字符串。

2. 双指针遍历规则：

   • 从两个数字的末尾开始逐位相加，使用 i 和 j 分别代表两个字符串的指针。
   • 循环条件是：
     • i >= 0 或 j >= 0：确保所有位数都被处理。
     • carry != 0：处理进位。
   • 逐位相加：
     • 提取当前位的数字，超出范围的部分用 0 补齐。
     • 计算 sum = 当前位的数字 + 进位。
     • 当前位数字：sum % 10，加入结果集中。
     • 更新进位：carry = sum / 10。
   • 移动指针：i--, j--。

3. 结果反转：
   因为结果是从低位计算的，最终需要反转字符串得到正确顺序。

💻代码(Java、Python、C++)：

Java

public String addStrings(String num1, String num2) {
    StringBuilder result = new StringBuilder();
    int carry = 0;

    int i = num1.length() - 1;
    int j = num2.length() - 1;

    while (i >= 0 || j >= 0 || carry != 0) {
        int x = (i >= 0) ? num1.charAt(i) - '0' : 0;
        int y = (j >= 0) ? num2.charAt(j) - '0' : 0;

        int sum = x + y + carry;
        result.append(sum % 10);
        carry = sum / 10;

        i--;
        j--;
    }

    return result.reverse().toString();
}

Python

def addStrings(self, num1: str, num2: str) -> str:
    result = []
    carry = 0

    i, j = len(num1) - 1, len(num2) - 1

    while i >= 0 or j >= 0 or carry != 0:
        x = int(num1[i]) if i >= 0 else 0
        y = int(num2[j]) if j >= 0 else 0

        sum_value = x + y + carry
        result.append(str(sum_value % 10))
        carry = sum_value // 10

        i -= 1
        j -= 1

    return ''.join(result[::-1])

C++

#include <string>
using namespace std;

string addStrings(string num1, string num2) {
    string result;
    int carry = 0;

    int i = num1.length() - 1;
    int j = num2.length() - 1;

    while (i >= 0 || j >= 0 || carry != 0) {
        int x = (i >= 0) ? num1[i] - '0' : 0;
        int y = (j >= 0) ? num2[j] - '0' : 0;

        int sum = x + y + carry;
        result.push_back(sum % 10 + '0');
        carry = sum / 10;

        i--;
        j--;
    }

    reverse(result.begin(), result.end());
    return result;
}

🚵🏻复杂度分析：

• 时间复杂度：O(max(n, m))，其中 n 和 m 分别是 num1 和 num2 的长度。
• 空间复杂度：O(max(n, m))，存储结果字符串所需的空间。

🔬在线评测(Online Judge):

题目链接