两个数组元素之和？

Question

给定两个随机整数数组，其中每个索引处都有0到9的数字（即每个给定数组的每个索引处都有一个个位数的整数）。我需要找到由输入数组表示的数字的总和，并将结果放入另一个数组中。

我认为我的代码一切正常，因为我已经对不同的数组执行了近50到60次。但是当我将其提交到学校的在线评测系统时，它只接受了4个测试用例，并拒绝了其他两个。我无法弄清楚在哪种情况下它会给出错误的输出。需要一点帮助。

以下是我的代码：

public static int[] sumOfTwoArrays(int[] arr1, int[] arr2){
    int size1 = arr1.length;
    int size2 = arr2.length;
    int carry = 0,sum,s,r;
    if(size1 == size2) {
        int arr3[] = new int[size1+1];
        for(int i=arr1.length-1;i>=-1;i--) { 
            if(i==-1) {
                arr3[i+1] = carry;
                //System.out.println(i+1+" "+arr3[i+1]);
            } else {
                sum = arr1[i] + arr2[i];
                if(sum>9) {
                    s =sum;
                    r = s % 10;
                    arr3[i+1] = carry + r;
                    carry = 1;
                    //System.out.println(i+" "+arr3[i]);    
                } else {
                    if(sum==9 && carry==1) {
                        s =sum+carry;
                        r = s % 10;
                        arr3[i+1] = r;
                    } else {
                        arr3[i+1] = sum+carry;
                        carry=0; 
                    }
                    //System.out.println(i+" "+arr3[i]);
                }  
            }      
        }
        return arr3;
    } else if (size1>size2) {
       int arr3[] = new int[size1+1];
       int diff = arr1.length - arr2.length;
       for(int i=arr1.length-1;i>=-1;i--) {
           if(i==-1) {
               arr3[i+1] = carry;
           } else {
               if(i>=diff) {
                   sum = arr1[i] + arr2[i-diff];
                    if(sum>9) {
                        s =sum;
                        r = s % 10;
                        arr3[i+1] = carry + r;
                        carry = 1;
                    } else {
                        if(sum==9 && carry==1) {
                            s =sum+carry;
                            r = s % 10;
                            arr3[i+1] = r;
                        } else {
                            arr3[i+1] = sum+carry;
                            carry=0; 
                        }
                    } 
                }  // end of diff i
                else {
                   arr3[i+1] =  arr1[i];
                   carry = 0;
                }
            }      
        }
        return arr3;
    } else {
        int arr3[] = new int[size2+1];
        int diff = arr2.length - arr1.length;
        for(int i=arr2.length-1;i>=-1;i--) {
            if(i==-1) {
                arr3[i+1] = carry;
            } else {
                if(i>=diff) {
                    sum = arr2[i] + arr1[i-diff];
                    if(sum>9) {
                        s =sum;
                        r = s % 10;
                        arr3[i+1] = carry + r;
                        carry = 1;
                    } else {
                        if(sum==9 && carry==1) {
                            s =sum+carry;
                            r = s % 10;
                            arr3[i+1] = r;
                        } else {
                            arr3[i+1] = sum+carry;
                            carry=0; 
                        }
                    }  
                }  // end of diff i
                else {
                    arr3[i+1] =  arr2[i];
                    carry = 0;
                }
            }      
        }
        return arr3;
    }   
}

样例输入：

int[] arr1 = {8,5,3,9,6};
int[] arr2 = {3,3,3,3,3};

输出示例：

{1,1,8,7,2,9}

示例输入：

int[] arr1 = {8,5,3,9,6};
int[] arr2 = {1,0,5}; 

样例输出:

{0,8,5,5,0,1}

- Prince Vijay Pratap

---

这可能包含有关算法、输入和输出的一些解释。 - AxelH

你最后输出中的前导 0 真的需要吗？它不应该是 {8,5,5,0,1} 吗？ - Roland

@Roland 你不能轻易确定结果是否需要进位，所以我认为OP的方法是可以的。 - Sentry

