具有相同数据类型代码的相同逻辑代码在 Java 中传递，但不在 C++ 中传递?

Question

我正在解决一个leetcode问题，我们必须找到添加到目标的可能集合的数量。

给定一个包含所有正数且没有重复项的整数数组，找到加起来为正整数目标的可能组合数。

我用Java编写了代码

.JAVA

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target+1];
        dp[0] = 1;
        for(int i = 1; i <= target; i++){
            for(int num : nums){
                if(i >= num){
                    dp[i] += dp[i-num];
                }
            }
        }
        return dp[target];
    }
}

它通过了所有测试用例，但是当我在C++中编写相同的代码时。它失败了几个测试用例。

C++

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        int dp[target+1] = {0};
        dp[0] = 1;
        for(int i = 1; i <= target; i++){
            for(int num : nums){
                if(i >= num){
                    dp[i] += dp[i-num];
                }
            }
        }
        return dp[target];
    }
};

测试用例是：

nums : [3,33,333]
target : 10000

我收到的错误：

Line 9: Char 27: runtime error: signed integer overflow: 1941940377 + 357856184 cannot be represented in type 'int' (solution.cpp)

注意：如您所见，在代码中，我只更改了dp数组部分的声明。为什么我会收到此错误。出了什么问题？

Answer 1

leetcode 的int似乎是 32 位，通常可以表示 [-2^31, 2^31) 范围内的数字。

溢出有符号整数在C++中具有未定义的行为。有符号的 32 位 int 在不同的平台上有不同的表示形式。您最常会找到两者的补码版本，但还有其他版本。

                2^31-1 = 2147483647
1941940377 + 357856184 = 2299796561 // overflow error in C++

添加(如果需要(

#include <cstdint>

并替换

int dp[target+1] = {0};

跟

std::vector<std::uintmax_t> dp(target+1, 0);

std::uintmax_t为您提供了最大的无符号整数类型，并且溢出的无符号整数在C++中具有明确定义的行为，因此即使您最终得到的计算大于限制，例如对于 64 位整数18446744073709551615，它也只是环绕。 在这种情况下18446744073709551615 + 1 == 0。

在 Java 中，溢出 int 具有明确定义的行为。
2147483647 + 1 = -2147483648
这就是为什么在Java中使用该代码时不会遇到麻烦的原因。

Answer 2

虽然@TedLyngmo的回答似乎已经正确地确定了问题，但我不同意解决方案。

您不应该只是忽略溢出，即使它的行为已经明确定义。你得到的编码问题本身是有缺陷的，因为事实上，整数的可能加法分解的数量随着该整数的值呈指数增长，这意味着输出的大小至少是输入数字值的某个线性函数 - 这意味着任何固定大小的类型都是不合适的。

如果你真的想解决这个问题并在没有溢出的情况下产生正确的输出，你将需要一个"big int"类 - 可以容纳任意大值的东西。

下面是 BigInt 实现C++示例：

https://github.com/kasparsklavins/bigint

当然还有其他的(但标准库中没有(。