1. 长度最小的子数组

题目思路:

首先暴力解法就是依次枚举出所有的子数组, 从第一个元素为左端点依次向后枚举, 枚举到长度大于target就停止枚举, 以第二个元素为左端点进行枚举, 这里我们可以进行优化.

滑动窗口解法, 定义两个下标, left先从第一个元素位置开始, right找右端点, 如果找到了此时right也不需再回到第二个元素开始, 和left一起向后走, 因为我们已经计算出right- left这段区间的和了, 只需要减去第一个元素即可枚举下一个数组, 并且right前一个元素与前面元素之和我们已经知道一定是小于target的, 所以直接left++即可, 这种场景就像在维持一个滑动窗口一样, 同向双指针, 按照以下步骤我们进行编写代码.

编写代码:

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int sum = 0, ret = INT_MAX;for(int left = 0,right = 0; right<nums.size();right++){sum += nums[right];while(sum >= target){ret = min(ret,(right - left +1));sum -= nums[left++];}}return ret == INT_MAX ? 0 : ret;}
};

2. 无重复字符的最长子串

题目思路:

首先看到求子串子数组, 我们首先可以想到滑动窗口, 但是怎么判断不重复呢, 我们可以利用哈希, 但是没必要使用容器, 因为字符范围我们已经知道了, 所以自己创建一个, 进窗口, 就是把每个字符扔到哈希表里, 判断条件就是是否重复, 如果重复, 那就出窗口进行下一次判断, 最后判断结束之后更新结果.

编写代码:

class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128] = {0},ret = 0;for(int left = 0, right = 0; right < s.size(); right++){hash[s[right]]++;while(hash[s[right]] == 2){hash[s[left]]--;left++;}ret = max(ret, (right - left +1));}return ret;}
};

3. 最大连续1的格数Ⅲ

题目思路:

寻找最大连续1的个数, 进窗口, 如果是1, 无视, 如果是0 ,则计数器加1, 当计数器大于k时, 开始判断然后出窗口, 最后更新结果.

编写代码:

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int ret = 0, zero = 0;for(int left = 0, right = 0; right < nums.size(); right++){if(nums[right] == 0) zero++;while(zero > k){if(nums[left] == 0) zero--;left++;}ret = max(ret, (right - left +1));}return ret;}
};

4. 将x减到0的最小操作数

题目思路:

采用正难则反的思想, 转化为找出最长子数组的长度, 所有元素之和正好等于sum- x即可, 然后进行滑动窗口求解, 最后更新结果时需要判断.

编写代码:

class Solution {
public:int minOperations(vector<int>& nums, int x) {int sum = 0, ret = -1;for(const auto& e : nums) sum+=e;int target = sum - x;if(target < 0) return -1;int tmp = 0;for(int left = 0, right = 0; right  < nums.size(); right++){tmp += nums[right];while(tmp > target){tmp -= nums[left];left++;}if(target == tmp)ret = max(ret, (right - left + 1));}if(ret == -1) return ret;else return nums.size() - ret;}
};

5. 水果成篮

题目思路:

采用暴力解法会超时, 我们采用滑动窗口解法, 定义kinds表示篮子的个数, 每次采摘水果之后将水果扔到哈希表中, 判断条件为如果种类大于2则出窗口, 并且把水果出哈希表, 进行下一次判断. 最后更新结果.

编写代码:

class Solution {
public:int totalFruit(vector<int>& f) {int hash[100001] = {0}, count = 0, ret = 0;for(int left = 0, right = 0; right < f.size(); right++){if(hash[f[right]]++ == 0) count++;while(count > 2){if(--hash[f[left++]] == 0) count--;}ret = max(ret,(right - left +1));}return ret;}
};

6. 找到字符串中所有字母异位词

题目思路:

利用哈希表进行判断是否时异位词, 如果出现的次数都一样则为异位词, 利用变量count来记录有效字符的个数, 条件是, 进入哈希表之后判断 hash2[in] <= hash1[in] 是否成立, 如果成立则count++, 然后进行单次判断, 因为这里窗口大小一定是固定大小的, 所以判断长度是否合法,然后出窗口, 出窗口之前一样先更新count, 最后判断如果count等于p的长度则更新结果.

编写代码:

class Solution {
public:vector<int> findAnagrams(string s, string p) {int hash1[26] = {0}, hash2[26] = {0};vector<int> v;for(const auto& ch : p) hash1[ch - 'a']++;for(int left = 0,right = 0,count = 0; right < s.size(); right++){char in = s[right];if(++hash2[in - 'a'] <= hash1[in - 'a']) count++;if((right - left + 1) > p.size()){char out = s[left++];if(hash2[out - 'a']-- <= hash1[out - 'a']) count--;}if(count == p.size()) v.push_back(left);}return v;}
};

7. 串联所有单词的子串

题目思路:

这道题与上一道题的解法非常的类似, 只不过这里判断是字符串, 这里我们采用容器哈希表来求解, 移动的步长是单词的长度, 滑动窗口执行的次数为len.

编写代码:

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {unordered_map<string,int> hash1;vector<int> ret;for(const auto& s : words) hash1[s]++;size_t len = words[0].size();for(int i = 0; i< len ;i++){unordered_map<string,int> hash2;for(int left = i, right = i, count = 0; right + len <= s.size(); right+=len){string in = s.substr(right,len);if(hash1.count(in) && ++hash2[in] <= hash1[in]) count++;if((right - left + 1) > words.size() * len){string out = s.substr(left, len);if(hash1.count(out) && hash2[out]-- <= hash1[out]) count--;left+=len;}if(count == words.size()) ret.push_back(left);}}return ret;}
};

8. 最小覆盖子串

题目思路:

寻找最小覆盖的子串, 这里有可能子串中存在多个t中的字符, 所以我们需要统计种类, 也就是有效个数的种类, 只有当hash1[in] == hash2[in]时, 我们才算做一次有效字符.

编写代码:

class Solution {
public:string minWindow(string s, string t) {int hash1[128] = {0}; int kids = 0;for(const auto& ch : t)if(hash1[ch]++ == 0) kids++;int hash2[128] = {0};int begin = -1,len = INT_MAX;for(int left = 0, right = 0, count = 0; right < s.size(); right++){//进窗口+维护if(++hash2[s[right]] == hash1[s[right]]) count++;while(count == kids){if (right - left + 1 < len){begin = left;len = right - left + 1;}if(hash2[s[left]]-- == hash1[s[left]]) count--;hash2[s[left++]];}}if(begin == -1) return "";else return s.substr(begin,len);}
};

---

完