这在某种程度上是正确的。但我更想知道是否真的需要呢？如果测试结果显示不允许有前导0，那该怎么办？ - Roland

@PrinceVijayPratap 在我的解决方案中，我已经添加了你的 bug 的原因。 - AxelH

Answer 1

我有一个基于Eran解决方案的算法（他已经修复了错误，我正在努力解决），由于我使用的数组较少，所以我想分享它。

public static int[] sum(int[] arr1, int[] arr2){
    int carry = 0;
    int sum = 0;

    int len1 = arr1.length;
    int len2 = arr2.length;
    int len = Math.max(len1, len2);

    int arr3[] = new int[len + 1];

    for (int i = 1; i <= len; i++) {
        sum =
            (len1 - i >= 0 ? arr1[len1-i] : 0)
            + (len2 - i >= 0 ? arr2[len2-i] : 0)
            + carry;

        arr3[len-i+1] = sum%10;
        carry = sum/10;
    }
    arr3[0] = carry;

    return arr3;
}

三元运算符的使用仍然可读性强，因此我认为这是一个好的解决方案。

简要解释一下，我们从数组末尾开始读取，使用 i 从右向左读取，但基于数组的长度。在不同数组大小的情况下，使用三元运算符。

编辑：

您的算法无法正确处理不同大小的数组中的进位值。

185 + 16 得到的结果是 101。

这只是因为您设置了如下的值：

arr3[i+1] =  arr1[i];

所以你忘记了最后一次操作中可能发生的进位。

- AxelH

---

@PrinceVijayPratap，欢迎您。原因只是因为您没有测试一切;)您没有进行任何不同尺寸和结尾进位的测试。 - AxelH

@AxelH 是的，随机性是罪魁祸首。 - Prince Vijay Pratap

Answer 2

这段代码比必要的复杂，这增加了难以检测到的错误的机会。

您不必根据第一个数组是较小、较大还是相等来实现算法3次。您可以为大小相等且长度为Math.max(arr1.length,arr2.length)的两个数组实现一次算法。 这将消除您代码的三分之二。

int len = Math.max(arr1.length,arr2.length);
int[] arr11 = new int[len];
int[] arr22 = new int[len];
int arr3[] = new int[len+1];
for(int i=len-1;i>=-1;i--) {
    if (i>=len-arr1.length)
        arr11[i]=arr1[i-(len-arr1.length)];
    if (i>=len-arr2.length)
        arr22[i]=arr2[i-(len-arr2.length)];
    // now you can use arr11[i] and arr22[i] instead of arr1[i] and arr2[i]
    ...
}

此外，我建议您在计算sum时立即添加进位- sum = arr11[i] + arr22[i] + carry;，而不是使用sum = arr1[i] + arr2[i];。现在您只需要检查一次sum > 9是否成立。请注意保留HTML标签。

    if(i==-1) {
        arr3[i+1] = carry;
    } else {
        sum = arr11[i] + arr22[i] + carry;
        if(sum>9) {
            arr3[i+1] = sum % 10;
            carry = 1;
        } else {
            arr3[i+1] = sum;
            carry = 0;
        }
    }

将这两个片段组合起来，你将获得：

int carry = 0;
int sum = 0;
int len = Math.max(arr1.length,arr2.length);
int[] arr11 = new int[len];
int[] arr22 = new int[len];
int arr3[] = new int[len+1];
for(int i=len-1;i>=-1;i--) {
    if(i==-1) {
        arr3[i+1] = carry;
    } else {
        if (i>=len-arr1.length)
            arr11[i]=arr1[i-(len-arr1.length)];
        if (i>=len-arr2.length)
            arr22[i]=arr2[i-(len-arr2.length)];
        sum = arr11[i] + arr22[i] + carry;
        if(sum>9) {
            arr3[i+1] = sum % 10;
            carry = 1;
        } else {
            arr3[i+1] = sum;
            carry = 0;
        }
    }
}
return arr3;

编辑:

