Rust实现LeetCode43字符串乘法时u128溢出，问题出在哪里？

问题根因 #

• 你的实现思路从底层就不符合题目要求：LeetCode第43题的输入字符串长度最多可达200位，而u128类型最多只能存储39位的十进制整数，输入长度超过上限后必然发生整数溢出。
• u128本身是无符号类型，不可能出现负数，你观察到的负数是溢出后产生的异常显示结果，本质还是数值超出了类型承载上限。
• Python的整数是任意精度实现，所以不会触发溢出问题，但你这套暴力逐位相乘累加的实现时间复杂度为O(n*m)，遇到长输入时运行效率自然偏低。

正确实现思路 #

不要尝试用基础整数类型存储最终结果，改用数组模拟竖式乘法逻辑：两个长度分别为m和n的数字相乘，结果最多有m+n位，你可以先把每一位的乘积存入数组对应位置，最后统一处理进位后再转成字符串即可。

修复后的Rust代码 #

pub fn multiply(num1: String, num2: String) -> String {
    if num1 == "0" || num2 == "0" {
        return "0".to_string();
    }
    let (n1, n2) = (num1.as_bytes(), num2.as_bytes());
    let mut res = vec![0; n1.len() + n2.len()];
    
    for (i, &b1) in n1.iter().enumerate().rev() {
        let digit1 = (b1 - b'0') as i32;
        for (j, &b2) in n2.iter().enumerate().rev() {
            let digit2 = (b2 - b'0') as i32;
            let product = digit1 * digit2;
            let sum = product + res[i + j + 1];
            res[i + j + 1] = sum % 10;
            res[i + j] += sum / 10;
        }
    }
    
    // 去掉前导零
    let start = res.iter().position(|&x| x != 0).unwrap();
    res[start..].iter().map(|&x| (x as u8 + b'0') as char).collect()
}

内容的提问来源于stack exchange，提问作者Kevin