LeetCode第15,16,18题:3Sum, 3Sum Closest and 4Sum总结

ToC

题目一 3Sum
题目二 3Sum Closest
题目三 4Sum
思路和题解(Python)

这三道题明显是一家子，放到一起。。。

题目一 3Sum

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:
Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
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)

大意：给定一个有n个整数的数组S，数组中是否存在元素a, b, c使得a + b + c = 0? 找出所有的组合。

题目二 3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

大意：给定一个有n个整数的数组S和一个给定的目标值tatget，找出数组中三个数a, b, c，使得三个数之和a + b + c最接近target，输出这个和。

题目三 4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:
Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
The solution set must not contain duplicate quadruplets.

For example, given array S = {1 0 -1 0 -2 2}, and target = 0.
A solution set is:
(-1, 0, 0, 1)
(-2, -1, 1, 2)
(-2, 0, 0, 2)

大意：同题目一，和题目一唯一的不同是从三个数变成了四个数。

思路和题解(Python)

思路一 (3Sum)

其实，3sum这道题也是和leetcode第一题Two Sum类似的，回顾Two Sum这道题，发现，可以利用哈希的思想，创建一个数组/map（python就可以是dict）把O( n^3 )的复杂度降为( n^4 )。

这里把这种方法用dict实现，具体思路是：
1. 先遍历所给数组，以数为key，数出现的次数为value，创建一个dict；
2. 然后两层循环选定前两个数a, b（O( n^2 )），进行常数查找(0 – a – b)是否存在字典中，若存在，则将这个三元组添加到待返回的list变量ret中。

需要注意两点：
1. 注意选定前两个数时，暂时将对应的count值-1；
2. 注意将符合条件的组合添加到ret前，检查ret中是否存在有重复的组合。

代码如下：

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ret = []
        dict_num = {} #dict_num[num] = count
        for value in nums:
            if value in dict_num:
                dict_num[value] += 1
            else:
                dict_num[value] = 1
        for value in dict_num:
            dict_num[value] -= 1
            for value2 in dict_num:
                dict_num[value2] -= 1
                if dict_num[value2] < 0:
                    continue
                value3 = 0 - value2 - value
                if value3 in dict_num and dict_num[value3] > 0:
                    tmp_list = sorted([value, value2, value3])
                    if tmp_list not in ret: 
                        ret.append(sorted(tmp_list))
                dict_num[value2] += 1
            dict_num[value] += 1
        return ret

class Solution(object):

def threeSum(self, nums):

"""

:type nums: List[int]

:rtype: List[List[int]]

"""

ret = []

dict_num = {} #dict_num[num] = count

for value in nums:

if value in dict_num:

dict_num[value] += 1

else:

dict_num[value] = 1

for value in dict_num:

dict_num[value] -= 1

for value2 in dict_num:

dict_num[value2] -= 1

if dict_num[value2] < 0:

continue

value3 = 0 - value2 - value

if value3 in dict_num and dict_num[value3] > 0:

tmp_list = sorted([value, value2, value3])

if tmp_list not in ret:

ret.append(sorted(tmp_list))

dict_num[value2] += 1

dict_num[value] += 1

return ret

思路二 (3Sum, 3Sum Closest and 4Sum)

但是，当我再想用这种思路解决问题二(3Sum Closest)时，就会发现目标并不是一个定值，所以查表确定是否符合条件的思路就行不通了，因为这道题是让我们解决最优的问题，而不是确切数值的问题。

所以经过百度发现，其实这类问题还可以个用另一种方法，步骤如下：
1. 将所给数组排序
2. 定义两个指向最小数和最大数的”游标“，两边移动”游标“向里逼近，逐步找到目标值

由于这种遍历将两个”游标”，放到一趟进行，向中间逼近，所以会将复杂度降为O( n^2 )

这种思路需要注意的是：
因为没有了上一思路的dict或者map来记录数字出现的次数，所以消除可能出现重复组合需要用到一个消除相同值(remove duplicates)的循环的技巧，详见代码。

用这种思路解决问题一(3Sum)的代码如下：

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ret = []
        nums.sort()
        if len(nums) < 3:
            return ret
        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            i_left, i_right = i + 1, len(nums) - 1
            target_sum = -nums[i]
            while i_left < i_right:
                test_sum = nums[i_left] + nums[i_right]
                if test_sum < target_sum:
                    i_left += 1
                elif test_sum > target_sum:
                    i_right -= 1
                else:
                    ret.append([nums[i], nums[i_left], nums[i_right]])
                    while i_left < i_right and nums[i_left] == nums[i_left + 1]:
                        i_left += 1
                    while i_right > i_left and nums[i_right] == nums[i_right - 1]:
                        i_right -= 1
                    i_left += 1
                    i_right -= 1
        return ret

class Solution(object):

def threeSum(self, nums):

"""

:type nums: List[int]

:rtype: List[List[int]]

"""

ret = []

nums.sort()

if len(nums) < 3:

return ret

for i in range(len(nums) - 2):

if i > 0 and nums[i] == nums[i-1]:

continue

i_left, i_right = i + 1, len(nums) - 1

target_sum = -nums[i]

while i_left < i_right:

test_sum = nums[i_left] + nums[i_right]

if test_sum < target_sum:

i_left += 1

