15. 3Sum

# Medium

Two pointers problem + one fixed pointer.

One pointer starts from the beginning of the list, the other one starts from the end of the list. The fixed pointer represents the one of the three elements.

Solution:

1. Set one pointer i, from 0 to len(nums)-2

2. Set second pointer j, starting from i+1

3. Set third pointer k, starting from len(nunms)-1

4. sum = nums[i] + nums[j] + nums[k]

5. If sum == 0, add the three elements to result, and j ++ & k --; If sum > 0, k --; If sum < 0, j ++

6. Stop condition: while j < k.

7. In order to avoid duplication

   1. If nums[i] == nums[i-1], skip this index.

   2. Set result as set, set the list as a set before adding it to the result. Because nums has been sorted, so don't need to consider duplication.

Python

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        # edge case
        if len(nums) < 3:
            return []
        
        # regular case
        result = set()
        # sort the list
        nums2 = sorted(nums)
        for i in range(len(nums2)-2):
            if i > 0 and nums2[i] == nums2[i-1]:
                continue
            j = i + 1
            k = len(nums2) - 1
            while j < k:
                s = nums2[i] + nums2[j] + nums2[k]
                if s == 0:
                    temp = (nums2[i], nums2[j], nums2[k])
                    result.add(temp)
                    j += 1
                    k -= 1
                elif s > 0:
                    k -= 1
                else:
                    j += 1
                    
        return result

Time complexity = $O(n^2)$ (最内层把时间复杂度从 $n^2$ 到 $n$ ), space complexity = $O(1)$