Share my three simple python solutions, each getting faster than previous one


  • -2
    D

    I list three solutions here, each is improved based on previous one. The first one is very straight forward, but a bit slow (around 600ms!)
    The idea is:

    1. use set to remove duplicates.

    2. two level loops with early terminators (otherwise TLE).
      Time complexity is O(n^3), since list.index() is used to find the target

      class Solution:
      # @param {integer[]} nums
      # @return {integer[][]}
      def threeSum(self, nums):
      # use set to remove duplicate
      ans = set()
      nums.sort()
      for i in range(len(nums)-2):
      # once outer loop is bigger than 0, we are done
      if nums[i] > 0:
      break;
      for j in range(i+1, len(nums)-1):
      # once inner loop is bigger one half the absolute value of outer loop number, done
      if nums[j] > -nums[i] // 2:
      break
      target = -(nums[i] + nums[j])
      try:
      index = nums[j+1:].index(target)
      ans.add((nums[i], nums[j], target))
      except:
      pass
      return list(ans)

    The second one uses two indicators (prevOuter and preInner) to remove duplicates. Thus we can use list to store the result directly. Time complexity is still O(n^3), but running time is reduced to 220ms!

    class Solution:
        # @param {integer[]} nums
        # @return {integer[][]}
        def threeSum(self, nums):
            ans = []
            nums.sort()
            # use preOuter to remove redudant nums[i]
            prevOuter = None
            for i in range(len(nums)-2):
                # once outer loop is bigger than 0, we are done
                if nums[i] > 0:
                    break;
                if nums[i] == prevOuter:
                    continue
                prevOuter = nums[i]
                # use preInner to remove redudant nums[j]
                prevInner = None
                for j in range(i+1, len(nums)-1):
                    # once inner loop is bigger one half the absolute value of outer loop number, done
                    if nums[j] > -nums[i] // 2:
                        break
                    if nums[j] == prevInner:
                        continue
                    prevInner = nums[j]
                    target = -(nums[i] + nums[j])
                    try:
                        index = nums[j+1:].index(target)
                        ans.append([nums[i], nums[j], target])
                    except:
                        pass
    
            return ans
    

    Now we will reduce time complexity by using dictionary (hash map) to store the index of each numbers.
    Note that we only need to store the last index for duplicates. The time complexity is O(n^2) and running time below 200ms.

    class Solution:
        # @param {integer[]} nums
        # @return {integer[][]}
        def threeSum(self, nums):
            ans = []
            nums.sort()
            index = {}
            # store the last index of a number in the sorted array
            for i in range(len(nums)):
                index[nums[i]] = i
    
            # use preOuter to remove redudant nums[i]
            prevOuter = None
            for i in range(len(nums)-2):
                # once outer loop is bigger than 0, we are done
                if nums[i] > 0:
                    break;
                if nums[i] == prevOuter:
                    continue
                prevOuter = nums[i]
                # use preInner to remove redudant nums[j]
                prevInner = None
                for j in range(i+1, len(nums)-1):
                    # once inner loop is bigger one half the absolute value of outer loop number, done
                    if nums[j] > -nums[i] // 2:
                        break
                    if nums[j] == prevInner:
                        continue
                    prevInner = nums[j]
                    target = -(nums[i] + nums[j])
                    if index.get(target, 0) > j:
                        ans.append([nums[i], nums[j], target])
    
            return ans

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.