代码随想录算法训练营第六天 | 454.四数相加II、383. 赎金信、15. 三数之和、18. 四数之和

发布时间:2024年01月18日

代码随想录算法训练营第六天 | 454.四数相加II、383. 赎金信、15. 三数之和、18. 四数之和

1 LeetCode 454.四数相加II

题目链接:https://leetcode.cn/problems/4sum-ii/description/

给你四个整数数组 nums1nums2nums3nums4 ,数组长度都是 n ,请你计算有多少个元组 (i, j, k, l) 能满足:

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

示例 1:

输入: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:

输入: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

这道题目也是哈希法的经典运用,和之前我们做过的242.有效的字母异位词思路一致,先遍历一个集合,然后再去另一个集合中找符合的元素,这道题目有四个数组,我们需要两两数组结合成一个集合,然后最后合并之后也就只剩下两个集合了,操作就和之前一致了。

然后哈希法的结构我们需要选择map来解决,因为我们需要存储元素是否出现过(这里是两个数组合并之后的元素),以及出现过的次数,第一个map存两个数组元素之和a+b,和出现的次数,然后在第二个map找0-(c+d) 是否在map中出现过,如果出现过就用count(用来统计 a+b+c+d = 0 出现的次数)把map中key对应的value也就是出现次数统计出来,最后返回统计值 count 即可。

(1)Python版本代码

class Solution:
    def fourSumCount(self, nums1, nums2, nums3, nums4):
        hashmap = {}    # key: nums1[i] + nums2[j], value: count
        for i in range(len(nums1)):         
            for j in range(len(nums2)):    # 计算nums1[i] + nums2[j]的和,存入hashmap
                if nums1[i] + nums2[j] in hashmap:
                    hashmap[nums1[i] + nums2[j]] += 1
                else:   # 如果不存在,初始化为1
                    hashmap[nums1[i] + nums2[j]] = 1
        count = 0   # 计数器
        for i in range(len(nums3)):     
            for j in range(len(nums4)):   # 计算nums3[i] + nums4[j]的和,如果存在hashmap中,count加上对应的value
                if -(nums3[i] + nums4[j]) in hashmap:
                    count += hashmap[-nums3[i] - nums4[j]]  
        return count

if __name__ == "__main__":
    nums1 = list(map(int, input().split()))
    nums2 = list(map(int, input().split()))
    nums3 = list(map(int, input().split()))
    nums4 = list(map(int, input().split()))
    solution = Solution()
    print(solution.fourSumCount(nums1, nums2, nums3, nums4))

(2)C++版本代码

#include <iostream>
#include <vector>
#include <unordered_map>
#include <sstream>

class Solution {
public:
    int fourSumCount(std::vector<int>& nums1, std::vector<int>& nums2, std::vector<int>& nums3, std::vector<int>& nums4) {
        std::unordered_map<int, int> hashmap; // key: nums1[i] + nums2[j] 的和, value: 出现次数
        // 计算 nums1[i] + nums2[j] 的和,并存储在 hashmap 中
        for (int i : nums1) {
            for (int j : nums2) {
                hashmap[i + j]++;
            }
        }

        int count = 0; // 计数器
        // 计算 nums3[i] + nums4[j] 的和,并在 hashmap 中查找是否有对应的负数
        for (int i : nums3) {
            for (int j : nums4) {
                if (hashmap.find(-i - j) != hashmap.end()) {
                    count += hashmap[-i - j];
                }
            }
        }

        return count;
    }
};

std::vector<int> readVector() {
    std::string line;
    std::getline(std::cin, line);
    std::istringstream stream(line);
    std::vector<int> nums;
    int number;
    while (stream >> number) {
        nums.push_back(number);
    }
    return nums;
}