elif test_sum > target_sum:

i_right -= 1

else:

ret.append([nums[i], nums[i_left], nums[i_right]])

while i_left < i_right and nums[i_left] == nums[i_left + 1]:

i_left += 1

while i_right > i_left and nums[i_right] == nums[i_right - 1]:

i_right -= 1

i_left += 1

i_right -= 1

return ret

对于问题二(3Sum Closet)，答题思路是相同的我们只需适当修改上题的代码，在每层循环外更新一个最小相差值（这里分别为closet和sub_closet），并适当优化（比如当相差0时，可以直接return）

用这种思路解决问题二(3Sum Closet)的代码如下：

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums.sort()
        closet = sys.maxint
        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            i_left, i_right = i + 1, len(nums) - 1
            sub_closet = sys.maxint
            while i_left < i_right:
                test_sum = nums[i] + nums[i_left] + nums[i_right]
                if test_sum < target:
                    i_left += 1
                elif test_sum > target:
                    i_right -= 1
                else:
                    return test_sum
                if sub_closet > abs(test_sum - target):
                    sub_closet = abs(test_sum - target)
                    sub_closet_sum = test_sum
            else:
                if sub_closet < closet:
                    closet = sub_closet
                    closet_sum = sub_closet_sum
        return closet_sum

class Solution(object):

def threeSumClosest(self, nums, target):

"""

:type nums: List[int]

:type target: int

:rtype: int

"""

nums.sort()

closet = sys.maxint

for i in range(len(nums) - 2):

if i > 0 and nums[i] == nums[i-1]:

continue

i_left, i_right = i + 1, len(nums) - 1

sub_closet = sys.maxint

while i_left < i_right:

test_sum = nums[i] + nums[i_left] + nums[i_right]

if test_sum < target:

i_left += 1

elif test_sum > target:

i_right -= 1

else:

return test_sum

if sub_closet > abs(test_sum - target):

sub_closet = abs(test_sum - target)

sub_closet_sum = test_sum

else:

if sub_closet < closet:

closet = sub_closet

closet_sum = sub_closet_sum

return closet_sum

对于问题三(4Sum)，不管我们通过上述哪种思路，都只能再在原来复杂度的基础上*n，即复杂度为O( n^3 )，这里的代码，还是用游标指针向中间逼近的方法，只要在3Sum的代码加一层循环，就可以得到本题的代码：

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        if len(nums) < 4:
            return []
        nums.sort()
        ret = []
        for i1 in range(len(nums) - 3):
            if i1 > 0 and nums[i1] == nums[i1 - 1]:
                continue
            target_1 = target - nums[i1]
            nums_1 = nums[i1 + 1:]
            for i2 in range(len(nums_1) - 2):
                if i2 > 0 and nums_1[i2] == nums_1[i2 - 1]:
                    continue
                target_2 = target_1 - nums_1[i2]
                i_left, i_right = i2 + 1, len(nums_1) - 1
                while i_left < i_right:
                    test = nums_1[i_left] + nums_1[i_right]
                    if test < target_2:
                        i_left += 1
                    elif test > target_2:
                        i_right -= 1
                    else:
                        ret.append([nums[i1], nums_1[i2], nums_1[i_left], nums_1[i_right]])
                        while i_left < i_right and nums_1[i_left] == nums_1[i_left + 1]:
                            i_left += 1
                        while i_right > i_left and nums_1[i_right] == nums_1[i_right - 1]:
                            i_right -= 1
                        i_left += 1
                        i_right -= 1
        return ret

class Solution(object):

def fourSum(self, nums, target):

"""

:type nums: List[int]

:type target: int

:rtype: List[List[int]]

"""

if len(nums) < 4:

return []

nums.sort()

ret = []

for i1 in range(len(nums) - 3):

if i1 > 0 and nums[i1] == nums[i1 - 1]:

continue

target_1 = target - nums[i1]

nums_1 = nums[i1 + 1:]

for i2 in range(len(nums_1) - 2):

if i2 > 0 and nums_1[i2] == nums_1[i2 - 1]:

continue

target_2 = target_1 - nums_1[i2]

i_left, i_right = i2 + 1, len(nums_1) - 1

while i_left < i_right:

test = nums_1[i_left] + nums_1[i_right]

if test < target_2:

i_left += 1

elif test > target_2:

i_right -= 1

else:

ret.append([nums[i1], nums_1[i2], nums_1[i_left], nums_1[i_right]])

while i_left < i_right and nums_1[i_left] == nums_1[i_left + 1]:

i_left += 1

while i_right > i_left and nums_1[i_right] == nums_1[i_right - 1]:

i_right -= 1

i_left += 1

i_right -= 1

return ret

JciX ~

LeetCode第15,16,18题:3Sum, 3Sum Closest and 4Sum总结

题目一 3Sum

题目二 3Sum Closest

题目三 4Sum

思路和题解(Python)

思路一 (3Sum)

思路二 (3Sum, 3Sum Closest and 4Sum)

相关

发表回复取消回复

题目一 3Sum

题目二 3Sum Closest

题目三 4Sum

思路和题解(Python)

思路一 (3Sum)

思路二 (3Sum, 3Sum Closest and 4Sum)

相关

发表回复 取消回复

发表回复取消回复