题目： 454.四数相加II
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
0 <= i, j, k, l < nnums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
思路：和昨天的两数之和即为相似，此处有4个数组，因此只需要将两个数组两两相加组合成2个数组即可按照两数之和的思路解题。
注意：需要使用map的主要原因是，两个数组两两相加的时候可以会有多组元素的和等于同一值，因此map中的key代表的是相加后的和，而value指的是这个和所出现的次数。
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int,int> nums_map;
for(int i = 0;i < nums1.size();i++){
for(int j =0;j < nums2.size();j++){
nums_map[nums1[i] + nums2[j]] +=1;
}
}
int count = 0;
for(int i = 0;i < nums3.size();i++){
for(int j =0;j < nums4.size();j++){
if(nums_map.find(0-nums3[i]-nums4[j]) != nums_map.end()){
count += nums_map[0-nums3[i]-nums4[j]];
}
}
}
return count;
}
};题目：383. 赎金信
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
思路：这道题目和昨天做的 242.有效的字母异位词 类似，都可以用数组实现，题目较为简单不做叙述，下面将给出代码。
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int record[26] = {0};
for(int i = 0; i<magazine.size();i++){
record[magazine[i]-'a'] += 1;
}
for(int j = 0; j<ransomNote.size();j++){
record[ransomNote[j]-'a'] -=1;
if(record[ransomNote[j]-'a']<0){
return false;
}
}
return true;
}
};题目：15. 三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
思路：初次做这道题目的时候会发现去重是一个很麻烦的事情，时常因为去重不到位而导致输出结果重复。本体的方法为双指针发，分别是left,right，去重需要对left,right以及for循环的i都要去重。去重逻辑如下，在每一次的循环中指针指向的值不能重复：
if(i>0 && nums[i] == nums[i -1])
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;去重需要注意的：指针之间不要碰撞上，不要超出数组的索引值。
代码如下：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> result;
for(int i = 0; i < nums.size()-2;i ++){
if(i>0 && nums[i] == nums[i -1]){ //去重逻辑
continue;
}
int left = i+1;
int right = nums.size()-1;
while(right>left){
if(nums[i]+nums[left]+nums[right] <0){
left ++;
}else if(nums[i]+nums[left]+nums[right] >0){
right --;
}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++;
left ++;
right --;
}
}
}
return result;
}
};题目：18. 四数之和
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < na、b、c和d互不相同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]]思路：和 15. 三数之和 类似，只是多了一层for循环，依然采用的是双指针，需要去重的包含了两个for循环的中的i和j以及双指针left,right
去重注意事项：指针之间不要碰撞上，不要超出数组的索引值。
自己写的时候没考虑剪纸操作，因此下面的代码中也将没有剪枝操作
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
sort(nums.begin(),nums.end());
for(int i = 0;i < nums.size();i++){
//i去重逻辑
if(i > 0 && nums[i] == nums[i-1]){
continue;
}
for(int j = i+1; j<nums.size();j++){
//j去重逻辑
if(j > i+1 && nums[j] == nums[j-1]){
continue;
}
int left = j+1;
int right = nums.size()-1;
while(right > left){
if((long)nums[i] + nums[j] + nums[left]+nums[right] > target){
right -- ;
}else if((long)nums[i] + nums[j] + nums[left]+nums[right] < target){
left ++;
}else{
result.push_back(vector<int>{nums[i],nums[j],nums[left],nums[right]});
//找到值了之后需要开始去重
while(right > left && nums[left] == nums[left + 1]){
left ++;
}
while(right >left && nums[right] == nums[right - 1]){
right --;
}
left ++;
right --;
}
}
}
}
return result;
}
};
评论