为了这个二维数组浪费了起码二十分钟！！！
子串与子序列傻傻分不清，子串是连续的，子序列是不连续的，重要事情必须记住，我就不三遍了。用子序列去做子串的题，起码也浪费了二十分钟。
unordered_map，不知道查看一个key有没有在字典中，查了至少5分钟！！！ 定义模板迭代器： unordered_map<int,int>::iterator it; map.find()函数查看是否有该键：if ( map1.find(arr[i]) == map1.end()) 可以看出：若有该键返回该迭代器，没有该键返回map.end() map的遍历：it迭代器访问key, value: it->first it->second 滑动窗口法目前还不熟练，需要强化练习！！！ 第一次通过：二维dp数组做的 class Solution { public: int equalSubstring(string s, string t, int maxCost) { int max_len = 0; vector<int> nums(t.size(), 0); // 一维数组 vector<vector<int>> dp(t.size(), vector<int>(2, 0)); // 二维vector数组及初始化 for (int i=0; i<s.size(); ++i){ nums[i] = abs(s[i] - t[i]); } // dp数组初始化 dp的初始化很重要，要细心！！！ if (nums[0] <= maxCost){ dp[0][0] = nums[0]; dp[0][1] = 1; max_len = 1; } for (int i=1; i<s.size(); ++i){ if (dp[i-1][0]+nums[i] <= maxCost){ dp[i][0] = dp[i-1][0] + nums[i]; dp[i][1] = dp[i-1][1] + 1; } else{ int tmp = dp[i-1][0], j; for (j=i-dp[i-1][1]; j<=i; ++j){ tmp -= nums[j]; if (tmp+nums[i] <= maxCost) break; } dp[i][0] = tmp+nums[i]; dp[i][1] = i - j; } max_len = max(max_len, dp[i][1]); } return max_len; } };因为子串都是连续的，所以容易想到使用滑动窗口法来做，而且元素都>=0，滑动窗口不会往回返！！！
class Solution { public: int equalSubstring(string s, string t, int maxCost) { int max_len = 0; vector<int> nums(s.size(), 0); for (int i=0; i<s.size(); ++i) nums[i] = abs(s[i] - t[i]); int start = 0, end = 0, sum_tmp = 0; for (; end<s.size(); ++end){ sum_tmp += nums[end]; if (sum_tmp <= maxCost) continue; else{ max_len = max(max_len, end-start); while (sum_tmp > maxCost){ sum_tmp -= nums[start]; ++start; } } } return max(max_len, end-start); } };使用滑动窗口法显然更好，
思路清晰、代码简洁、时间空间复杂度有显著降低，简直完美！！！。
转载于:https://www.cnblogs.com/ACStrive/p/11610537.html
