面试题:两数组之和

题目

有两个数组：int[] a = {1,2,3,4}; int[] b = {5,6,7}; 请实现add(a, b);算法，计算两个数组相加的值int c [] = {1,8,0,1}; 即1234+567=1801。

解答

算法一

将字符串转换为数字，计算出c=a+b后，再将c转换为字符串输出：

public class ArrayAddition {
    public static int[] add(int[] a, int[] b) {
        // 将数组转换为字符串
        StringBuilder num1 = new StringBuilder();
        StringBuilder num2 = new StringBuilder();
        
        for (int i : a) {
            num1.append(i);
        }
        
        for (int i : b) {
            num2.append(i);
        }
        
        // 将字符串转换为整数
        int number1 = Integer.parseInt(num1.toString());
        int number2 = Integer.parseInt(num2.toString());
        
        // 相加得到结果
        int sum = number1 + number2;
        
        // 将结果转换为字符串
        String sumString = String.valueOf(sum);
        
        // 创建结果数组
        int[] result = new int[sumString.length()];
        
        // 将字符串拆分为数组
        for (int i = 0; i < sumString.length(); i++) {
            result[i] = Character.getNumericValue(sumString.charAt(i));
        }
        
        return result;
    }

    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4};
        int[] b = {5, 6, 7};
        
        int[] c = add(a, b);
        
        // 打印结果数组
        for (int value : c) {
            System.out.print(value);
        }
    }
}

算法二

对位相加，短的数组前面补0，最终结果无进位需要去掉：

import java.util.Arrays;

public class ArrayAddition {
    public static int[] add(int[] a, int[] b) {
        // 找到两个数组的最大长度
        int maxLength = Math.max(a.length, b.length);
        
        // 创建结果数组
        int[] result = new int[maxLength + 1];
        
        // 从数组的最后一位开始逐位相加
        int carry = 0;
        for (int i = 0; i < maxLength; i++) {
            int digitA = i < a.length ? a[a.length - 1 - i] : 0;
            int digitB = i < b.length ? b[b.length - 1 - i] : 0;
            
            int sum = digitA + digitB + carry;
            result[result.length - 1 - i] = sum % 10;
            carry = sum / 10;
        }
        
        // 处理最后的进位
        result[0] = carry;
        
        // 如果最高位没有进位，去掉最高位
        if (result[0] == 0) {
            result = Arrays.copyOfRange(result, 1, result.length);
        }
        
        return result;
    }

    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4};
        int[] b = {5, 6, 7};
        
        int[] c = add(a, b);
        
        // 打印结果数组
        for (int value : c) {
            System.out.print(value);
        }
    }
}