Three Sum

Return all the different triples of values from nums that add up to 0. Each triple is written in increasing order, there must be no repeated triple, and the list of triples is sorted (compare the first value, then the second, then the third). A value can be used as many times as it appears in nums, but only at different positions.

The starter code tries every set of three positions. It is correct but too slow for long lists. Make it fast.

Examples

Example 1

Input:

three_sum([-1, 0, 1, 2, -1, -4])

Output:

[[-1, -1, 2], [-1, 0, 1]]

The triples are [-1, -1, 2] and [-1, 0, 1].

Example 2

Input:

three_sum([0, 0, 0, 0])

Output:

[[0, 0, 0]]

Only one different triple: [0, 0, 0].

Constraints

• 0 <= len(nums) <= 1500
• -10**5 <= nums[i] <= 10**5