15-三数之和/18-四数之和

Leetcode题解
  1. 15、三数之和/18、四数之和
    1. 题目：
    2. 题解：

15、三数之和/18、四数之和

题目：

https://leetcode-cn.com/problems/3sum/

Uri4k4.png

题解：

​ 本题看懂题目后，第一反应就是三层循环遍历得出三元组的解。但必然会超时，并且还有一些小坑。比如，要求得出的三元组满足a+b+c=0且不能重复。如果是三层循环得出解后，再进行去重，相当于在O(N3)的时间复杂度上雪上加霜。

​ 首先考虑如何去重，就是将nums数组从小到大排序，然后每一层循环都判断一次当前nums[i]值是否等于上一次循环的值nums[i-1]，如果是直接跳过此次循环即可，但仅仅这样时间复杂度没有降下去。只能通过简化循环来降低时间复杂度。

​ 降低时间复杂度的方法：由于数组是从小到大排序，在不断的循环过程中每一层循环的数值都在增大，且条件要求是a+b+c=0，a+b越大，c就得越小才能满足条件，就可以使用类似双指针的方法，来将第二层和第三层循环简化为一层循环。在确定第一层循环a的值后，把b和c作为双指针来进行移动，b正常按照循环判断，c的指针则用while循环左移直到满足a+b+c<=0的条件。

​ 这样，第二层和第三层只需要走一趟就可以结束，成功将O(N3)简化到O(N2)。排序的时间复杂度是O(NlogN)，在渐进意义下小于前者，因此算法的总时间复杂度为 O(N^2)O(N2)。

总结：排序判断去重，找规律双指针降低时间复杂度。18、四数之和只需再加一层循环即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result = list()
        n = len(nums)
        nums.sort();
        for first in range(n-2):
            if first != 0 and nums[first] == nums[first-1]:
                continue
            third = n - 1
            for second in range(first + 1,third):
                if second != first + 1 and nums[second] == nums[second-1]:
                    continue
                while nums[first] + nums[second] + nums[third] > 0 and third > second:
                    third-=1
                if third == second:
                    break
                if nums[first] + nums[second] + nums[third] == 0:
                    result.append([nums[first],nums[second],nums[third]])
        return result

当前网速较慢或者你使用的浏览器不支持博客特定功能，请尝试刷新或换用Chrome、Firefox等现代浏览器