day7 记录代码随想录
第一题 力扣454.四数相加II
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。
例如:
输入:
- A = [ 1, 2]
- B = [-2,-1]
- C = [-1, 2]
- D = [ 0, 2]
输出:
2
解释:
两个元组如下:
- (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
- (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
题目链接：力扣题目链接
解题思路：
这道题，我首先想到的是将四个数组分解为两个数组，这样就简化称为了两数相加的题。
因为只需要返回元祖数量，那么将值存入就可以了，所以我考虑使用multiset来做。
首先将nums1[i] + nums2[j] 遍历存入 sum1中
然后遍历查找sum1中符合 0 - nums[3] - num[4] 的元素数量，就得到了元祖数量。
代码如下：
//一个错误做法
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
multiset<int> sum1;
int count = 0;
int n = nums1.size();
for(int i = 0 ; i < n ; i++ ) {
for( int j = 0 ; j < n ; j++ ) {
sum1.insert(nums1[i]+nums2[j]);
}
}
for(int i = 0 ; i < n ; i++ ) {
for( int j = 0 ; j < n ; j++ ) {
if( sum1.find(-nums3[i]-nums4[j]) != sum1.end() )
count++;
}
}
return count;
}
};很显然，结果出错了。原因在哪里呢？
在于find这一步，由于sum1.find()只能找到一个符合的变量，所以就算num1中有多个相同的符合条件的值，count也只会加一次。
如何修改呢？
第一种方法是保留使用multiset，在find这里采用for循环遍历sum1赋值对比。
//超时了o(╥﹏╥)o
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
multiset<int> sum1;
int count = 0;
int n = nums1.size();
for(int i = 0 ; i < n ; i++ ) {
for( int j = 0 ; j < n ; j++ ) {
sum1.insert(nums1[i]+nums2[j]);
}
}
for(int i = 0 ; i < n ; i++ ) {
for( int j = 0 ; j < n ; j++ ) {
for(auto& sum:sum1) {
if( sum == ( -nums3[i] - nums4[j] ) )
count++;
}
}
}
return count;
}
};很遗憾，三重循环超时了，不得不改用其他方法。
第二种方法是放弃set采用map映射。
对于本题来说，只需要给出最后的数量，那么map映射的key和value分别可以设置成“数值”和“数量”，这样一来，只需要查找符合条件的“数值”的map.value就可以了。
代码如下：
//使用map映射
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int,int> mymap;
int n = nums1.size();
int count = 0;
for(int i = 0 ; i < n ; i++ ) {
for ( int j = 0 ; j < n ; j++) {
mymap[nums1[i] + nums2[j]]++; //新语法：元素对应的值加一
}
}
for(int a:nums3) {
for(int b:nums4) {
if ( mymap.find(-a-b) != mymap.end() )
// count += mymap.find(-a-b)->second;
count += mymap[-a-b];
}
}
return count;
}
};这里有一个for循环的新用法：for(int a:nums3)，是将num3中的值依次赋值给a做循环操作。
时间复杂度为O(n^2)
第二题 力扣383. 赎金信
给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。
(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)
注意：
你可以假设两个字符串均只含有小写字母。
canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true
题目链接：力扣题目链接
解题思路：
本题关键词有：对比，重复，使用哈希表来做很简单
选择数组来实现哈希表，可以完整地将magazine存入，并且由于只有小写字母所以数组大小只需要26即可。数据跨度小，且可重复很符合数组的使用条件。
代码如下：
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int mag[26] = {0};
for(int i = 0 ; i < magazine.size() ; i++ ) {
mag[magazine[i] - 'a']++;
}
for ( int i = 0 ; i < ransomNote.size() ; i++) {
mag[ransomNote[i] - 'a']--;
if( mag[ransomNote[i] - 'a'] < 0 ) {
return 0;
}
}
return true;
}
};第三题 力扣 15.三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意： 答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]
题目链接：力扣题目链接
解题思路：
看到三数之和，很容易想到昨天的两数之和，两数之和采用了map映射来做，将数组的下标与数值存在map中，然后遍历数组去map中找值。
那么对于此题，是不是也可以考虑使用map呢？
构思一下，固定一个数，然后用两重for循环遍历数组去找map中的值。
看起来是可以的，但是有个问题时题目中要求不能包含重复的三元组，即[-1,-1,2]只能用一次，但是在上面的构思中，去重是个十分棘手的操作。
放弃map，尝试使用别的办法。
此题中并不考虑a,b,c的顺序，那么是否可以提前给nums排序一下。
对于有序数组，固定一个值查找另外一个值，很容易想到双指针法。
使用for循环，遍历固定 i ，再定义两个指针 left 和 right ，在 i<left<right 的范围内移动left和right查找对应的值，就可以实现。
移动查找的循环条件为 left <right
当nums[i] + nums[left] + nums[right] == 0 时，将此时的三个值存入result中，考虑到需要去重，判断一下left与其右边是否相等，相等则跳过，同样的，判断right与其左边是否相同，相等则跳过，然后left右移，right左移。
当nums[i] + nums[left] + nums[right] < 0 时，则说明三个数的值太小，此时将较小的数 left 增加一点（右移）
同样的，当nums[i] + nums[left] + nums[right] > 0 时，则说明三个数的值太大，此时将较大的数 right 减小一点（左移）
对于 i 来说，也需要去重，判断 i > 0 && nums[i] == nums[i - 1]，符合直接跳过此次循环
这里需要注意的是不能使用nums[i] == nums[i + 1] 来判断，因为这样的话会将left挤出去，导致缺失值。
代码如下：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
int left;
int right;
for (int i = 0; i < nums.size(); i++) {
left = i + 1;
right = nums.size() - 1;
if (i > 0 && nums[i] == nums[i - 1])
continue;
while (left < right) {
if (nums[i] + nums[left] + nums[right] == 0) {
result.push_back({nums[i], nums[left], nums[right]});
while (left < right && nums[right] == nums[right - 1])
right--;
while (left < right && nums[left] == nums[left + 1])
left++;
left++;
right--;
}
else if (nums[i] + nums[left] + nums[right] < 0)
left++;
else
right--;
}
}
return result;
}
};时间复杂度为O（n^2）
双指针法将原本时间复杂度为O（n^3）的解法优化为了O（n^2）的解法。
第四题 18. 四数之和
题意：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
示例： 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
提示：
1 <= nums.length <= 200-10^9 <= nums[i] <= 10^9-10^9 <= target <= 10^9
题目链接：力扣题目链接
解题思路：
四数之和与三数之和的解题思路基本一致，也是采用双指针法。
不过这里需要用双重for循环来固定两个数 i , j ，然后采用对撞指针来找值。
这里需要注意的有两个点：
1）题目给的值大小为-10^9 <= nums[i] <= 10^9，而int的大小为2^31-1，是负的21亿多到正的21亿多，如果三个足够大的数相加就会导致数值越界，此时需要使用 (long) 来进行强制类型转换
2）在循环过程中，有些条件是肯定不符合题意的，比如nums[i] > target && nums[i] > 0，对于这部分，直接跳过就可以了，这个操作叫做“剪枝”，能够增加运行效率。
代码如下：
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
int left;
int right;
for (int i = 0; i < nums.size(); i++) {
if(nums[i] > target && nums[i] > 0) //剪枝
break;
if(i > 0 && nums[i] == nums[i-1])
continue;
for (int j = i + 1; j < nums.size(); j++) {
if( nums[i] + nums[j] > target && nums[i] + nums[j] > 0) //二重剪枝
break;
if(j > i + 1 && nums[j] == nums[j-1])
continue;
left = j + 1;
right = nums.size() - 1;
while( left < right ) {
if ((long) nums[i] + nums[j] + nums[left] + nums[right] == target) {
result.push_back({nums[i], nums[j], nums[left], nums[right]});
while (left < right && nums[right] == nums[right-1])
right--;
while (left < right && nums[left] == nums[left+1])
left++;
left++;
right--;
}
else if((long) nums[i] + nums[j] + nums[left] + nums[right] < target)
left++;
else
right--;
}
}
}
return result;
}
};时间复杂度为O（n^3）
双指针法将原本时间复杂度为O（n^4）的解法优化为了O（n^3）的解法。
总结：数组、set、map是实现哈希表的三种方法，分别具有其适用条件和范围，也各有优缺点，同时还有multi 和 unordered 分别用来处理重复和无序不重复的元素，需要结合不同的功能来选择不同的方法实现。双指针算法是一种强大的算法，对于有序的数组来说十分适用，并且相关操作（如去重）的代码也很简洁，且效率很高，双指针法将原本时间复杂度为O（n^3）的解法优化为了O（n^2）的解法。
部分图文出自代码随想录。
标签：vector,四数,15,nums,int,随想录,++,right,left From： https://blog.csdn.net/zhang1282882326/article/details/136657547