leetcode2/3/4数之和的解法比较python_哈希和双指针（sort的时空复杂度）

1. 两数之和题目

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。

示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]

提示：
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案
进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

思路和代码
1.二数之和的暴力法
这个就是两层for循环嘛，时间复杂度O（n2），空间复杂度O（1）。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i+1, n):
                if nums[i] + nums[j] == target:
                    return [i,j]
1
2
3
4
5
6
7

2.两数之和的哈希法
这个比较有意思，就是一层遍历，然后判断target-nums[i]是不是在字典中，在的话返回结果。把当前值加到字典中，key是当前遍历的值，value是下标i。因为哈希表的增删改查的时间复杂度都是O(1),所以用哈希表的时间复杂度是O（n），空间复杂度是O（n）。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        dic = {}
        for i in range(n):
            if target - nums[i] in dic:
                return [i,dic[target-nums[i]]]
            dic[nums[i]] = i
1
2
3
4
5
6
7
8

3.两数之和的双指针法
先排序，然后前后两个指针相加和target比较，比target大就把后面的指针往前移动，否则就把前面的指针往后移动。注意，因为返回的是下标，所以开始的时候利用元组把值和元组组合到一起到再排序，排序的时间复杂度是O（nlogn），空间复杂度是O（n）。

还有思路就是排序后，对当前值遍历，在后面利用二分查找（也是利用两个指针）。这个时间复杂度也是O(nlogn),空间复杂度是O（n）。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        left, right = 0,n-1
        concate = []
        for i,v in enumerate(nums):
            concate.append((i,v))
        concate.sort(key= lambda x:(x[1],x[0]))
        while left < right:
            if concate[left][1] + concate[right][1] == target:
                return [concate[left][0], concate[right][0]]
            elif concate[left][1] + concate[right][1] > target:
                right -= 1
            else:
                left += 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

15. 三数之和

题目
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：
3 <= nums.length <= 3000
-105 <= nums[i] <= 105

思路和代码
暴力没啥可说的，三层for循环，肯定也通过不了。

想说的还是哈希法和双指针法。

1.三数之和的哈希法

先两层for循环，计算两数的和two_sum,然后计算-two_sum是否在哈希表中。这两天在听左神的课，说到c++中哈希表有两种，map是有键值对，set是只有key。对应到python中，字典是有键值对，set也是只有key。（我之前一直以为python中只有字典是哈希表。其实现在还是有点点迷糊。）这题使用的是set。

由于这题要求不能有重复的列表，所以要对答案去重。这就涉及到代码的细节，我参考的是代码随想录的题解，看懂个七七八八。

第一次去重是对第一个for循环（也就是第一个数）进行判断，如果第一个数大于0（后面不可能构成和为0的三元组），直接跳过，if i > 0 and nums[i]==nums[i-1]也进行跳过。

第二次去重是对第二个值去重，if j > i+2 and nums[j] == nums[j-1] and nums[j-1] == nums[j-2]就跳过。这个我理解了怪好一会。例如[0,0,0,0,0]，如果不进行这句的判断，就会返回三个[0,0,0]。必须要判断当前值与前一个值相等且当前值的前一个值和当前值前一个的前一个值相等才跳过，不能判断当前值和前一个值相等就跳过，这样会漏值，如[-2,1,1]。

第三次去重是对第三个值去重，如果已经存在第三个数在集合中，且三数之和为0，那么要把这个数从集合中删去，不然再次判断的时候还是会将其加到结果集合中。如[-2,0,0,2,2],如果不对第三个数去重的话，就会返回两个[-2,2,0]。

时间复杂度是O（n2），空间复杂度是O（n）。

代码：

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        res = []
        nums.sort()
        for i in range(n-2):
            if nums[i] > 0:
                continue
            # 对第一个数去重
            if i > 0 and nums[i] == nums[i-1]:
                continue
            s = set()
            for j in range(i+1,n):
                # 对第二个数去重
                if j > i+2 and nums[j] == nums[j-1] and nums[j-1] == nums[j-2]:
                    continue
                two_sum = nums[i] + nums[j]
                target = -two_sum
                if target in s:
                    res.append([nums[i], nums[j], target])
                    # 对第三个数去重
                    s.remove(target)
                s.add(nums[j])
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

