389.找不同
给定两个字符串 s 和 t ，它们只包含小写字母。
字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
请找出在 t 中被添加的字母。
示例：
输入： s = "abcd", t = "abcde"
输出： "e"
解释： 'e' 是那个被添加的字母。
方法一：差值法
时间复杂度O(N) 空间复杂度O(1)
class Solution {
public:char findTheDifference(string s, string t) {int result1 = 0;int result2 = 0;for(int i = 0; i < s.length(); i++){result1 += s[i];}for(int j = 0; j < t.length(); j++){result2 += t[j];}//计算s t 各个字符串的总ASCII码值return (char)result2 - result1;//返回差值转换为字符即为后添加的字符}
};
方法二：记数法
时间复杂度O(N) 空间复杂度O(1)
class Solution {
public:char findTheDifference(string s, string t) {vector<int>count(26,0);//创建一个26个整数的数组对应26个英文字母for(int i = 0; i < s.length(); i++){char ch = s[i];// 获取s中第i个字符count[ch - 'a']++;// 对应字母计数+1//因为s 和 t 只包含小写字母，用ch字符减去a获取26个英文字母对应的1~26数字}for(int j = 0; j < t.length(); j++){char ch = t[j];// 获取t中第i个字符count[ch - 'a']--;// 对应字母计数-1if(count[ch - 'a'] < 0) {// 发现多出来的字母，立即返回return ch;}}return ' ';}
};
方法三：异或法
时间复杂度O(N) 空间复杂度O(1)
class Solution {
public:char findTheDifference(string s, string t) {// 初始化结果变量为0int res = 0;// 遍历字符串s中的每个字符for(int i = 0; i < s.size(); i++){// 将当前字符与结果进行异或操作res = res ^ s[i];}// 遍历字符串t中的每个字符for(int j = 0; j < t.size(); j++){// 将当前字符与结果进行异或操作res =res ^ t[j];}// 最终结果res就是多出来的字符return res;}
};