Leetcode: 3 Sum

3Sum | LeetCode OJ

The brute force method to solve this will take O(n³) time complexity. We will try sorting and searching instead.

1. Sort the input
2. Starting from left , for each unique (a, b) find -c in rest of the array
3. As the rest of array is sorted the search can be done in log(n) time

Remarks:

1. O(n*log n) + O(n²*log n) time complexity
2. Space complexity will depend on the number of solutions

from bisect import bisect_left

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        res = []
        l = len(nums)
        for i in range(l):
            if nums[i] > 0:
                break
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            for j in range(i + 1, l):
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                c = -nums[i] - nums[j]
                if self.binary_search(j + 1, l, nums, c):
                    res.append([nums[i], nums[j], c])
        return res
    def binary_search(self, low, high, nums, c):
        pos = bisect_left(nums, c, low, high)
        return True if pos != high and nums[pos] == c else False