I have a working solution for the 3Sum problem, but it doesn’t pass all the test cases because it “exceeds the time limit.” I passed 310 / 312 test cases on LeetCode, so I know it works. It’s just the last 2 test cases that it takes too long for.

Given an integer array nums, return all the triplets [nums[i],
nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] +
nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Here is my code:

def threeSum(nums):
    sol = []
    pos = 1
    nums.sort()

    def search(p, vals):
        l, r = 0, len(vals) - 1
        sols = []
        while l < p < r:
            if vals[l] + vals[p] + vals[r] == 0:
                sols.append([vals[l], vals[p], vals[r]])
                vals.pop(r)
                vals.pop(l)
                l, r = l, r - 2
                p -= 1
                continue
            if vals[l] + vals[p] + vals[r] > 0:
                r -= 1
            if vals[l] + vals[p] + vals[r] < 0:
                l += 1
        return sols

    while pos < len(nums) - 1:
        new_sol = search(pos, nums[:])
        for n in new_sol:
            if n not in sol:
                sol.append(n)
        pos += 1
    return sol

Can someone change my code to reduce the time complexity? Could you also describe what the time complexity of my current and the new code is? I want it to be my code, so I would appreciate it if it stayed similar to the one I provided and only had the necessary changes.