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.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
Example 2:
Input: nums = [0,1,1]
Output: []`
Explanation: The only possible triplet does not sum up to 0.
Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.
I wrote my own version, but in the last tests I get a problem with execution time. At the same time, it seems to me that I broke the problem down into its component parts quite well and optimized them.
class Solution(object):
def threeSum(self, nums):
# I divide the list into positive and negative numbers
less_nums = sorted(list(set(filter(lambda x: x < 0, nums))))
more_nums = sorted(list(set(filter(lambda x: x > 0, nums))))
complete = []
# I get all possible options in the format [-n, 0, n]
if 0 in nums:
complete = map(lambda y: [y, 0, -y], filter(lambda x: -x in more_nums, less_nums))
# I get all options in the format [n, n, 2n]
even_nums = filter(lambda y: y % 2 == 0 and y != 0, list(set(nums)))
map(lambda num: complete.append(sorted([-(num / 2), -(num / 2), num])), filter(lambda num: -(num / 2) in nums and len(filter(lambda u: u == -(num / 2), nums)) > 1, even_nums))
# and I get all the other possible options, both with positive numbers and with negative ones
for plus_num in more_nums:
for min_num in filter(lambda z: -z < plus_num, less_nums):
if (-(plus_num + min_num) in less_nums) and (-(plus_num + min_num) != min_num) and not(sorted([min_num, -(plus_num + min_num), plus_num]) in complete):
complete.append(sorted([min_num, -(plus_num + min_num), plus_num]))
for min_num in less_nums:
for plus_num in filter(lambda z: -z > min_num, more_nums):
if (-(min_num + plus_num) in more_nums) and (-(min_num + plus_num) != plus_num) and not(sorted([min_num, -(min_num + plus_num), plus_num]) in complete):
complete.append(sorted([min_num, -(min_num + plus_num), plus_num]))
# at the end I also check the option when there are three zeros in the list
if len(filter(lambda x: x == 0, nums)) >= 3:
complete.append([0, 0, 0])
return complete
My question is exactly - WHY IS IT SLOW? I cant understand why all use While. I know, that filter is faster than ussualy cycles, but anw
I don't understand why this solution works faster and passes all tests:
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
ans = []
n = len(nums)
i = 0
while i < n:
if nums[i] > 0: break # Since arr[i] <= arr[l] <= arr[r], if arr[i] > 0 then sum=arr[i]+arr[l]+arr[r] > 0
l = i + 1
r = n - 1
while l < r:
sum3 = nums[i] + nums[l] + nums[r]
if sum3 == 0:
ans.append([nums[i], nums[l], nums[r]])
while l+1 < n and nums[l+1] == nums[l]: l += 1 # Skip duplicates nums[l]
l += 1
r -= 1
elif sum3 < 0: l += 1
else: r -= 1
while i+1 < n and nums[i+1] == nums[i]: i += 1 # Skip duplicates nums[i]
i += 1
return ans