383. 赎金信

https://leetcode.cn/problems/ransom-note/

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1：

1
2
输入：ransomNote = "a", magazine = "b"
输出：false

示例 2：

1
2
输入：ransomNote = "aa", magazine = "ab"
输出：false

示例 3：

1
2
输入：ransomNote = "aa", magazine = "aab"
输出：true

提示：

  • 1 <= ransomNote.length, magazine.length <= 105
  • ransomNote 和 magazine 由小写英文字母组成

思路

  1. 把这题目当成生成者，消费者问题：ransomNote是消费者，它需要消费指定数量的指定字符；matezine是生产者
  2. ransomNote 长度要少于等于 magazine, 因为magazine中字符只能使用一次
  3. 需要用到hash table

与242.区别

在242. 有效的字母异位词中，可以同步遍历的原因是两者相互为生产者与消费者；

1
2
3
4
# 仅当长度相等时，同步推进，减少一次遍历次数
for i,j in zip(s,t):
    nums[ord(i) - ord('a')] += 1
    nums[ord(j) - ord('a')] -= 1

本题特殊性是，magazine需要cover掉ransomNote用的字符，所以必须先遍历ransomNote，了解ransomNote的需求；

再遍历magazine，如果某个字符需求数量大于0，再将需求减一；否则没必要操作：

比如ransomNote = “aa”, magazine = “aab”，虽然’b’在magazine中，但table[‘b’-‘a’]=0，没必要进行操作的

代码

  • 时间复杂度O(N)
  • 空间复杂度O(1)
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
class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        # 本题特殊性是，magazine需要cover掉ransomNote用的字符
        if len(ransomNote) > len(magazine):
            return False
        table = [0] * 26
        
        # 消费者需要的量
        for i in ransomNote:
            table[ord(i) - ord('a')] += 1
        
        # 生产者有的量
        for i in magazine:
            # 如果消费者有这个字符的需求，才减少，不然没必须操作
            if table[ord(i) - ord('a')] > 0:
                table[ord(i) - ord('a')] -= 1
        
        # 直接求和，只有等于零时才满足要求
        if sum(table)!= 0:
            return False

        # 或者逐个遍历也是一样的
        # for i in table:
        #     if i != 0:
        #         return False

        return True

15. 三数之和

对于15.三数之和 (opens new window)双指针法就是将原本暴力O(n^3)的解法，降为O(n^2)的解法，四数之和的双指针解法就是将原本暴力O(n^4)的解法，降为O(n^3)的解法。

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

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

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

示例 1：

1
2
3
4
5
6
7
8
输入：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：

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

示例 3：

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

提示：

  • 3 <= nums.length <= 3000
  • -105 <= nums[i] <= 105

思路

  1. 这题目和1. 两数之和很像，但本题target固定为0
  2. 这题目用hash table会变得复杂，使用双指针更简单
  3. 从左向右遍历，先固定一个数,如num[0]，则num[1:]可以看成一个“两数之和”的问题，并且target变成0-num[0]

代码

  • 时间复杂度O(N^2)
  • 空间复杂度O(1)
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
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 这题目和1. 两数之和很像，但本题target固定为0
        # 这题目用hash table会变得复杂，使用双指针更简单
        # 从左向右遍历，先固定一个数,如num[0]，则num[1:]可以看成一个“两数之和”的问题，并且target变成0-num[0]
        L = len(nums)
        res = list()
        nums.sort()
        for index in range(L):
            if nums[index] > 0:
                return res
            # 对于nums[index]来说, 跳过相同的数字
            if index > 0 and nums[index] == nums[index - 1]:
                continue

            left = index + 1
            right = L - 1
            currentTarget = - nums[index]
            while left < right:
                # 计算双指针的和
                currentSum = nums[left] + nums[right]
                if currentSum == currentTarget:
                    res.append([nums[index], nums[left], nums[right]]) 
                    # 需要去重复
                    while right > left and nums[right] == nums[right - 1]:
                        right -= 1
                    while right > left and nums[left] == nums[left + 1]:
                        left += 1
                    # 记得修改条件
                    left += 1
                    right -= 1
                elif currentSum < currentTarget:
                    left += 1
                else:
                    right -= 1
        
        return res

思路二(字典)

  1. 或者和之前一样，使用字典也能做
  2. 同样，对nums里每个num遍历，把剩下的nums看成双数相加等于target问题
  3. 创建个字典，用来记录剩下nums的其中一个值，并在剩下nums找另一个值；如果

img

