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

454.四数相加II

题目链接：454.四数相加II
文档讲解：第454题.四数相加II
视频讲解：学透哈希表，map使用有技巧！LeetCode：454.四数相加II
目标：
状态：想到了两个数组比较好处理，没想到把四个数组两两结合形成新的两个数组🤪

学习前的想法

题目要求从四个数组中分别找出一个数，使这四个数相加等于0，并返回符合要求的下标元组数目，即四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以。

这道题可以说是昨天两数相加的plus版本，两个数的求和组合方式比较少，容易找出和为目标值的组合，但是四个数组合方式太多，想不到如何解决。

学习后的想法

假设有a，b，c，d四个数组，就像我上面所说，两个数相加等与一个数比较容易判断，因此我们将a + b所有可能的值当成一个数组，而c + d所有可能的值当作一个数组，这样就可以将其转化为两数相加了。

我们依然使用unordered_map数据结构来实现，因为其高效的查找效率。

key为a和b两个数的和，value为这个和出现的次数。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
count;
unordered_map<int, int> map;
// 对a，b进行求和
for(a : A) {
	for(b : B) {
		map[a + b] ++;
	}
}

for(c : C) {
	for(d : D) {
		if(map.find(0 - (c + d)) != map.end()) {
			count += map(0 - (c + d));
		}
	}
}

return count;

383. 赎金信

题目链接：383. 赎金信
文档讲解：383. 赎金信
视频讲解：
目标：在哈希法中有一些场景就是为数组量身定做的。
状态：这道题有了前面的铺垫，哈希法思路轻轻松松，暴力法学习了erase的使用

学习前的想法

题目给定俩个字符串，ransomNote和magazine，判断ransomNote能不能由magzine里面的字符构成，如果可以返回true，否则返回false。

这一题和昨天的242.有效字母异位词是同一个思路。

我的想法是使用一个大小为26的数组，存储magzine中所有的字符出现的次数，由于magzine中每个字符在ransomNote中出现一次，所以每次匹配成功后，数组中对应位置的数值应该减1。

尝试实现代码如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int nums[26] = {0};

        for(int i = 0; i < magazine.size(); i++) {
            nums[magazine[i] - 'a']++;
        }

        for(int j = 0; j < ransomNote.size(); j++) {
            if(nums[ransomNote[j] - 'a'] == 0) return false;
            else nums[ransomNote[j] - 'a']--;
        }

        return true;
    }
};

轻松ac。

2024/2/27
有了上次的经验，在做这道题时就显得很轻松，思路也很清晰。

学习后的想法

暴力解法
时间复杂度：O(n^2)
空间复杂度：O(1)

这道题的暴力解法是使用两层for循环，第一层for循环遍历magzine，第二层for循环遍历ransomNote，当magzine中的字符出现在ransomNote中时，就调用erase函数，将该字符从ransomNote中删除，接着退出第二层循环。

这样当遍历结束时，如果ransomNote中还有剩余的字符，就说明其中有不能用magzine中字符表示的字符。如果没有，则可以表示完全。

即判断循环结束后ransomNote的长度即length即可。

哈希法
时间复杂度：O(n)
空间复杂度：O(1)

和我上面的思路基本一致。

哈希法使用空间来换取时间，

实现

暴力法实现 

1
2
3
4
5
6
7
8
9
10
11
for(int i= 0; i < magzine.size(); i++) {
	for(int j = 0; j < ransomNote..size(); j++) {
		if(magzine[i] == ransomNote[j]) {
			ransomNote.erase(ransomNote.begin() + j);
			break;
		}
	}
}

if(ransomNote.size() == 0) return true;
else return false;

哈希法参考上面我的思路。

15. 三数之和

题目链接：15. 三数之和
文档讲解：15. 三数之和
视频讲解：梦破碎的地方！| LeetCode：15.三数之和
目标：
状态：

学习前的想法

题目给定一个包含n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得a + b + c = 0，找出所有满足条件且不重复的三元组。

