代码随想录刷题题Day6

刷题的第六天，希望自己能够不断坚持下去，迎来蜕变。😀😀😀
刷题语言：C++ / Python
哈希表理论基础见代码随想录刷题题Day5
Day6 任务
● 454.四数相加II
● 383. 赎金信
● 15. 三数之和
● 18. 四数之和
● 总结

1 四数相加II

本题使用map解决问题，体会使用哈希法如何提高程序执行效率，降低时间复杂度，当然使用哈希法会提高空间复杂度，但一般来说就是舍空间换时间，工业开发也是这样

当我们遇到要快速判断一个元素是否出现在集合里，就要考虑哈希法
伪代码：

（1）定义一个unordered_map，key存放nums1和nums2里面的元素之和,value存放nums1和nums2里面的元素之和出现的次数
（2）遍历nums1和nums2数组，统计key和value
（3）定义变量count，统计$nums1[i]+nums2[j]+nums3[k]+nums4[l]=0$出现的次数
（4）遍历nums3和nums4数组，如果$0-(nums3[k]+nums4[l])$在map出现过，就用count把map中key对应的value统计出来
（5）返回统计值count

C++：

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
		unordered_map<int, int> map;
		for (auto a : nums1)
			for (auto b : nums2)
			{
				map[a+b]++;
			}
		int count = 0;// 统计a+b+c+d = 0 出现的次数
		for (auto c : nums3)
			for (auto d : nums4)
			{
				int target = 0 - (c + d);
				if (map.find(target) != map.end())
				{
					count += map[target];
				}
			}
		return count;
    }
};

时间复杂度：$O(n^2)$
空间复杂度：$O(n^2)$
Python：

