题目描述

题目大意&链接

给定两个正整数，计算它们的和。

输入输出样例：
输入：

12
23

输出：

35

详情：ac_791高精度加法

解题思路

高精度加法需要注意2点。

用户输入的两个整数数值可能比较大，需要用字符串 string 进行读取，然后再存到 vector 容器中：

string a, b;
vector<int> A, B;

cin>>a>>b;
//注意要逆序存储到 vector 容器中
for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
for(int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');

定义 t 记录相加时是否进位，将 t%10 作为结果的数值位，t/=10作为进位：

vector<int> c;

int t = 0; //进位
for(int i = 0; i < A.size() || i < B.size(); i++)
{
    if(i < A.size()) t += A[i];
    if(i < B.size()) t += B[i];
    c.push_back(t % 10);
    t /= 10;
}

if(t) c.push_back(1);

完整代码

#include<iostream>
#include<vector>

using namespace std;

vector<int> add(vector<int> &A, vector<int> &B)
{
    vector<int> c;
    
    int t = 0; //进位
    for(int i = 0; i < A.size() || i < B.size(); i++)
    {
        if(i < A.size()) t += A[i];
        if(i < B.size()) t += B[i];
        c.push_back(t % 10);
        t /= 10;
    }
    
    if(t) c.push_back(1);
    return c;
}

int main()
{
    string a, b;
    vector<int> A, B;
    
    cin>>a>>b;
    for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    for(int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
    
    auto c = add(A, B);
    
    for(int i = c.size() - 1; i >= 0; i--) printf("%d", c[i]);
    return 0;
}

时间和空间复杂度

假设 a 和 b 的长度分别为 n 和 m，则：
时间复杂度：O(n + m)
空间复杂度：O(n + m)