我有一个小bug。我在较小的数组中添加0，但是我添加的位置是最不显著的位（即高索引）而不是最显著的位（即低索引），这导致如果这两个数组长度不同，则结果错误。 不过我已经修复了它，尽管现在将元素从原始数组复制到arr11和arr22的部分不太易读。

- Eran

---

@Eran 尝试了一下 int arr1[] = {8, 5, 3, 9, 6}; int arr2[] = {1, 0, 5};，但不起作用。 - Prince Vijay Pratap

@PrinceVijayPratap 现在已经修复了长度不同的数组问题。您的输入将会得到输出 [0, 8, 5, 5, 0, 1]。 - Eran

@MauricePerry 现在已经修复。 - Eran

@Eran，是的，现在它可以工作了，但我仍然搞不清楚为什么我的代码这么长却出现问题。每次都给我正确的输出 ఠ_ఠ - Prince Vijay Pratap

@Eran，好吧，我也在写我的算法时得到了这个。我只是为了可读性使用了len1和len2。循环后简单地将arr3[0] = carry;放置在if语句if(i ==-1)之后即可。 - AxelH

Answer 3

它有点能用

        int[] arr1 = {1, 2, 3, 4, 5, 6}, arr2 = {3, 5, 2, 9, 0};
        int[] output = new int[Math.max(arr1.length, arr2.length)];
        int num1 = 0, num2 = 0;
        for (int value : arr1) {
            num1 = (num1 * 10) + value;
        }

        for (int i : arr2) {
            num2 = (num2 * 10) + i;
        }

        int result = (num1 + num2), k = output.length - 1;

        while(result > 0){
            output[k] = (result % 10);
            result = result / 10;
            k--;
        }

        if(k>0){
            output[k] = 0;
            k--;
        }

        for(int value: output){
            System.out.print(value + " ");
        }
    }

- Ayush

Answer 4

int[] firstArray = {1,8,8,8, 8};
        int[] secondArray = {1,8,9};
        String diffstring1 = "", diffstring2 = "";
        for (int i = 0; i < firstArray.length; i++) {
            diffstring1 = diffstring1 + String.valueOf(firstArray[i]);
        }

        for (int i = 0; i < secondArray.length; i++) {
            diffstring2 = diffstring2 + String.valueOf(secondArray[i]);
        }

        int diff = Integer.parseInt(diffstring1) + Integer.parseInt(diffstring2);

        String diifffinal = String.valueOf(diff);
        int[] third = new int[diifffinal.length()];
        for (int j = 0; j < diifffinal.length(); j++) {
            char abc = diifffinal.charAt(j);
            third[j] = Character.getNumericValue(abc);
            Log.d(TAG, "onCreate:---> " + third[j]);
        }

- Dhara Patel

Answer 5

如果你的第二个示例输出中的前导零不是必需的，你也可以使用另一种方法来预处理输入，例如使用以下函数：

static Integer toNumber(int[] arr) {
  return Integer.valueOf(Arrays.stream(arr)
                               .mapToObj(Integer::toString)
                               .collect(Collectors.joining()));
}

这样，您就可以像普通整数一样对数组进行求和：

Integer sum = toNumber(arr1) + toNumber(arr2);

将其转换回数组可以按以下方式完成：

int[] sumArray = sum.toString().chars()
                               .map(operand -> Character.digit(operand, 10))
                               .toArray();

但是您在输出中现在没有前导的0。 该代码使用Java 8编写，但是也可以在没有流的情况下编写（但未经测试）：

static Integer toNumber(int[] arr) {
  StringBuilder integerStrBuilder = new StringBuilder();
  for (int i = 0; i < arr.length; i++) {
    integerStrBuilder.append(Integer.toString(arr[i]));
  }
  return Integer.valueOf(integerStrBuilder.toString());
}

对于数组：

char[] characters = sum.toString().toCharArray();
int[] sumArray = new int[characters.length];
for (int j = 0; j < characters.length; j++) {
  sumArray[j] = Characters.digit(characters[j], 10);
}

- Roland