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

Question

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

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

我把代码写在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 在不同平台上有不同的表示。您最常找到的是 Two's complement 版本，但还有其他版本。

                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++ 中具有明确定义的行为，因此即使您最终的计算结果大于限制，例如 18446744073709551615 对于 64位整数，它只会环绕。 18446744073709551615 + 1 == 0 在这种情况下。

在 Java 中，溢出 int 具有明确定义的行为。
2147483647 + 1 = -2147483648
这就是为什么在 Java.

中使用该代码时不会遇到麻烦的原因

Answer 2

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

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

如果你真的想解决这个问题并产生正确的输出而不会溢出，你需要一个 "big int" class - 可以容纳任意大值的东西。

这是一个 C++ BigInt 实现示例：

https://github.com/kasparsklavins/bigint

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

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

Same logic code with same data type code passes in Java but not in C++?

java

c++

arrays

integer-overflow

subset-sum