I have been doing LeetCode and tackled the problem of the 3Sum and first I tried to do a O(nlogn) solution and after seeing the proposed solution I see that the solution is $O(n^2)$ or $O(n^2 \times \log n)$ and not only that but the problem is a highly researched topic so I don't think I found a better solution but can't see why my approach wouldn't work, can use help to figure it out.
The problem is the following
Find three numbers in an array such that $a + b + c = t$,
the LeetCode problem is slightly different in which you need to find the closest sum.
My code is the following:
- Sort the array.
j= last element of array
arr[m] == target - arr[i] - arr[j], if such
mdoesn't exist return
arr[m]is the closest.
arr[i] + arr[m] + arr[j] == targetthen your finished.
arr[i] + arr[m] + arr[j] < targetthen add 1 to
ielse subtract 1 form
- Repeat 3 → 5 until
j - i == 2
- Return the best found
The logic in step 5 is that if the solution found is less than the target then we should increase
i such that our next guess is bigger.
def binSearch(arr, s, e, t): m = (s + e) // 2 r = m d = 9999 while s <= e: m = (s + e) // 2 if arr[m] == t: return m elif arr[m] > t: e = m - 1 else: s = m + 1 if d > abs(t - arr[m]): d = abs(t - arr[m]) r = m return r class Solution: def threeSumClosest(self, nums, target: int) -> int: nums.sort() s = 0 e = len(nums) - 1 minn = 999999 t = () while e - s >= 2: left = nums[s] right = nums[e] remaining = target - (left + right) m = binSearch(nums, s + 1, e - 1, remaining) middle = nums[m] r = left + middle + right # print("i's: ", (s,m,e)) # print("values: ", (nums[s], nums[m], nums[e])) # print("r", r) # print("**************") if r == target: return r elif r < target: s += 1 else: e -= 1 if abs(target - r) < minn: minn = abs(target - r) t = r return t