class Solution(object):
    def fourSumCount(self, nums1, nums2, nums3, nums4):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :type nums3: List[int]
        :type nums4: List[int]
        :rtype: int
        """
        # 使用字典存储nums1和nums2中的元素及其和
        hashmap = dict()
        for a in nums1:
            for b in nums2:
                if a + b in hashmap:
                    hashmap[a+b] += 1
                else:
                    hashmap[a+b] = 1
        # 如果 -(a+b) 存在于nums3和nums4, 存入结果
        count = 0
        for c in nums3:
            for d in nums4:
                target = 0 - (c + d)
                if target in hashmap:
                    count += hashmap[target]
        return count

2 赎金信

本题和有效的字母异位词是一个思路

有效的字母异位词：求字符串a和字符串b是否可以相互组成，这道题目求字符串a能否组成字符串b，而不用管字符串b能否组成a
本题判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成

（1）杂志字符串中的每个字符只能在赎金信字符串中使用一次
（2）两个字符串均只含有小写字母：可以用数组做哈希法
暴力法
C++:

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        for (int i = 0; i < magazine.size(); i++)
        {
            for (int j = 0; j < ransomNote.size(); j++)
            {
                // 在ransomNote中找到和magazine相同的字符
                if (magazine[i] == ransomNote[j])
                {
                    ransomNote.erase(ransomNote.begin() + j); // ransomNote删除这个字符
                    break;
                }
            }
        }
        // 如果ransomNote为空，则说明magazine的字符可以组成ransomNote
        if (ransomNote.length() == 0) return true;
        return false;
    }
};

时间复杂度: $O(n^2)$
空间复杂度: $O(1)$
哈希解法：
本题使用map的空间消耗要比数组大一些，因为map要维护红黑树或者哈希表，而且还要做哈希函数，是费时的！数据量大的话就能体现出来差别了。 所以数组更加简单直接有效！
伪代码：

（1）定义hash[26]，记录每个字符出现的次数
（2）如果ransomNote的字符数大于magazine的字符数，return false
（3）记录 magazine里各个字符出现次数
（4）遍历ransomNote，在hash里对应的字符个数做–操作，如果小于零说明ransomNote里出现的字符，magazine没有，return false
（5）遍历完，返回true

C++：

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int hash[26] = {0};
        if (ransomNote.size() > magazine.size()) return false;
        // 记录 magazine里各个字符出现次数
        for (auto a : magazine)
        {
        	hash[a - 'a']++;
        }
        // 遍历ransomNote，在hash里对应的字符个数做--操作
        for (auto b : ransomNote)
        {
        	hash[b - 'a']--;
        	// 如果小于零说明ransomNote里出现的字符，magazine没有
        	if (hash[b - 'a'] < 0) return false;
        }
        return true;
    }
};

时间复杂度: $O(n)$
空间复杂度: $O(1)$
Python：

class Solution(object):
    def canConstruct(self, ransomNote, magazine):
        """
        :type ransomNote: str
        :type magazine: str
        :rtype: bool
        """
        count = [0] * 26
        for c in magazine:
            count[ord(c) - ord('a')] += 1
        for c in ransomNote:
            count[ord(c) - ord('a')] -= 1
            if count[ord(c) - ord('a')] < 0:
                return False
        return True

3 三数之和

本题虽然和两数之和很像，也能用哈希法，但是用哈希法会很麻烦，双指针法才是正解

双指针：
本道题目用哈希法不合适，因为去重有很多细节需要注意，面试中很难做到bug free

伪代码：

（1）先将数组nums排序
（2）for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i]，b = nums[left]，c = nums[right]
（3）如果$nums[i]>0$，返回。对a做去重处理，如果i>0&&a等于a的前一个数，continue
（4）移动left和right，把left < right作为循环结束条件，不能等于是因为不能将两个指针指向同一个数
（5）如果三数之和>0，right下标向左移动
（6）如果三数之和<0，left下标向右移动
（7）如果三数之和=0，把结果存到result，对left和right做去重操作，如果right下标等于right下标的前一个数,right–；如果left下标等于left下标的后一个数,left++
（8）找到答案时，双指针同时收缩

处理left和right的去重细节
这里也类似前面的i,要和之前已经处理过的数据比较
这里同时要保证left是小于right的，不然容易越界，也没必要做任何操作了
违反这个会直接退出大的while（left<right）循环
这里要用while处理，因为可能有连续的好几个

C++：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
		vector<vector<int>> result;
		sort(nums.begin(), nums.end());
		// 找出a + b + c = 0
        // a = nums[i], b = nums[left], c = nums[right]
		for (int i = 0; i < nums.size(); i++)
		{
			// 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果
			if (nums[i] > 0) return result;
			// 正确去重a方法
			if (i > 0 && nums[i] == nums[i - 1]) continue;
			int left = i + 1;
			int right = nums.size() - 1;
			while (left < right)
			{
				if (nums[i] + nums[left] + nums[right] > 0) right--;
				else if (nums[i] + nums[left] + nums[right] < 0) left++;
				else 
				{
					result.push_back(vector<int>{nums[i], nums[left], nums[right]});
					// 去重逻辑应该放在找到一个三元组之后，对b和c去重
					while (left < right && nums[right] == nums[right - 1]) right--;
					while (left < right && nums[left] == nums[left + 1]) left++;
					// 找到答案时，双指针同时收缩
					left++;
					right--;
				}
			}
		}
		return result;
    }
};

时间复杂度：$O(n^2)$
空间复杂度：$O(1)$
Python：

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = []
        nums.sort()
        for i in range(len(nums)):
            # 如果第一个元素已经大于0，不需要进一步检查
            if nums[i] > 0:
                return result
            # 跳过相同的元素以避免重复
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            left = i + 1
            right = len(nums) - 1
            while left < right:
                if nums[i] + nums[left] + nums[right] > 0:
                    right -= 1
                elif nums[i] + nums[left] + nums[right] < 0:
                    left += 1
                else:
                    result.append([nums[i], nums[left], nums[right]])
                    # 跳过相同的元素以避免重复
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    right -= 1
                    left += 1
        return result

哈希法：

三数之和去重是怎么保证a的去重，而没有把合适的b也去掉了呢？
b在a后面，当a的数字确定，后面b+c的值也确定，比如序列-2,-2,4,8,16,第一次遇到某一个a=-2的时候已经把后面所有b+c=2的情况跑完了，第二次再次遇到a=-2的时候已经没有跑的意义了，更遑论有没有去掉合适的b，而且有可能第一次遇到a=-2的时候，可能正好有b=-2,c=4这种情况，但你第二次遇到a=-2,再去跑，就会发现甚至这种情况还会被漏掉。nums[i] == nums[i-1]基本就是应对这两种情况
对于哈希法，b和c去重的逻辑
对于 b 的去重，一般可以和 a 一样检查当前的 b 是否和前一个 b 相同，如果相同，则跳过当前的 b。这样可以保证每个 b 只被使用一次。但是这种方法有一个问题，就是如果数组中有连续三个或以上相同的元素，那么第一个和第二个元素都会被跳过，导致漏掉一些可能的解。例如，如果数组中有三个0，那么[0,0,0]就是一个有效的解，但是用这种方法就会被忽略。
改进一下条件，只有当当前的b和前两个b都相同时才跳过当前的 b。这样可以保证至少有一个 b 被使用，并且不会出现重复对于 c 的去重，利用哈希集合的特性，在找到一个 c 后将其从哈希集合中删除。这样可以保证每个 c 只被使用一次且不会出现重复。

C++：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        // 找出a + b + c = 0
        // a = nums[i], b = nums[j], c = -(a + b)
        for (int i = 0; i < nums.size(); i++) {
            // 排序之后如果第一个元素已经大于零，那么不可能凑成三元组
            if (nums[i] > 0) {
                break;
            }
            if (i > 0 && nums[i] == nums[i - 1]) { //三元组元素a去重
                continue;
            }
            unordered_set<int> set;
            for (int j = i + 1; j < nums.size(); j++) {
                if (j > i + 2
                        && nums[j] == nums[j-1]
                        && nums[j-1] == nums[j-2]) { // 三元组元素b去重
                    continue;
                }
                int c = 0 - (nums[i] + nums[j]);
                if (set.find(c) != set.end()) {
                    result.push_back({nums[i], nums[j], c});
                    set.erase(c);// 三元组元素c去重
                } else {
                    set.insert(nums[j]);
                }
            }
        }
        return result;
    }
};

4 四数之和

思路：和前面的三数之和思路很像，都是用双指针的方法来解决。

三数之和的双指针解法是一层for循环num[i]为确定值，然后循环内有left和right下标作为双指针，找到nums[i] + nums[left] + nums[right] == 0
四数之和的双指针解法是两层for循环nums[k] + nums[i]为确定值，依然是循环内有left和right下标作为双指针，找出nums[k] + nums[i] + nums[left] + nums[right] == target的情况，三数之和的时间复杂度是$O(n^2)$，四数之和的时间复杂度是$O(n^3)$
五数之和、六数之和等等都采用这种解法

四数相加II 相对于本题简单很多，因为本题是要求在一个集合中找出四个数相加等于target，同时四元组不能重复，而四数相加II是四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况

C++:

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        for (int k = 0; k < nums.size(); k++)
        {
        	// 剪枝
        	if (nums[k] > target && nums[k] > 0 && target > 0) break;
        	// 对nums[k]去重
        	if (k > 0 && nums[k] == nums[k - 1]) continue;
        	for (int i = k + 1; i < nums.size(); i++)
        	{
        	    // 2级剪枝
        		if (nums[k] + nums[i] > target && nums[k] + nums[i] > 0 && target > 0) break;
        		// 对nums[i]去重
        		if (i > k + 1 && nums[i] == nums[i - 1])continue;
        		int left = i + 1;
        		int right = nums.size() - 1;
        		while (left < right)
        		{
        		    // nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出
        			if ((long)nums[k] + nums[i] + nums[left] + nums[right] > target) right--;
        			else if ((long)nums[k] + nums[i] + nums[left] + nums[right] < target) left++;
        			else
        			{
        				result.push_back({nums[k], nums[i], nums[left], nums[right]});
        				// 对nums[left]和nums[right]去重
        				while (left < right && nums[left] == nums[left + 1]) left++;
        				while (left < right && nums[right] == nums[right - 1]) right--;
        				// 找到答案时，双指针同时收缩
        				left++;
        				right--;
        			}
        		}
        	}
        }
        return result;
    }
};

时间复杂度: $O(n^3)$
空间复杂度: $O(1)$
Python：

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        nums.sort()
        n = len(nums)
        result = []
        for i in range(n):
            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):
                if nums[i] + nums[j] > target and nums[i] + nums[j] > 0 and target > 0: #剪枝
                    break
                if j > i + 1 and nums[j] == nums[j-1]: # 去重
                    continue
                left = j + 1
                right = n - 1
                while left < right:
                    s = nums[i] + nums[j] + nums[left] + nums[right]
                    if s < target:
                        left += 1
                    elif s > target:
                        right -= 1
                    else:
                        result.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 result

鼓励坚持七天的自己😀😀😀