代码

  • 时间复杂度O(N^2)
  • 空间复杂度O(1)
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
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        L = len(nums)
        res = list()
        nums.sort()
        for index in range(L):
            if nums[index] > 0:
                return res
            # 对于nums[index]来说, 跳过相同的数字
            if index > 0 and nums[index] == nums[index - 1]:
                continue
            
            table = dict()
            # 更新target
            target = 0 - nums[index]
            for j in range(index + 1, L):
              	# 跳过重复的值
                if j > index + 2 and nums[j] == nums[j - 1] == nums[j - 2]:
                    continue
                # 后面的思路和1. 两数之和完全一样，判断某个值是否已经在table里了，如果在，说明它就是需要被找到的值
                # 否则就把它添加进去
                if nums[j] in table:
                    res.append([nums[index], nums[j], target - nums[j]])
                    table.pop(nums[j])
                else:
                    table[target - nums[j]] = j

18. 四数之和https://leetcode.cn/problems/4sum/

给你一个由 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：

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

示例 2：

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

提示：

  • 1 <= nums.length <= 200
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109

思路

  1. 和三数之和几乎一样，这题目可以扩展到N数之和
  2. 可以不提前退出，但必须“去重复”；否则[2,2,2,2,2]（输入），会输出[[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]]
  3. 提前退出的条件
    1. 条件1：if nums[i] > target and nums[i] > 0 and target > 0:
    2. 条件2：if nums[i] + nums[j] > target and target > 0
    3. 满足其中一个即可退出

代码

  • 时间复杂度O(N^3)
  • 空间复杂度O(1)
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
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        # 和三数之和相似，但可以用两层for循环，将原本需要O(n^4)降为O(n^3)
        res = list()
        L = len(nums)
        nums.sort()
        for i in range(L):
            # 必须去重复，否则[2,2,2,2,2]（输入），会输出[[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]]
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            # 提前退出[Optional]
            if nums[i] > target and nums[i] > 0 and target > 0:
              	break
                
            for j in range(i + 1, L):
                # 必须去重复
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                # 提前退出[Optional]
                if nums[i] + nums[j] > target and target > 0
                		break 
                  
                # 双指针
                left = j + 1
                right = L - 1
                current_target = target - nums[i] - nums[j]
                while left < right:
                    currentSum = nums[left] + nums[right]
                    if current_target == currentSum:
                        res.append([nums[i], nums[j], nums[left], nums[right]])
                        # 同样是为了去重复
                        while right > left and nums[right] == nums[right - 1]:
                            right -= 1
                        while right > left and nums[left] == nums[left + 1]:
                            left += 1
                        left += 1
                        right -= 1
                    elif currentSum < current_target:
                        left += 1
                    else:
                        right -= 1

        return res

思路二(字典)

同样，这题目也可以用dict解决，我刚开始没有去重复，于是错误了

  • 时间复杂度O(N^3)
  • 空间复杂度O(1)
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
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        # 和三数之和相似，但可以用两层for循环，将原本需要O(n^4)降为O(n^3)
        res = list()
        L = len(nums)
        nums.sort()
        for i in range(L):
            # 必须去重复，否则[2,2,2,2,2]（输入），会输出[[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]]
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            for j in range(i + 1, L):
                # 必须去重复
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue

                # 用hash table试试
                table = dict()
                current_target = target - nums[i] - nums[j]
                for k in range(j + 1, L):
                    if k > j + 3 and nums[k] == nums[k - 1] == nums[k - 2] == nums[k - 3]:
                        continue
                    if nums[k] in table:
                        res.append([nums[i], nums[j], nums[k], current_target - nums[k]])
                        table.pop(nums[k])
                    else:
                        table[current_target - nums[k]] = k

        return res

454. 四数相加 II

https://leetcode.cn/problems/4sum-ii/

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

  • 0 <= i, j, k, l < n
  • nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例 1：

1
2
3
4
5
6
输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

示例 2：

1
2
输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1

提示：

  • n == nums1.length
  • n == nums2.length
  • n == nums3.length
  • n == nums4.length
  • 1 <= n <= 200
  • -228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228

思路

  1. 之前的三数之和、四数之和是在同一个数组查找，现在是四个不同的数组
  2. 用两个双层for循环，先算A, B的所有和，放在字典中；再算C, D所有排列组合可能的和，从字典中查找是否存在这样的键，如果存在就将这个键对应的值（即A,B的所有的和出现的次数

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        # 统计 a+b+c+d = 0 出现的次数
        res = 0
        # key放a和b两数之和，value 放a和b两数之和出现的次数
        table = dict()
        # 先计算nums1, nums2的排列组合可能的和
        for i in nums1:
            for j in nums2:
                table[i + j] = table.get(i + j, 0) + 1
        # 
        for i in nums3:
            for j in nums4:
                if table.get(- i - j, 0):
                    res += table[0 - i - j]
        
        return res