int main() {
    Solution solution;
    std::cout << "输入四个整数数组,每个数组一行,数字之间用空格分隔:" << std::endl;
    std::vector<int> nums1 = readVector();
    std::vector<int> nums2 = readVector();
    std::vector<int> nums3 = readVector();
    std::vector<int> nums4 = readVector();
    std::cout << "结果:" << solution.fourSumCount(nums1, nums2, nums3, nums4) << std::endl;
    return 0;
}
  • 时间复杂度: O( n 2 n^2 n2)。
  • 空间复杂度: O( n 2 n^2 n2),最坏情况下A和B的值各不相同,相加产生的数字个数为 n 2 n^2 n2

2 LeetCode 383. 赎金信

题目链接:https://leetcode.cn/problems/ransom-note/description/

给你两个字符串:ransomNotemagazine ,判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以,返回 true ;否则返回 false

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

示例 1:

输入:ransomNote = "a", magazine = "b"
输出:false

示例 2:

输入:ransomNote = "aa", magazine = "ab"
输出:false

示例 3:

输入:ransomNote = "aa", magazine = "aab"
输出:true

提示:

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

这道题目也和前面的242.有效的字母异位词解决思路基本一致,这几题都有异曲同工之妙。

(1)Python版本代码

  • 数组

    class Solution:
        def canConstruct(self, ransomNote, magazine):
            # 创建一个长度为26的数组来存储每个字母在杂志字符串中出现的次数
            # 每个字母对应数组的一个位置,例如 'a' 对应位置 0,'b' 对应位置 1,以此类推
            count = [0] * 26
    
            # 遍历杂志字符串,更新数组中各字母出现的次数
            for char in magazine:
                count[ord(char) - ord('a')] += 1
    
            # 遍历赎金信字符串
            for char in ransomNote:
                # 检查当前字母是否足够
                if count[ord(char) - ord('a')] == 0:
                    return False
                count[ord(char) - ord('a')] -= 1
    
            return True
    
    if __name__ == '__main__':
        s = Solution()
        ransomNote = input()
        magazine = input()
        print(s.canConstruct(ransomNote, magazine))
    
    • 时间复杂度:O(M + N)
    • 空间复杂度:O(1)
  • map

    class Solution:
        def canConstruct(self, ransomNote, magazine):
            dic = {}  # 创建一个字典,用于存储杂志字符串中每个字符出现的次数
    
            # 遍历杂志字符串,统计每个字符出现的次数
            for i in magazine:
                if i in dic:  # 如果字符已经在字典中,则增加其计数
                    dic[i] += 1
                else:  # 如果字符不在字典中,则将其添加到字典中,并初始化计数为1
                    dic[i] = 1
    
            # 遍历赎金信字符串,检查每个字符是否能从杂志字符串中找到
            for i in ransomNote:
                if i in dic and dic[i] > 0:  # 如果字符在杂志字符串中,并且数量大于0
                    dic[i] -= 1  # 使用一个字符,相应减少字典中该字符的计数
                else:  # 如果字符不在杂志字符串中,或者数量不足
                    return False  # 无法构建赎金信,返回False
    
            # 如果所有赎金信的字符都能在杂志字符串中找到且数量足够,则返回True
            return True
        
    if __name__ == '__main__':
        s = Solution()
        ransomNote = input()
        magazine = input()
        print(s.canConstruct(ransomNote, magazine))
    
    • 时间复杂度:O(M + N),其中 M 是杂志字符串 magazine 的长度, N 是赎金信字符串 ransomNote 的长度。
    • 空间复杂度:O(M),我们使用了一个字典来存储杂志字符串中每个字符出现的次数,在最坏的情况下(即杂志字符串中的每个字符都不同),这个字典的大小会与杂志字符串的长度 M 相等。

两者相比较就可以发现这题更适合使用数组来实现哈希法,因为题目限制了数组的大小,因此使用数组空间复杂度会很低。

这道题目python还有一种更加简洁的写法,但是不推荐大家写,因为面试大概率不会让你这样去写的。

class Solution:
    def canConstruct(self, ransomNote, magazine):
        for i in ransomNote:
                if ransomNote.count(i) > magazine.count(i):
                    return False
            return True