2.三数之和的双指针法

先对nums进行排序，第一个for循环对每一个值遍历。target值为-nums[i]。然后两个指针left和right，如果两数之和大于target，right往左，如果两数之和小于target，left往右。等于的话就加入结果中，并且left+1,right - 1。

注意里面的去重处理，在while循环里，如果nums[left+1] == nums[left], 那么left继续加一。如果nums[right-1] == nums[right]，right继续减一。

时间复杂度是O（n2），空间复杂度是O（n）。

代码：

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        n = len(nums)  
        nums.sort()
        c = 0
        for i in range(n-2):
            if nums[i] > 0:
                continue
            if i>0 and nums[i-1] == nums[i]:
                continue
            left, right = i+1,n-1
            targrt = - nums[i] 
            while left < right:
                if nums[left] + nums[right] > targrt:
                    right -= 1
                elif nums[left] + nums[right] < targrt:
                    left += 1
                else:
                    res.append([nums[i], nums[left],nums[right]])
                    while left < right and nums[left] == nums[left+1]:
                        left += 1
                    while left < right and nums[right] == nums[right-1]:
                        right -= 1
                    left += 1
                    right -= 1
        return res          
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

16. 最接近的三数之和

题目
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例 1：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
示例 2：

输入：nums = [0,0,0], target = 1
输出：0

提示：

3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-104 <= target <= 104

思路和代码

和三数之和的双指针法一个思路，一个for循环，然后两个前后指针，然后三数之和和target的大小，比target大right-1，小则left+1。此外，判断三数和和target的差值，保留差值小的三数之和。时间复杂度是O（n2）,空间复杂度O（logn）？

代码：

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        res = float("inf")
        for i in range(n):
            left, right = i+1, n-1
            while left < right:
                three_sum = nums[i] + nums[left] + nums[right]
                if three_sum > target:
                    right -= 1
                elif three_sum < target:    
                    left += 1
                else:
                    return target
                if abs(three_sum - target) < abs(res - target):
                    res = three_sum
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

18. 四数之和

题目
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。

示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

思路和代码

1.四数之和的哈希法

三数之和的哈希法或双指针法是把暴力的时间复杂度从O（n3）降到O（n2）。四数之和也是一样，通过哈希法或双指针法是把暴力的时间复杂度从O（n4）降到O（n3）。

我们知道哈希的增删改查的时间复杂度是O(1)，按左神的说法就是性能是逆天的。那这里面如果用哈希的话，就是先来三层for循环，然后查找最后一个数在不在哈希表里（O（n3））。三数之和的哈希不就是先两层for循环，然后判断第三个数在不在哈希里嘛（O（n2））。和三数之和同样，四数之和也需要涉及到答案去重的问题。

我们来回忆一下，三数之和哈希表怎么去重的？

对第一个去重就是判断和前面的值是不是相等，但要注意i>0,也即判断条件是if i>0 and nums[i] == nums[i-1]。还有就是三数之和为0，如果第一个值已经大于零了也进行跳过，这个属于剪枝。

对第二个数去重的判断句是if j> i+2 and nums[j] == nums[j-1] and nums[j-1] == nums[j-2]。最后对第三个数去重，是判断第三个数是不是在集合中，在的话把结果加入到结果集中同时把第三个数从集合中删除。

那四数之和怎么去重？这个代码写的很神奇啊，这是怎么想到的啊！

哈希表中键值对，key存放的就是每个值，value存放的是每个value出现的次数。然后三层for循环后，不是要在哈希表里找第四个数在不在嘛。先判断在不在，在的话再比较dic[第四个数]的值和count的值，这个count是前三个值和这个要求的第四个值相等的个数。那如果dic[第四个数] > count,不就说明nums中还存在其他的第四个数嘛，如果小于的话，就说明这第四个数虽然存在，但是和前三个数中的某一个或几个重了。

这这这，这一般人谁能想到啊…

