15.3Sum

Tags: [sort], [binary_search], [sortcut]

Com: {fb}

Link: https://leetcode.com/problems/3sum/\#/description

Given an arraySofnintegers, are there elementsa,b,cinSsuch thata+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.

For example, given array S = [-1, 0, 1, 2, -1, -4],

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

Solution: Sort, Binary Search, Shortcut

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if not nums or len(nums) < 3:
            return []

        nums.sort()

        result_set = set()
        result = []

        for i in xrange(len(nums) - 2):
            if i > 0 and nums[i - 1] == nums[i]:
                # The previous running has covered the all current cases,
                # so we can just skip this round.
                continue

            a = nums[i]
            left = i + 1
            right = len(nums) - 1

            while left < right:
                tmp_sum = a + nums[left] + nums[right]

                if tmp_sum == 0:
                    result_str = '{},{},{}'.format(a, nums[left], nums[right])
                    if result_str not in result_set:
                        result_set.add(result_str)
                        result.append([a, nums[left], nums[right]])

                    left = self.find_next(nums, left, 1)
                    right = self.find_next(nums, right, -1)
                elif tmp_sum > 0:
                    right -= 1
                else:
                    left += 1

        return result

    def find_next(self, nums, curr_index, direction):
        curr = nums[curr_index]
        while 0 <= curr_index < len(nums) and nums[curr_index] == curr:
            curr_index += direction

        return curr_index

Revelation:

• We use the following code to skip the cases we have calculated in the previous steps.

for i in xrange(len(nums) - 2):
    if i > 0 and nums[i - 1] == nums[i]:
        # The previous running has covered the all current cases,
        # so we can just skip this round.
        continue

• The reason why we didn't use 'find__next' function i the following blocks, is that it seems that if we use 'find__next' function in these two blocks will make the code more slow, which cannot leetcode AC.

elif tmp_sum > 0:
    right -= 1
else:
    left += 1

Note:

• Time complexity = O(n^2), n is the number of elements in give nums.