O(n^2) Python Solution without Sort


  • 0
    L

    I have seen all the post and they all use sort first.
    Below is my AC solution without sort.

    class Solution(object):
    def threeSum(self, nums):
    """
    :type nums: List[int]
    :rtype: List[List[int]]
    """
    # time O(n^2), space O(1)
    result = []
    for i in range(len(nums)):
    lookup = {}
    for j in range(i+1, len(nums)):
    tmp = 0 - nums[j] - nums[i]
    if tmp in lookup:
    # to keep list sorted in order to remove duplicate
    if sorted([nums[i], tmp, nums[j]]) not in result:
    result.append(sorted([nums[i], tmp, nums[j]]))
    lookup[nums[j]] = j
    return result


  • 0
    P

    Very smart!
    it seems lookup[nums[j]] = j, here j is never used.

    perhaps we could use a set, like:

    lookup = set()
    lookup.add(nums[j])

    So the programs runs a bit faster.


Log in to reply
 

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