LeetCode 454.四数相加Ⅱ
题目：
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：1、0 <= i, j, k, l < n；2、nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0。
思路：
这道题的解题思路和leetcode242很相似。这里有4个数组，将他们两两分组相加，这样就得到了两个和数组A，B，最后只需要在A中寻找值为-B的元素就行了。因为这里要考虑重复的情况（例如：1+0=1；2-1=1），应该在和数组中还要有一个变量保存相同值重复的次数，所以这里选用map结构来保存和数组A、B。
代码：
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int,int> temp;
int count=0;
for(int a:nums1)
{
for(int b:nums2)
{
temp[a+b]++;
}
}
for(int c:nums3)
{
for(int d:nums4)
{
int res=0-(c+d);
if(temp.find(res)!=temp.end())
{
count+=temp[res];
}
}
}
return count;
}
};
LeetCode 383.赎金信
题目：
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。如果可以，返回 true ；否则返回 false 。magazine 中的每个字符只能在 ransomNote 中使用一次。
思路：
这道题和上一道题的思路都是一样的，先把一个数组存着，然后再在这个数组里寻找与另一个数组相同的元素。
代码：
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int temp[26]={0};
if(ransomNote.size()>magazine.size())
{
return false;
}
for(char a:magazine){
temp[a-'a']++;
}
for(char b:ransomNote)
{
int res=b-'a';
temp[res]--;
if(temp[res]<0)
{
return false;
}
}
return true;
}
};
LeetCode 15.三数之和
题目：
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。
思路：
首先先对数组排序，定义三个指针i、j、k，最开始i指向nums[0]、j指向i的下一个位置、k指向nums的最后一个位置。对i进行for循环遍历，在遍历过程中如果nums[i]+nums[j]+num[k]>0，说明和大了要将nums[k]减小，k--；如果nums[i]+nums[j]+num[k]<0，说明和小了要将nums[j]增大，j++;直到三个数相加和为0时，保存此时的下标。
这道题的关键点在于不能重复：（1）i、j、k不能重复,j、k分别从i的下一位、nums的尾部开始遍历就能保证这一点；（2）得到的三元组不能重复,为了实现不重复，要对三个数进行去重：对于i，如果nums[i]==nums[i-1]，则说明这次循环的i值和上一次循环的i值说相等的，应该跳过这次循环，注意nums[i]==nums[i+1]表达的是三元组中第一个元素和第二个元素不能相等，与题目要求不符合。对于j、k，在保证三数之和为0后再判断它们的下一个值是否跟这次的值相同，若相同则跳过。
代码:
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();i++)
{
if(nums[i]>0) return result;
if(i>0 && nums[i]==nums[i-1]) continue;
int j=i+1;
int k=nums.size()-1;
while(j<k)
{
int sum=nums[i]+nums[j]+nums[k];
if(sum>0)
{
k--;
}else if(sum<0)
{
j++;
}else{
result.push_back(vector<int>{nums[i], nums[j], nums[k]});
while(j<k && nums[j]==nums[j+1])j++;
while(j<k && nums[k]==nums[k-1])k--;
j++;
k--;
}
}
}
return result;
}
};
LeetCode 18.四数之和
题目：
给你一个由 n 个整数组成的数组nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]]（若两个四元组元素一一对应，则认为两个四元组重复）：（1）0 <= a, b, c, d < n，a、b、c 和 d 互不相同；（2）nums[a] + nums[b] + nums[c] + nums[d] == target.你可以按 任意顺序 返回答案 。
思路：
这道题和上一道题说一样的解法，只不过在外层又加了一层for循环。这道题要注意两层for循环的去重，还有四个数的和可能会超过int的表示范围，要用类型转换。
代码：
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;
}
if (k > 0 && nums[k] == nums[k - 1]) {
continue;
}
for (int i = k + 1; i < nums.size(); i++) {
if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
break;
}
if (i > k + 1 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (right > left) {
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(vector<int>{nums[k], 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;
}
};