(2)C++版本代码

  • 数组

    #include <iostream>
    #include <string>
    #include <vector>
    
    class Solution {
    public:
        bool canConstruct(std::string ransomNote, std::string magazine) {
            std::vector<int> count(26, 0);
    
            // 统计杂志中各字母出现的次数
            for (char ch : magazine) {
                count[ch - 'a']++;
            }
    
            // 检查赎金信中的字符是否可以由杂志中的字符组成
            for (char ch : ransomNote) {
                if (--count[ch - 'a'] < 0) {
                    return false;
                }
            }
    
            return true;
        }
    };
    
    int main() {
        Solution solution;
        std::string ransomNote, magazine;
        std::getline(std::cin, ransomNote);
        std::getline(std::cin, magazine);
        std::cout << (solution.canConstruct(ransomNote, magazine) ? "True" : "False") << std::endl;
        return 0;
    }
    
  • map

    #include <iostream>
    #include <string>
    #include <unordered_map>
    
    class Solution {
    public:
        bool canConstruct(std::string ransomNote, std::string magazine) {
            std::unordered_map<char, int> charCount;
    
            // 统计杂志中各字母出现的次数
            for (char ch : magazine) {
                charCount[ch]++;
            }
    
            // 检查赎金信中的字符是否可以由杂志中的字符组成
            for (char ch : ransomNote) {
                if (--charCount[ch] < 0) {
                    return false;
                }
            }
    
            return true;
        }
    };
    
    int main() {
        Solution solution;
        std::string ransomNote, magazine;
        std::getline(std::cin, ransomNote);
        std::getline(std::cin, magazine);
        std::cout << (solution.canConstruct(ransomNote, magazine) ? "True" : "False") << std::endl;
        return 0;
    }
    

3 LeetCode 15. 三数之和

题目链接:https://leetcode.cn/problems/3sum/description/

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != ji != kj != 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

这道题目强烈推荐大家去看看卡哥的视频讲解,很详细,然后再去看看代码随想录文字版讲解

这道题目可以使用哈希法,也可以使用双指针法,关键就在于去重,因为题目要求答案中不可以包含重复的三元组,但是哈希法相对于双指针法更加的麻烦,麻烦就在去重的操作上面,有很多的小细节需要注意。

3.1 为什么哈希法比较麻烦?

  • 去重处理复杂:哈希法在寻找三元组的过程中可能会遇到重复的组合,特别是当数组中有多个相同的数字时。处理这些重复的组合需要额外的逻辑,以确保最终结果中不包含重复的三元组。
  • 空间复杂度较高:使用哈希法通常需要额外的空间来存储已经访问过的数字或数字对,这可能导致相对较高的空间复杂度。

3.2 为什么双指针法更简单?

  • 减少不必要的搜索:首先对数组进行排序,然后固定一个数,使用两个指针在剩余的数组中寻找符合条件的另外两个数,这种方法可以有效地减少搜索空间。
  • 去重简单:由于数组已排序,去重变得相对简单。只需要跳过重复的元素即可,这在编码实现上更加直观。

3.3 使用双指针法时需要注意的问题

我们在使用双指针法之前必须要先对数组进行排序(这是使用双指针法的前提,这也是为啥前面两数之和我们不能使用双指针法的原因),然后我们在查找的过程中,根据三数之和与0的比较结果,决定是移动左指针还是右指针,如果和小于0,移动左指针;如果和大于0,移动右指针,在移动指针时,我们还要确保指针不会越界。

下面是去重操作需要注意的方面:

  • 跳过相同的元素:在移动指针时,如果遇到相同的元素,需要跳过,以避免重复的三元组。
  • 固定元素去重:在外层循环固定第一个元素时,如果当前元素与前一个元素相同,也需要跳过,以避免重复。
  • 左右指针去重:在内层循环中,当找到符合条件的三元组后,左右指针分别需要跳过所有重复的元素。

3.4 代码实现

(1)Python版本代码

