408算法题leetcode--第10天

643. 子数组最大平均数 I

• 643. 子数组最大平均数 I
• 思路：滑动窗口
• 时间：O(n)；空间：O(1)

class Solution {
public:double findMaxAverage(vector<int>& nums, int k) {double ret = 0, temp = 0;size_t size = nums.size();for(int i = 0; i < k; i++){temp += nums[i];}ret = temp;// 进，出for(size_t i = k; i < size; i++){temp = temp + nums[i] - nums[i - k];ret = max(temp, ret);}return ret / k;}
};

567. 字符串的排列

• 567. 字符串的排列
• 思路：滑动窗口
• 时间：O(s2_size)；空间：O(1)，因为都是小写字母

class Solution {
public:bool checkInclusion(string s1, string s2) {// 滑动窗口：大小为s1.size()// 相等：两个字符串的字符种类和次数都相同int s1_size = s1.size(), s2_size = s2.size();if(s1_size > s2_size){return false;}vector<int>hash_s1(26), hash_s2(26);for(int i = 0; i < s1_size; i++){hash_s1[s1[i] - 'a']++;hash_s2[s2[i] - 'a']++;}if(hash_s1 == hash_s2){  // O(1)return true;}// 滑动for(int i = s1_size; i < s2_size; i++){hash_s2[s2[i] - 'a']++;hash_s2[s2[i - s1_size] - 'a']--;if(hash_s1 == hash_s2){return true;}}return false;}
};