字母异位词分组
题目来源：leetcode
1、问题描述
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
2、思路解析
思路一：暴力破解
双循环判断当前字符串和后边的字符串是不是字母异位词，内判断当前字符串就是一次循环，还有判断是不是异位词，也要一次循环时间复杂度接近O(N^3)，虽然说思想是哈希但是，时间复杂度太高了。还有每次取完数据还要一次排序。
思路二：字符串排序为键值+哈希
同一组字母异位词中的字符串具备相同点，可以使用相同点作为一组字母异位词的标志，使用哈希表存储每一组字母异位词，哈希表的键为一组字母异位词的标志，哈希表的值为一组字母异位词列表。
遍历每个字符串，对于每个字符串，得到该字符串所在的一组字母异位词的标志，将当前字符串加入该组字母异位词的列表中。遍历全部字符串之后，哈希表中的每个键值对即为一组字母异位词。由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。
3、代码实现
class Solution {
public:
bool _groupAnagrams(string s, string t) {
vector<int> v(128, 0);
for (int i = 0;i < s.size();i++) {
v[s[i]]++;
}
for (int i = 0;i < t.size();i++) {
v[t[i]]--;
}
for (int i = 0;i < 128;i++) {
if (v[i] != 0) {
return false;
}
}
return true;
}
struct cmp{
bool operator ()(vector<string>&a,vector<string>&b){
return a.size()<b.size();
}
}cmp;
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> v;
for (int i = 0;i < strs.size();i++) {
vector<string> s;
if (strs[i] == " ") {
continue;
}
s.push_back(strs[i]);
for (int j = i + 1;j < strs.size();j++) {
if (_groupAnagrams(strs[i], strs[j])) {
s.push_back(strs[j]);
strs[j] = " ";
}
}
sort(s.begin(), s.end());
v.push_back(s);
}
sort(v.begin(), v.end(),cmp);
return v;
}
};
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string,vector<string>> m;
vector<vector<string>> v;
for(int i=0;i<strs.size();i++){
//将字符串排序
//对于字母异位词---排序后的组合都是相同的
string k=strs[i];
sort(k.begin(),k.end());
//将属于 同一类的字母异味词存储到排序后的位置
m[k].push_back(strs[i]);
}
//遍历拿出元素
for(auto o:m){
//元素排序
sort(o.second.begin(),o.second.end());
v.push_back(o.second);
}
return v;
}
};
三数之和
题目来源：leetcode
1、问题描述
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
2、思路解析
思路一：DFS+回溯
DFS寻找所有组合中符合条件的组合，但是要先找到3个元素的所有组和，接着在这些组合寻找符合条件的组合。时间大多花费在寻找组合的事情上判断 a + b + c = 0 ？只需要一步就可以
思路二：哈希+排序
3、代码实现
class Solution {
public:
void DFS(set<vector<int>>&s,vector<vector<int>>&v,vector<int> &vm,vector<int> &num,vector<int> &vs,int &&sum){
//判断有没有满足条件
if(vm.size()>=3){
if(vm.size()==3&&sum==0){
//满足条件将结果保存下来
//排序加去除
vector<int>vl(vm);
sort(vl.begin(),vl.end());
if(s.find(vl)==s.end()){
s.insert(vl);
v.push_back(vl);
}
}
return;
}
for(int i=0;i<num.size();i++){
//先判断数据有没有使用
if(vs[i]==0){
vs[i]=1;
vm.push_back(num[i]);
BFS(s,v,vm,num,vs,sum+num[i]);
//不满足条件回溯
vm.pop_back();
vs[i]=0;
}
}
}
vector<vector<int> > threeSum(vector<int> &num) {
//首先满足数组长度必须大于3
vector<vector<int>>v;
if(num.size()<3){
return v;
}
vector<vector<int>>l={{-1,0,1},{0,0,0}};
if(num.size()>200){
return l;
}
set<vector<int>>s;
//标记矩阵
vector<int>vs(num.size(),0);
sort(num.begin(),num.end());
//存储中间数据
vector<int> vm;
BFS(s,v,vm,num,vs,0);
return v;
}
};
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
//先排序
vector<vector<int>> v;
if(nums.size()<3){
return v;
}
sort(nums.begin(),nums.end());
set<vector<int>>s;
for(int i=0;i<nums.size();i++){
int l=i+1;
int r=nums.size()-1;
while(l<r){
if(nums[i]+nums[l]+nums[r]==0){
s.insert({nums[i],nums[l],nums[r]});
l++;
r--;
}else if(nums[i]+nums[l]+nums[r]<0){
//寻诈骗更大的数
l++;
}else if(nums[i]+nums[l]+nums[r]>0){
//寻找更小的数
r--;
}
}
}
for(auto &o:s){
v.push_back(o);
}
return v;
}
};
四数之和
题目来源：leetcode
1、问题描述
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
3、思路解析
思路一：四层for循环暴力破解
每一层寻找一个符合要求的元素，最后将符合条件的元素保存下来，时间复杂度为O(N^4)
思路二：
3、代码实现
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> v;
sort(nums.begin(),nums.end());
set<vector<int>> s;
for(int i=0;i<nums.size();i++){
for(int j=i+1;j<nums.size();j++){
//去重
int begin=j+1;
int end=nums.size()-1;
int sum=target-nums[i]-nums[j];
//找到两数之和即可
while(begin<end){
if(nums[begin]+nums[end]==sum){
//找到
s.insert({nums[i],nums[j],nums[begin],nums[end]});
begin++;
end--;
}else if(nums[begin]+nums[end]<sum){
begin++;
}else{
end--;
}
}
}
}
for(auto o:s){
v.push_back(o);
}
return v;
}
};
还可以不使用hash数据结构去重，因为使用hash是还需要将数据映射到哈希表中这也浪费了不少时间，所以直接去重效果会更好。
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> v;
sort(nums.begin(),nums.end());
set<vector<int>> s;
for(int i=0;i<nums.size();i++){
//去重
if(i>0&&nums[i]==nums[i-1]) continue;
for(int j=i+1;j<nums.size();j++){
//去重
if(j>i+1&&nums[j]==nums[j-1]) continue;
int begin=j+1;
int end=nums.size()-1;
int sum=target-nums[i]-nums[j];
//找到两数之和即可
while(begin<end){
if(nums[begin]+nums[end]==sum){
//找到
v.push_back({nums[i],nums[j],nums[begin],nums[end]});
//去重
while(begin<end&&nums[begin]==nums[begin+1]) begin++;
while(begin<end&&nums[end]==nums[end-1]) end--;
begin++;
end--;
}else if(nums[begin]+nums[end]<sum){
begin++;
}else{
end--;
}
}
}
}
// for(auto o:s){
// v.push_back(o);
// }
return v;
}
};
可以看出不加哈希时间执行减少到原来的五分之一，可见并不是使用了hash效率会增加，有可能效率反而会减少
