Ttyjfyk

I tried a binary solution to 3Sum problem in LeetCode:

Given an array nums of $n$ integers, are there elements $a$, $b$, $c$ in nums such that $a + b + c = 0$? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
 [-1, 0, 1],
 [-1, -1, 2]
]

Ｍy plan: divide and conquer threeSum to

1. an iteration


2. and a two_Sum problem.


3. break two_Sum problem to
   
   
   1. a loop
   
   
   2. binary search
   
   

The complexity is: $O(n^2logn)$.

 class Solution:
 """
 Solve the problem by three module funtion
 threeSum
 two_sum
 bi_search 
 """
 def __init__(self):
 self.triplets: List[List[int]] = []

 def threeSum(self, nums, target=0) -> List[List[int]]:
 """
 :type nums: List[int]
 :type target: int 
 """
 nums.sort() #sort for skip duplicate and binary search 

 if len(nums) < 3:
 return []

 i = 0
 while i < len(nums) - 2:
 complement = target - nums[i]

 self.two_sum(nums[i+1:], complement)
 i += 1 #increment the index 
 while i < len(nums) -2 and nums[i] == nums[i-1]: #skip the duplicates, pass unique complement to next level.
 i += 1 

 return self.triplets


 def two_sum(self, nums, target):
 """
 :type nums: List[int]
 :tppe target: int
 :rtype: List[List[int]]
 """
 # nums = sorted(nums) #temporarily for testing.
 if len(nums) < 2:
 return [] 

 i = 0
 while i < len(nums) -1:
 complement = target - nums[i]

 if self.bi_search(nums[i+1:], complement) != None:

 # 0 - target = threeSum's fixer 
 self.triplets.append([0-target, nums[i], complement]) 
 i += 1

 while i < len(nums) and nums[i] == nums[i-1]:
 i += 1 

 def bi_search(self, L, find) -> int:
 """
 :type L: List[int]
 :type find: int 
 """
 if len(L) < 1: #terninating case 
 return None 
 else:
 mid = len(L) // 2
 if find == L[mid]:
 return find 

 if find > L[mid]:
 upper_half = L[mid+1:]
 return self.bi_search(upper_half, find)
 if find < L[mid]:
 lower_half = L[:mid] #mid not mid-1
 return self.bi_search(lower_half, find)

I ran it but get the report

Status: Time Limit Exceeded

Could you please give any hints to refactor?

Is binary search is an appropriate strategy?

Your bi_search() method is recursive. It doesn’t have to be. Python does not do tail-call-optimization: it won’t automatically turn the recursion into a loop. Instead of if len(L) < 1:, use a while len(L) > 0: loop, and assign to (eg, L = L[:mid]) instead of doing a recursive call.

Better: don’t modify L at all, which involves copying a list of many numbers multiple times, a time consuming operation. Instead, maintain a lo and hi index, and just update the indexes as you search.

Even better: use a built in binary search from import bisect.