Put every sum in an array and every sum in an array . Each array has length . Include a separate entry for every index pair, even if several pairs give the same sum.
Sort both arrays in increasing order. Consider the smallest unprocessed value of and the largest unprocessed value of . If , pairing with any remaining value of still gives a negative sum, so advance on the side. If , pairing with any remaining value of gives a positive sum, so advance on the side.
If , let and be the lengths of the current runs of and . Every pairing between the runs gives a valid tuple. Add and skip both runs. A value can only be matched with its negation, so no tuple is counted twice.
The time complexity is and the space complexity is . A sum of four input values fits in a signed 32-bit integer. Use 64-bit integers for the product of the multiplicities and for the answer, which can reach .
Solution written by GPT