将所有 存入数组 ,将所有 存入数组 。两个数组的长度均为 。即使不同下标对产生相同的和,也要分别存入。
将两个数组按升序排序。考察 中未处理的最小值 和 中未处理的最大值 。若 ,则 与 中任何剩余值之和都为负,因此向前移动 一侧。若 ,则 与 中任何剩余值之和都为正,因此移动 一侧。
若 ,设两侧连续等于 和 的元素个数分别为 。从两段中各选一个元素的 种方案均满足条件。将这一数量计入答案并跳过两段。每个值只能与其相反数配对,因此不会重复计数。
时间复杂度为 ,空间复杂度为 。四个输入值之和可用 32 位有符号整数表示。出现次数的乘积及答案可能达到 ,必须使用 64 位整数计算。
Solution written by GPT