Home 15. Three Sum
Post
Cancel

15. Three Sum

Leetcode #15


題目描述

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

白話文運動

給定一維數列 nums,找到所有以三個數字的總和恰好為零的不重複組合。

題目限制

  • 0 <= nums.length <= 3000
  • 105 <= nums[i] <= 105

具體測資

Case 1

1
2
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Case 2

1
2
Input: nums = []
Output: []

Case 3

1
2
Input: nums = [0]
Output: []

解題想法

暴力法

  1. 使用 DFS 遍歷所有三元組組合,一一確認總合是否為零。不過,會遇到 TLE (Time Limit Exceed) 問題。

排序 + 雙指標

  1. 先排序一維數列。

  2. 遍歷該數列,鎖定每個數,使其當一次主角。接著,使用雙指標遍歷尋找其他兩個數。


實際解題

Sort + TwoPointers

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
29
30
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:

        before_ret = set()
        
        ## Using sort (O(NlogN)) can save time (Brute force: O(N^3))
        nums = sorted(nums)
        
        ## One Target Num and Two Pointers
        for i, num in enumerate(nums):

            left = i + 1
            right = len(nums) - 1
            
            while left < right:

                three_sum = num + nums[left] + nums[right]
                
                if three_sum == 0:
                    before_ret.add((num, nums[left], nums[right]))
                    left += 1
                    right -= 1
                
                elif three_sum > 0:
                    right -= 1
                
                else:
                    left += 1
        
        return list(before_ret)

複雜度分析

  • 時間複雜度: O(NlogN + N2) = O(N2)
  • 空間複雜度: O(1) 不考慮回傳時的陣列

討論區

This post is licensed under CC BY 4.0 by the author.