题目
给出两个很大的整数，要求实现程序求出两个整数之和。注：这两个整数用Long都无法表示
解决方案
思路
在我们运算两位很长的整数加法时，都是通过下面这种方式
其实本质就是把计算过程拆解成一个一个子步骤。针对大整数，可以使用数组来存取，比如整数的最高位存放在数组的下标0处。
以426 709 752 318+95 481 253 129 为例，来看看大整数相加的详细步骤。
第1步
创建两个整型数组，数组长度是较大整数的位数+1。把每一个整数倒序存储到数组中，整数的个位存于数组下标为0的位置，最高位存于数组的尾部。之所以倒序存储，是因为这样更符合从左到右访问数组的习惯。
第2步，创建结果数组，结果数组的长度同样是较大整数的位数+1，+1的目的很明显，是给最高位进位预留的。
第3步，遍历两个数组，从左到右按照对应下标把元素两两相加，就像小学生计算竖式一样。
最先相加的是数组A的第1个元素8和数组B的第1个元素9，结果是7，进位1。把7填充到result数组的对应下标位置，进位的1填充到下一个位置。
第2组相加的是数组A的第2个元素1和数组B的第2个元素2，结果是3，再加上刚才的进位1，把4填充到result数组的对应下标位置。
第3组相加的是数组A的第3个元素3和数组B的第3个元素1，结果是4，把4填充到result数组的对应下标位置。
第4组相加的是数组A的第4个元素2和数组B的第4个元素3，结果是5，把5填充到result数组的对应下标位置。
以此类推……一直把数组的所有元素都相加完毕。
第4步，把result数组的全部元素再次逆序，去掉首位的0，就是最终结果。
代码实现
package arithmetic.com.ty.binary; public class LargeAdd { /** * 大整数求和 * * @param bigNumberA 大整数A * @param bigNumberB 大整数B */ public static String bigNumberSum(String bigNumberA, String bigNumberB) { //1.把两个大整数用数组逆序存储，数组长度等于较大整数位数+1 int maxLength = bigNumberA.length() > bigNumberB.length() ? bigNumberA.length() : bigNumberB.length(); int[] arrayA = new int[maxLength + 1]; /** * 1.大整数倒着存放在数组中，因为计算得先从个位数开始计算，所以为了方便，将个位数存在下标0处，然后正常循环数组就可以做加操作 * 2.获取大整数的每位char，通过 char - '0' 再转换成int */ for (int i = 0; i < bigNumberA.length(); i++) { arrayA[i] = bigNumberA.charAt(bigNumberA.length() - 1 - i) - '0'; } int[] arrayB = new int[maxLength + 1]; for (int i = 0; i < bigNumberB.length(); i++) { arrayB[i] = bigNumberB.charAt(bigNumberB.length() - 1 - i) - '0'; } //2.构建result数组，数组长度等于较大整数位数+1 int[] result = new int[maxLength + 1]; //3.遍历数组，按位相加 for (int i = 0; i < result.length; i++) { int temp = result[i]; temp += arrayA[i]; temp += arrayB[i]; //判断是否进位 if (temp >= 10) { temp = temp - 10; result[i + 1] = 1; } result[i] = temp; } // 4.把result数组再次逆序并转成String StringBuilder sb = new StringBuilder(); //是否找到大整数的最高有效位 boolean findFirst = false; for (int i = result.length - 1; i >= 0; i--) { if (!findFirst) { if (result[i] == 0) { continue; } findFirst = true; } sb.append(result[i]); } return sb.toString(); } public static void main(String[] args) { System.out.println(bigNumberSum("426709752318", "95481253129")); } }
时间复杂度
如果给出的大整数的最长位数是n，那么创建数组、按位计算、结果逆序的时间复杂度各自都是O(n)，整体的时间复杂度也是O(n)。