454. 四数相加II
原题链接
解题思路：
哈希表：
- a+b+c+d=0；存在 a+b = 0 - (c + d)；
- 那么预处理提前将 a+b 的值存入哈希表中。
- 然后再去搜寻 0 - (c+d) 的值，累加次数。
实现代码：
class Solution {
public:
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
int cnt=0;
unordered_map<int, int> umap;
for (int a:A) {
for (int b:B) {
umap[a+b] ++;
}
}
for (int c:C) {
for (int d:D) {
if (umap.find(0-(c+d)) != umap.end()) {
cnt += umap[0 - (c+d)];
}
}
}
return cnt;
}
};
时间复杂度：O(n^2)
空间复杂度：O(n^2)，最坏情况下A和B的值各不相同，相加产生的数字个数为 n ^2。
383. 赎金信
原题链接
解题思路：
暴力法：别人的
- 设计两层for循环，然后外层for循环负责遍历magazine字符串。
- 内层循环负责在ransom字符串里面寻找对应的当前magazine[i] 字符，找到后并进行删除ransom[j]，因为下次还可能再寻找，避免出现重复。
- 总之就是，外层循环，每次从magazine字符串里面依次取出一个字符，然后将该字符，用来去看ransom字符串里面是否有对应的字符，有的话，说明构成ransom中的一个字符，然后将ransom这个字符删除，因为已经被组建了，避免重复消耗！
实现代码：
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 ++) {
if (magazine[i] == ransomNote[j]) {
ransomNote.erase(ransomNote.begin() + j);
break;
}
}
}
if (ransomNote.size == 0)
return true;
else return false;
}
};
哈希表：别人的
- 题意是：用magazine里面的字符构建ransom字符串，所以说首先的一个条件就是ransom的字符串长度必须 <= magazine字符串。
- 然后我们可以累加 magazine字符串里面的每个字符的个数。
- 然后遍历ransom字符串，去消耗之前magazine里面的字符次数。如果某个字符的次数被消耗为0，则表示凑不出ransom字符串。返回false；
实现代码：
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int n1 = ransomNote.size();
int n2 = magazine.size();
if (n1 > n2) return false;
int record[26] = {0};
for (int i=0; i < n2; i ++) {
record[magazine[i] - 'a'] ++;
}
for (int i=0; i < n1; i ++) {
record[ransomNote[i] - 'a'] --;
if (record[ransomNote[i] - 'a'] < 0) {
return false;
}
}
return true;
}
};
15. 三数之和
原题链接
解题思路：
暴力法：自己的
- 三层循环；
- 外层循环枚举第一个数：a；
- 中层循环枚举第二个数：b；
- 内层循环枚举第三个数：c；
时间复杂度：O(n^3)；
超时的！
双指针：别人的（优化）
- 排序，然后枚举第一个数，利用有序性，后面两个数用双指针扫描。
- 相比于上面的两层for循环O(n^2)扫描无疑是超时的。而用双指针扫描，则是O(n)的。
- 排序后，当前的序列呈非递减、允许相等的递增。
- 枚举第一个数nums[i]，然后剪枝去重。因为有序，如果第一个数为正，三数之和不可能为0。如果nums[i] = nums[i-1]，则跳过该数。
- 利用有序性，第二个数和第三个数双指针扫描。如果三数之和sum=0，则记录答案，左右两侧去重，若sum < 0，则l ++，r – ；继续搜索。
时间复杂度：O(n^2)；文章来源：https://www.toymoban.com/news/detail-614163.html
实现代码：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
int n = nums.size();
if (n < 3) {
return ans;
}
for (int i=0; i < n; i ++) {
if (nums[i] > 0) {
break; //剪枝！
}
if (i > 0 && nums[i] == nums[i-1]) continue; //去重！
for (int l=i+1, r = n - 1; l < r; ) {
int res = nums[i] + nums[l] + nums[r];
if (res == 0) {
ans.push_back({nums[i], nums[l], nums[r]});
l ++, r --; //排除两个元素
while (l < r && nums[l] == nums[l-1]) l ++; //左侧去重！
while (r > l && nums[r] == nums[r+1]) r --; //右侧去重！
}
else if (res < 0) {
l ++;
}
else {
r --;
}
}
}
return ans;
}
};
18. 四数之和
原题链接
解题思路：
双指针：自己的
- 观察数据范围；
- 暴力的话，则是四重循环，从左往右依次枚举。
- 排序：从小到大枚举！
- 那么我们可以采用双指针的算法。优化掉最里面的两层循环，优化为一层循环。
- 最终还是三层循环：外两层，枚举前两个数，内一层，采用双指针扫描后面的数。
- 一个指针指向左边，另一个指针指向末尾，然后分情况移动。
- 当四个数之和相加 == target 的时候，则将当前的四个数记录下来。然后由于要去重，我们就不断地让左指针和右指针先同步向内移动一个单位，然后先从左边元素去重，再从右边元素去重。因为排序后，相等的元素必定是会堆积到一起的！
- 如果四数之和大于了target的话，则说明当前过大，我们需要降低某个元素的值，那么就可以降低右边指针的，将右指针向左移动一个单位，使得第四个元素的值减小。
- 如果小于了target的话，则右移左指针。
实现代码：
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int n = nums.size();
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
for (int i:nums) {
cout << i << " ";
}
if (n < 4) {
return ans;
}
for (int i=0; i < n - 3; i ++) {
if (i > 0 && nums[i] == nums[i-1]) continue;
for (int j=i+1; j < n-2; j ++) {
if (j > i+1 && nums[j] == nums[j-1]) continue;
int l = j + 1, r = n - 1;
while (l < r) {
long res = (long)nums[i] + nums[j] + nums[l] + nums[r];
if (res == target) {
ans.push_back({nums[i], nums[j], nums[l], nums[r]});
l ++ , r --;
while (l < r && nums[l] == nums[l-1]) l ++;
while (l < r && nums[r] == nums[r+1]) r --;
}
else if (res > target) {
r --;
}
else {
l ++;
}
}
}
}
return ans;
}
};
今日总结：
哈希表可以比对两个数据结构里面的元素。
当枚举一个序列的时候，可以使用双指针进行枚举，而双指针每次最多只能枚举两个数，若要枚举三个数，或者三个及以上的数，则需要先提前将前面的数采用嵌套for循环的方式进行枚举，然后双指针的优势是将两层for循环变为一层，即O(n^2) 变为 O(n)，所以说嵌套for循环需要最后预留两个数，使用双指针进行枚举，从而将O(n ^ x) 优化为：O(n ^ x-1)；文章来源地址https://www.toymoban.com/news/detail-614163.html
到了这里，关于力扣 [454、383、15、18]的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