代码：

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        n = len(nums)
        dic = {}
        for k in nums:
            if k in dic:
                dic[k] += 1
            else:
                dic[k] = 1
        ans = set()
        for i in range(n):
            for j in range(i+1,n):
                for k in range(j+1,n):
                    cur_target = target - (nums[i] + nums[j] + nums[k])
                    if cur_target in dic:
                        count = (cur_target == nums[i]) + (cur_target==nums[j]) + (cur_target == nums[k])
                        if dic[cur_target] > count:
                            ans.add(tuple(sorted((nums[i],nums[j],nums[k],cur_target))))
                        else:
                            continue
        return list(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.四数之和的双指针

双指针啊，就是在三数之和的外面再套一层for循环。两层for循环求前两个值two_sum，然后left和right指针，后面两数和为target-two_sum,则判断一些是否已经在结果集合中，不在就加入。left+1，right-1。后面两数和大于target-two_sum，right-1，否则left+1。此外，需要注意一些情况的去重和剪枝。

首先对第一个数剪枝，如果当前值已经大于target并且下一个值和target本身都大于0，终止循环。（-4，-1，0,0，target=-5，如果不判断其下一个值和target本身都大于零直接跳过那就会漏掉结果[-4,-1,0,0]，因为两个负数相加值会更小。）或者写成if nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target则break。如果当前值和最后三个数之和小于target则跳过本次循环。

然后对第一个数去重，和三数之和一样，if i>0 and nums[i] == nums[i-1]跳过。

接下来对第二个数进行剪枝和去重。此时nums[i]+ nums[j]作为一个整体，这个整体大于target且后面的一个值和target都大于零则终止本次循环。如果当前两数和和最后两个数和的依然小于target的话则跳过本次循环。去重的话，就是if j>i+1 and nums[j] == nums[j-1],（问，这里怎么不是if j> i+2 and nums[j] == nums[j-1] and nums[j-1] == nums[j-2]？好像懂又不多）。

最后双指针，两个while循环对第三个数和第四个数去重，和三数之和一样的。

时间复杂度O（n3）。空间复杂度官方说是O（logn）？ 我保持怀疑。 官方说法空间复杂度主要取决于排序额外使用的空间。此外排序修改了输入数组 nums，实际情况中不一定允许，因此也可以看成使用了一个额外的数组存储了数组 nums 的副本并排序，空间复杂度为 O(n)。”

怀疑什么？

python中自带的sort的时空复杂度是什么？这个问题困扰了我很久。

网上说这个sort不是简单的快排t使用的排序方式为TimeSort，TimeSort是结合了归并排序(merge sort)和插入(insert sort)排序的一种在实际应用中高效的排序算法。

最坏时间复杂度O(nlogn)，空间复杂度O(n)。既然空间复杂度是O（n），为什么官方说是O(logn)?

回顾：归并排序的时间复杂度是O（nlogn），空间复杂度是O（n），稳定排序算法。
插入排序的时间复杂度O（n2），空间复杂度是O（1），不稳定排序算法。

代码：

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        res = []
        n = len(nums)
        for i in range(n-3):
            # 对第一个数剪枝 终止整个循环
            # 剪枝-过大
            if nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target:
                break
            # 剪枝-过小
            # 当前值和最后三个数之和小于target则跳入下次循环 
            if nums[i] + nums[n-1] + nums[n-2] + nums[n-3] < target:
                continue

            # 对第一个数去重
            if i > 0 and nums[i] == nums[i-1]:
                continue
            for j in range(i+1,n-2):
                # 对第二个数剪枝 
                # 剪枝-过大
                if nums[i] + nums[j] + nums[j+1] + nums[j+2] > target:
                    break
                #剪枝- 过小
                # 当前两数和最后两个数之和小于target则跳入下次循环 
                if nums[i] + nums[j] + nums[n-1] + nums[n-2] < target:
                    continue
                #对第二个数去重
                if j> i + 1 and nums[j]==nums[j-1]:
                    continue
                two_sum = nums[i] + nums[j]
                two_target = target - two_sum
                left = j + 1
                right = n - 1
                while left < right:
                    if nums[left] + nums[right] > two_target:
                        right -= 1
                    elif nums[left] + nums[right] < two_target:
                        left += 1
                    else:
                        res.append([nums[i],nums[j],nums[left],nums[right]])
                        while left < right and nums[left] == nums[left+1]:
                            left += 1
                        while left < right and nums[right] == nums[right-1]:
                            right -= 1
                        left += 1
                        right -= 1
        return res

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49