c++ - 如何摆脱算术溢出

Question

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

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 溢出测试，3 MAXINTs”说代码返回 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;
}