The provided solution runs in O(n^2) time. Is this optimal, or can we solve this in just O(nlogn)?
from collections import Counter
def find_sum_of_three(nums, target):
counter = Counter(nums)
n = len(nums)
nums.sort()
lo, hi = 0, n - 1
while lo < hi:
lo_num = nums[lo]
hi_num = nums[hi]
counter[lo_num] -= 1
counter[hi_num] -= 1
need = target - lo_num - hi_num
if counter[need] > 0:
return True
elif need >= hi_num:
lo += 1
else:
hi -= 1
counter[lo_num] += 1
counter[hi_num] += 1
return False
Course: Grokking Coding Interview Patterns in Python - AI-Powered Learning for Developers
Lesson: Solution: Sum of Three Values - Grokking Coding Interview Patterns in Python