只给了一个数组，还要求三元组不能重复且i != j != k，卡哥给的建议是使用双指针，因为哈希法很麻烦，于是下面开始考虑双指针法。

。。。

没有思路。

学习后的想法

哈希解法

两层for循环可以确定所有a + b的值，可以用哈希法来确定0 - (a + b)是否再数组中出现过，这样的思路是正确的，但是比较复杂的是题目不允许出现重复的三元组。

如果在找出所有可能组合后，再进行去重，是很费时的操作，因此不建议使用哈希法来解决此题。

双指针法

假设三个指针分别为i，left，right

首先需要将数组排序，通过i来遍历整个数组，在遍历过程中，分别令三个指针分别指向下标为0，1，nums.size() - 1的位置，计算其三数之和，如果大于0，则需要将right向左移动，反之，left向后移动。

比较值得注意的是去重操作，下面分别说明这个三个指针即三个数如何去重。

对于i，如果当前位置的值等于其前一个位置即i-1的值，则需要跳过该循环。对于为什么不是i和i+1的位置比较，这是因为left指向的是i+1位置，如果以这种方式作比较的话，会忽略掉 i 和 left 取值相同的情形。

例如-1,-1,2这种情况。

对于left，如果其值等于其后一位的值，则跳过。

对于right，如果其值等于其前一位的值，则跳过。

此外，在对left和right进行跳步之前，需要先进行一次保存，因为我们对left和right的循环终止条件是，left < right，如果不先保存一次，则会漏掉一次当前组合。

例如0, 0, 0

实现

哈希法代码不给出，感兴趣的可以去代码随想录网站学习。

2024/2/28
我只会给出我自己理解并搞懂的方法的代码，现阶段确实没时间去把所有方法搞明白

双指针法 

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
vector<vector<int>> result;

sort(nums.begin(), nums.end());

for(int i = 0; i < nums.size(); i++) {
	if(nums[i] > 0) return result;
	
	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]});
			while(right > left && nums[right] == nums[right - 1]) right--;
			while(right > left && nums[left] == nums[left + 1]) left++;
			right--;
			left++;
		}
	}
}
return result;

18. 四数之和

题目链接：18. 四数之和)
文档讲解：18. 四数之和)
视频讲解：难在去重和剪枝！| LeetCode：18. 四数之和
目标：
状态：

学习前的想法

题目需要从数组nums中找出A，B，C，D四个数，使其相加之后的和等于目标值target，四个数的下标不相同，且四元组不能重复。

由于时间原因，直接学习如何解决此题。

学习后的想法

前面学习的三数之和，使用了双指针法。而四数之和是在三数之和的基础上，再加上一层for循环。

主要就是下面的几个问题：

如何剪枝？
如何对四个数分别去重？

实现

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
50
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) {
            	break; // 这里使用break，统一通过最后的return返回
            }
            // 对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) {
                    break;
                }

                // 对nums[i]去重
                if (i > k + 1 && nums[i] == nums[i - 1]) {
                    continue;
                }
                int left = i + 1;
                int right = nums.size() - 1;
                while (right > left) {
                    // nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出
                    if ((long) nums[k] + nums[i] + nums[left] + nums[right] > target) {
                        right--;
                    // nums[k] + nums[i] + nums[left] + nums[right] < target 会溢出
                    } else if ((long) nums[k] + nums[i] + nums[left] + nums[right]  < target) {
                        left++;
                    } else {
                        result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
                        // 对nums[left]和nums[right]去重
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;

                        // 找到答案时，双指针同时收缩
                        right--;
                        left++;
                    }
                }

            }
        }
        return result;
    }
};

收获与学习时长

学习时长： 3h

收获

感觉这几题挺难的，还是需要多练，多思考。

总结

2024/2/28
由于学业繁忙，今后的博客会比较粗糙，只是记录一些自己的想法，后续有时间了会逐渐补充完善，更新频率也会降低，可能几天才会更新一篇，望谅解。