leetcode15

Posted on | In

15. 3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + 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.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

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

Idea

  • two pointer
    firstly perform the sort operation

    1
    2
    3
    4
    5
    6
    7
    l, r = init1, init2
    if s(l, r) < target:
        l += 1
    elif s(l, r) > target:
        r -= 1
    else:
        ...

  • find next different number:

    1
    2
    3
    for i in range(len(nums)):
        if i > 0 and nums[i] == nums[i - 1]: # find next different num1
            continue

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ans = []
        nums = sorted(nums)
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i - 1]: # find next different num1
                continue
            # two pointers operations
            l, r = i + 1, len(nums) - 1
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if s < 0:
                    l += 1
                elif s > 0:
                    r -= 1
                else:
                    ans.append((nums[i], nums[l], nums[r]))
                    while l < r and nums[l] == nums[l + 1]: # find last same number as num2
                        l += 1
                    while l < r and nums[r] == nums[r - 1]: # find last same number as num3
                        r -= 1
                    l += 1 # find next different number
                    r -= 1 # find next different number
        return ans