LeetCode 15 3Sum

Posted on | In | 阅读

T Sum问题的O(n)解决方法；

N Sum类的问题的一般解决方法；

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

1
2
3
4
5
6
7
8
9
> For example, given array S = [-1, 0, 1, 2, -1, -4],
>
> A solution set is:
> [
>   [-1, 0, 1],
>   [-1, -1, 2]
> ]
>
>

Two sum类问题，找两个数的和为一个定值的问题，如果直接使用二分查找，排序+查找或者在有序数组中直接查找的复杂度都是O(nlogn)，有的题卡复杂度的就过不去

Two Sum问题的一般做法

对无序数组进行排序后（若数组已经是有序的化则不需要排序），设置两个指针left、right指向数组的首尾，target是要查找的目标

  • 如果arr[left] + arr[right] == target，查找到了

  • 如果arr[left] + arr[right] > target，按照遍历的方式right往左移，right -= 1

  • 如果arr[left] + arr[right] < target，很显然right不需要再往左移动了，直接进入下一轮迭代，即left += 1，right不动

  • right不用像遍历一样回到最右边吗？不用。因为现在的arr[left]与right右边的数相加都是大于target的（不然right不会向左移），那么left再向右移动arr[left]只会更大，right也就不用再回到右边了

  • 最后注意下重复数字答案重复的问题

    Two Sum问题的这种解决方法排序+查找复杂度依然是O(nlogn)，但是主要是因为排序的消耗。如果题目已经给了有序的数列，那么复杂度将会降为O(n)

N Sum 问题

  • 对前几位进行遍历，对最后两维做Two Sum

Python 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
29
30
31
32
class Solution(object):  
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ans = []
        if len(nums) < 3:
            return []
        nums.sort()
        for i in range(len(nums) - 2):
            if nums[i] > 0:
                break
            if i > 0 and nums[i] == nums[i-1]:
                continue
            l = i+1
            r = len(nums)-1
            while l < r:
                if nums[i] + nums[l] + nums[r] > 0:
                    r -= 1
                elif nums[i] + nums[l] + nums[r] < 0:
                    l += 1
                else:
                    ans.append([nums[i], nums[l], nums[r]])
                    l += 1
                    while l < r and nums[l] == nums[l-1]:
                        l += 1
                    r -= 1
                    while l < r and nums[r] == nums[r+1]:
                        r -= 1
                    
        return ans