如何摆脱算术溢出

Question

这是 codility 中的三角问题的代码，它给我抛出一个算术溢出错误。

int solution(vector<int> &A) {

    int i, n;
    n=A.size();
    sort(A.begin(), A.end());
    for(i=0; i<n-2; i++)
    {
        if((A[i]+A[i+1]>A[i+2])&&(A[i]+A[i+2]>A[i+1])&&(A[i+1]+A[i+2]>A[i]))
        {
            return 1;
        }
    }
    return 0;
}

它通过了所有测试，除了 'extreme_arith_overflow1 overflow test, 3 MAXINTs' 说代码 returns 0 但它期望 1。有人知道如何解决这个问题吗？

Answer 1

您将 A.size() 存储在 n 中，然后循环直到 i<n 并访问 A[i+2]。在错误情况下，这是 A[A.size()] 甚至 A[A.size()+1]。这是越界的。修复循环的范围。

当总和大于INT_MAX时出现下一个问题。使用差值而不是总和以避免溢出。请记住，元素按 A[i] <= A[i+1] <= A[i+2]

排序

int solution(vector<int> &A) {
    if (A.size() < 3) return 0;
    const auto n = A.size() - 2;
    std::sort(A.begin(), A.end());
    for(decltype(n) i = 0; i < n; ++i) {
        if((A[i]>A[i+2]-A[i+1])&&(A[i+2]>A[i+1]-A[i])&&A[i]>0) {
            return 1;
        }
    }
    return 0;
}

如何摆脱算术溢出

How to get rid of the arithmetic overflow

c++

arithmetic-overflow