【练习4】

1.两数之和

在这里插入图片描述

暴力：

class Solution {
public:
     vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        vector<int> res(2, -1); // 初始化结果为-1
        for (int i = 0; i < n; i++) {
            int temp = nums[i];
            for (int j = i + 1; j < n; j++) {
                if (target == temp + nums[j]) {
                    res[0] = i ; // 索引加1以符合一般的约定
                    res[1] = j ;
                    return res; // 找到结果后立即返回
                }
            }
        }
        // 如果找不到结果，返回空向量
        return res;
    }
};

在这里插入图片描述

hash表：

class Solution {
public:
     vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> hashtable;
       vector<int> res(2,-1);
       for(int i=0;i<nums.size();i++){
         if(hashtable.count(target-nums[i])>0)//哈希表中存在元素与之和为目标值
           {
              res[0]=i;
              res[1]=hashtable[target-nums[i]]; 
              break;
           }
          else{
             hashtable[nums[i]]=i;//没有就把该元素存到哈希表中
          }
       }
       return res;
     }
};

在这里插入图片描述

2.字母异位词分组

在这里插入图片描述

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
       unordered_map<string,vector<string>> mp;//定义一个无序表
       for(string&str:strs){//定义了一个函数，类型为string，名称为strs
          string key=str; //记录排序后的字符串
          sort(key.begin(),key.end());//对字符串内部元素进行排序并把排序得到的结果赋给key
          mp[key].emplace_back(str); //将str添加到key所在行的最后
       }
      vector<vector<string>> ans;
      for(auto i=mp.begin();i!=mp.end();i++){
         ans.emplace_back(i->second);//eg：nat被排序为ant,存到mp里边形式是ant,tan,nat;把tan,nat以[tan,nat]形式加入到ans中
      }
       return ans;
    }
};

在这里插入图片描述

3.有效的字母异位词

在这里插入图片描述

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s == t) return false;
        if (s.size() != t.size()) {
            return false;
        }
        else {
            string temp1 = s;
            string temp2 = t;
            sort(temp1.begin(), temp1.end());
            sort(temp2.begin(), temp2.end());
            if (temp1 != temp2) {
                return false;
            }
            else {
                return true;
            }
        }
    }
};