简单水篇文章。

一个面试题，int64 数组求和，题目不保证中间过程不会溢出，只能保证结果不溢出。

这题有一个小技巧，直接转换成 uint64 相加，结果再转换回 int64 就行了。这就是补码的性质。

int64_t sum(std::vector<int64_t> arr) {
    uint64_t res = 0;
    for (int64_t i : arr) {
        res += i;
    }
    return res;
}

但是如果不让用 uint64（虽然这个限制没有道理），也是有办法的。

我们可以用双指针，指针 i 只找正数，指针 j 只找负数。求和过程中，sum 是正数就和 j 指向的负数相加，否则和 i 指向的正数相加。

int64_t sum(std::vector<int64_t> arr) {
    size_t i = 0;
    size_t j = 0;
    int64_t res = 0;

    while (true) {
        while (i < arr.size() && arr[i] <= 0) {
            i++;
        }
        while (j < arr.size() && arr[j] >= 0) {
            j++;
        }

        if (i == arr.size() && j == arr.size()) {
            break;
        }

        if (res > 0 || i == arr.size()) {
            res += arr[j];
            j++;
        } else {
            res += arr[i];
            i++;
        }
    }
    return res;
}