四数之和II
在这道题中我们要做的是寻找次数，所以在这个代码中这个次数就是value因为我们是通过key来寻找value。所以为了寻找这个次数我们需要把这个我们要找的数当做值，由此我们需要根据键来寻找值！！！
#include<iostream>
#include<unordered_map>
using namespace std;
#include<vector>
int fan_num(vector<int>&u,vector<int>&v, vector<int>&z, vector<int>&w)
{
int cishu = 0;
unordered_map<int, int>x;
for (int num : u)
{
for (int num2 : v)
{
x[num+num2]++;//num+num=key ++=value 前者叫键 后者叫值 在代码中都是按照find来找键
}
}
for (int num : z)
{
for (int num2 : w)
{
if (x.find(0 - num - num2) != x.end())
{
cishu += x[0 - num - num2];
}
}
}
return cishu;
}
int main()
{
vector<int>u, v, z, w;
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
int num;
cin >> num;
u.push_back(num);
}
for (int i = 0; i < n; i++)
{
int num;
cin >> num;
v.push_back(num);
}
for (int i = 0; i < n; i++)
{
int num;
cin >> num;
z.push_back(num);
}
for (int i = 0; i < n; i++)
{
int num;
cin >> num;
w.push_back(num);
}
cout<< fan_num(u, v, z, w);
}赎金信
这个代码中这个我们需要看看这个不需要key和value，我们在上面的代码中我么之所以那么写是在于我们要记录次数。但是在这个赎金信中我们不需要去记录这个value的具体值，我们要做的是对其数值进行加加减减。
#include<iostream>
using namespace std;
#include<string>
bool panduan(string s1, string s2)
{
int arr[26] = { 0 };
if (s1 > s2)
{
return false;
}
for (int i = 0; i < s1.size(); i++)
{
arr[s1[i] - 'a']++;
}
for (int i = 0; i < s2.size(); i++)
{
arr[s2[i] - 'a']--;
}
for (int i = 0; i < 26; i++)
{
if (arr[i] > 0)
{
return false;
}
}
return true;
}
int main()
{
string s1, s2;
cin >> s1 >> s2;
cout<<panduan(s1, s2);
}三数之和
在这道题里面我认为比较重要的点在于对于去重，首先我们应该先确定我们做这道题的目标，我们这个去重是指对于这个答案去重，不是对于0 0 0去重这个答案是对的，我们设一个i这个是我们要找的与他相加和为0的值，我们为了能过够更快捷，更方便找三个数我们不应该选哈希方法，这个哈希法与我们前面写的两个数的和像。
#include<iostream>
#include<algorithm>
using namespace std;
#include<vector>
vector<vector<int>>chazhao(vector<int>u)
{
vector<vector<int>>v;
sort(u.begin(), u.end());
for (int i = 0; i < u.size(); i++)
{
if (u[i] > 0)
{
return v;
}
if (i>0&&u[i] == u[i - 1])
{
//i++
continue;//这个地方得这么写
}
int left = i + 1;
int right = u.size() - 1;
while (left < right)
{
if (u[left] + u[right] + u[i] > 0)
{
right--;
}
else if (u[left] + u[right] + u[i] < 0)
{
left++;
}
else
{
v.push_back({ u[left],u[i],u[right] });
while (left < right && u[left] == u[left + 1])left++;
while (left < right && u[right] == u[right - 1])right--;
left++;
right--;
}
}
}
return v;
}
int main()
{
int n;
cin >> n;
vector<int>u;
for (int i = 0; i < n; i++)
{
int num;
cin >> num;
u.push_back(num);
}
vector<vector<int>>v=chazhao(u);
for (auto num : v)
{
for (int num2 : num)
{
cout << num2 << " ";
}
cout << endl;
}
}四数之和
这个地方一定要仔细思考哦~~~~
#include<iostream>
using namespace std;
#include<algorithm>
#include<vector>
vector<vector<int>>chazhao(vector<int>u,int target)
{
vector<vector<int>>v;
sort(u.begin(), u.end());
for (int k = 0; k < u.size(); k++)
{
if (u[k] > target && u[k] >= 0)
{
break;
}
if (k > 0 && u[k] == u[k - 1])continue;
for (int i = k + 1; i < u.size(); i++)
{
if (u[k]+u[i] > target && u[k]+u[i] >= 0)
{
break;
}
if (i > k + 1 && u[i] == u[i - 1])
{
// break;
continue;
}
int left = i + 1;
int right = u.size() - 1;
while (left < right)
{
if (u[k] + u[i] + u[left] + u[right] > target)
{
right--;
}
else if (u[k] + u[i] + u[left] + u[right] < target)
{
left++;
}
else
{
v.push_back({ u[k],u[i],u[left],u[right] });
v.push_back({ u[left],u[i],u[right] });
while (left < right && u[left] == u[left + 1])left++;
while (left < right && u[right] == u[right - 1])right--;
left++;
right--;
}
}
}
}
return v;
}
int main()
{
int tar;
cin >> tar;
int n;
cin >> n;
vector<int>u;
for (int i = 0; i < n; i++)
{
int num;
cin >> num;
u.push_back(num);
}
vector<vector<int>>v = chazhao(u,tar);
for (auto num : v)
{
for (int num2 : num)
{
cout << num2 << " ";
}
cout << endl;
}
}上面这个代码虽然有点问题，但是还没找到：（
下面这个正确
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
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 && target >= 0) {
break;
}
// 对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 && target >= 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) {
long long sum = (long long) nums[k] + nums[i] + nums[left] + nums[right];
if (sum > target) {
right--;
} else if (sum < target) {
left++;
} else {
result.push_back({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;
}
int main() {
int tar, n;
cout << "请输入目标值: ";
cin >> tar;
cout << "请输入数组的大小: ";
cin >> n;
vector<int> u(n);
cout << "请输入数组元素: ";
for (int i = 0; i < n; i++) {
cin >> u[i];
}
vector<vector<int>> v = fourSum(u, tar);
cout << "满足条件的四元组有: " << endl;
for (const auto& num : v) {
for (int num2 : num) {
cout << num2 << " ";
}
cout << endl;
}
return 0;
}