class Solution:
    def threeSum(self, nums):
        # 对数组进行排序
        nums.sort()
        n = len(nums)
        res = []

        # 遍历数组,固定第一个数
        for i in range(n):
            # 如果当前数字大于0,则三数之和一定大于0,结束循环
            if nums[i] > 0:
                break
            # 跳过重复数字
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            # 左右指针初始化
            left, right = i + 1, n - 1
            while left < right:
                total = nums[i] + nums[left] + nums[right]
                # 如果三数之和为0,加入到结果中
                if total == 0:
                    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
                # 如果三数之和小于0,移动左指针
                elif total < 0:
                    left += 1
                # 如果三数之和大于0,移动右指针
                else:
                    right -= 1

        return res

if __name__ == "__main__":
    solution = Solution()
    nums = list(map(int, input().split()))
    print(solution.threeSum(nums))

为什么跳过重复数字要用nums[i] == nums[i - 1]而不能用nums[i] == nums[i + 1]?

当使用 nums[i] == nums[i - 1]

  • 检查当前元素与前一个元素:我们只在发现当前元素与前一个元素相同时跳过当前元素。
  • 避免漏掉组合:这种方法确保了即使数组中有重复的数字,每个数字也至少被作为三元组的第一个数字尝试一次,这样做不会错过任何可能的组合。
  • 在循环的开始处判断:此检查通常在循环的开始执行,确保了当我们开始处理一个新的数字时,它是不同于前一个数字的。

相反如果使用 nums[i] == nums[i + 1]

  • 检查当前元素与后一个元素:这会在发现当前元素与后一个元素相同时跳过当前元素。
  • 可能漏掉组合:这种方法可能会导致错过一些有效的组合。比如在数组 [1, 1, 1, 2, 2] 中寻找三数之和为6的组合,我们会在第一个1的时候就跳过后面所有的1,从而错过有效的组合 (1, 2, 3)
  • 在处理完成后判断:这种检查通常在处理完当前数字后执行,这意味着可能会重复处理相同的数字作为三元组的起始数字。

(2)C++版本代码

#include <iostream>
#include <vector>
#include <algorithm>

class Solution {
public:
    std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
        std::sort(nums.begin(), nums.end());
        std::vector<std::vector<int>> res;
        int n = nums.size();

        // 遍历数组,固定第一个数
        for (int i = 0; i < n; ++i) {
            // 如果当前数字大于0,则三数之和一定大于0,结束循环
            if (nums[i] > 0) break;
            // 跳过重复数字
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            // 左右指针初始化
            int left = i + 1, right = n - 1;
            while (left < right) {
                int total = nums[i] + nums[left] + nums[right];
                // 如果三数之和为0,加入到结果中
                if (total == 0) {
                    res.push_back({nums[i], nums[left], nums[right]});
                    // 跳过重复数字
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    // 移动指针
                    left++;
                    right--;
                }
                // 如果三数之和小于0,移动左指针
                else if (total < 0) {
                    left++;
                }
                // 如果三数之和大于0,移动右指针
                else {
                    right--;
                }
            }
        }

        return res;
    }
};

