java - 查找整数数组的总和而不会溢出

给定一个整数数组(正数和负数)，每个整数最多具有K位(加上符号位)，并且已知数组中所有整数之和也最多具有K位(加上符号位) 。设计一种算法，该算法计算数组中的整数和，所有中间和也最多具有K位(加上符号位)。 [提示:查找应按什么顺序添加正数和负数]。

这是来自面试材料的问题，而不是家庭作业

我实际上是在考虑创建两个单独的数组，一个用于正数，另一个用于负数，对它们进行排序，然后将两者都相加，以使大多数负数与大多数正数相加……但这似乎具有O(nlogn)时间复杂度(排序)和O(n)空间复杂度>请帮助!

最佳答案

首先请注意，即使让立即结果溢出，如果可以表示最终结果，也将始终是正确的。这是因为在包括Java在内的大多数语言中，任何大小的整数类型都像循环组一样起作用(不包括C(整数溢出是未定义的行为，而C#则可能引发溢出异常))。

如果您仍想防止溢出，请按照以下步骤在原地和线性时间内执行:

将数组原位拆分为否定条目(按任何顺序)和其肯定条目(按任何顺序)。零可以在任何地方结束。换句话说，在枢轴为零的情况下执行一个快速排序步骤。

让ni指向数组的开始(负条目位于其中)。

让pi指向数组的末尾。

令sum为零。

而pi >= ni

如果sum为负

将arr[pi]添加到sum中。

如果arr[pi]为负(我们用尽了正的加数)并且sum为正(发生了溢出)，则结果溢出。

递减pi

else

将arr[ni]添加到sum中。

如果arr[ni]为正，而sum为负，则结果溢出。

递增ni。

最后，检查sum是否具有超过K位。如果是这样，则声明结果溢出。