Hi I’m doing LeetCode and I struct this 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 * logn) 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 so I wan’t to see if you could help me 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.

Start with two pointers
i=0
andj= last element of array
 Use binary search between
i
andj
to findm
such thatarr(m) == target  arr(i)  arr(j)
, if suchm
doesn’t exist returnm
such thatarr(m)
is the closest.  If
arr(i) + arr(m) + arr(j) == target
then your finished.  Otherwise if
arr(i) + arr(m) + arr(j) < target
then add 1 toi
else subtract 1 formj
.
 Use binary search between

Repeat 3 > 5 until
j  i == 2

Return the best found
i,m,j
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.
problem https://leetcode.com/problems/3sumclosest/
Code:
def findPair(nums, s, e, t): # O(log n)
i = s
j = e
d = 9999999999
r1 = r2 = 0
while i < j:
val = nums(i) + nums(j)
if abs(t  val) < d:
d = abs(t  val)
r1, r2 = i, j
if val == t:
return (i, j)
elif val > t:
j = 1
else:
i += 1
return (r1, r2)
class Solution:
def threeSumClosest(self, nums, target: int) > int:
nums.sort()
s = 0
L = len(nums)
res = 0
d = 9999999999
for i in range(L2): # O(n)
j, k = findPair(nums, i + 1, L  1, target  nums(i))
val = nums(i) + nums(j) + nums(k)
if abs(target  val) < d:
d = abs(target  val)
res = val
return res
```