int main() {
    Solution solution;
    std::vector<int> nums;
    int num;
    while (std::cin >> num) {
        nums.push_back(num);
        if (std::cin.peek() == '\n') break;
    }

    std::vector<std::vector<int>> result = solution.threeSum(nums);
    for (const auto& triple : result) {
        for (int num : triple) {
            std::cout << num << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}
  • 时间复杂度: O( n 2 n^2 n2)
  • 空间复杂度: O(1)

4 LeetCode 18. 四数之和

题目链接:https://leetcode.cn/problems/4sum/description/

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

  • 0 <= a, b, c, d < n
  • abcd 互不相同
  • 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 <= nums.length <= 200
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109

这题跟上一题思路大致一样,需要再加上一层for循环,然后去重的操作需要注意一下,和上一题相比有所区别,三数之和是使用一个外层循环遍历数组,对于每个元素,使用双指针在剩余部分寻找两个数,使得三数之和为0,而四数之和使用两层循环固定前两个数,然后在剩余的数组中使用双指针寻找另外两个数,使得四数之和达到目标值,前面是固定找相加等于0,后面是用户自己输入的target,因此后续去重操作有所不同,四数之和在去重方面相比三数之和更加复杂,因为它涉及到两层循环的去重,而三数之和只需要处理外层循环和双指针的去重,本题虽然看起来和前面做的454.四数相加Ⅱ但本质还是有所不同,前者是四个数组,本题只有一个数组,需要考虑去重操作。

(1)Python版本代码

class Solution:
    def fourSum(self, nums, target):
        nums.sort()  # 对数组进行排序
        n = len(nums)  # 数组长度
        res = []  # 用于存储结果的列表

        # 遍历数组,固定第一个数
        for i in range(n):
            # 如果当前数字大于目标值且当前数字和目标值都大于0,则后续不可能找到符合条件的组合
            if nums[i] > target and nums[i] > 0 and target > 0:
                break
            # 跳过重复数字
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            # 第二层循环,固定第二个数
            for j in range(i + 1, n):
                # 如果两个固定数字之和已大于目标值且目标值大于0,则后续不可能找到符合条件的组合
                if nums[i] + nums[j] > target and target > 0:
                    break
                # 跳过重复数字
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue

                # 双指针寻找剩余两个数
                left, right = j + 1, n - 1
                while left < right:
                    sum = nums[i] + nums[j] + nums[left] + nums[right]  # 四数之和
                    if sum == target:  # 如果和等于目标值,添加到结果中
                        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
                    elif sum < target:  # 如果和小于目标值,移动左指针
                        left += 1
                    else:  # 如果和大于目标值,移动右指针
                        right -= 1
        return res
    
if __name__ == "__main__":
    solution = Solution()
    nums = list(map(int, input().split()))
    target = int(input())
    print(solution.fourSum(nums, target))

(2)C++版本代码

#include <iostream>
#include <vector>
#include <algorithm>

class Solution {
public:
    std::vector<std::vector<int>> fourSum(std::vector<int>& nums, int target) {
        std::sort(nums.begin(), nums.end()); // 对数组进行排序
        int n = nums.size();
        std::vector<std::vector<int>> res;

        // 遍历数组,固定第一个数
        for (int i = 0; i < n; ++i) {
            // 如果当前数字大于目标值且当前数字和目标值都大于0,则后续不可能找到符合条件的组合
            if (nums[i] > target && nums[i] > 0 && target > 0) break;
            // 跳过重复数字
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            // 第二层循环,固定第二个数
            for (int j = i + 1; j < n; ++j) {
                // 如果两个固定数字之和已大于目标值且目标值大于0,则后续不可能找到符合条件的组合
                if (nums[i] + nums[j] > target && target > 0) break;
                // 跳过重复数字
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;

                // 双指针寻找剩余两个数
                int left = j + 1, right = n - 1;
                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right]; // 四数之和
                    if (sum == target) { // 如果和等于目标值,添加到结果中
                        res.push_back({nums[i], nums[j], nums[left], nums[right]});
                        // 跳过重复数字
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        left++;
                        right--;
                    } else if (sum < target) { // 如果和小于目标值,移动左指针
                        left++;
                    } else { // 如果和大于目标值,移动右指针
                        right--;
                    }
                }
            }
        }
        return res;
    }
};

int main() {
    Solution solution;
    int target;
    std::vector<int> nums;
    int num;

    std::cout << "输入数组元素,以空格分隔:" << std::endl;
    while (std::cin >> num) {
        nums.push_back(num);
        if (std::cin.peek() == '\n') break;
    }

    std::cout << "输入目标值:" << std::endl;
    std::cin >> target;

    std::vector<std::vector<int>> result = solution.fourSum(nums, target);
    for (const auto& quad : result) {
        for (int num : quad) {
            std::cout << num << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}
  • 时间复杂度: O(n^3)
  • 空间复杂度: O(1)
文章来源:https://blog.csdn.net/qq_52417436/article/details/135671512
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。