文章目录
- 209. 长度最小的子数组(中等)
- 题目链接
- 算法原理
- 代码实现
- 3. 无重复字符的最长子串(中等)
- 题目链接
- 算法原理
- 代码实现
- 1004. 最大连续1的个数 III(中等)
- 题目链接
- 算法原理
- 代码实现
- 1658. 将 x 减到 0 的最小操作数(中等)
- 题目链接
- 算法原理
- 代码实现
- 904. 水果成篮(中等)
- 题目链接
- 算法原理
- 代码实现
- 438. 找到字符串中所有字母异位词(中等)
- 题目链接
- 算法原理
- 代码实现
- 30. 串联所有单词的子串(困难)
- 题目链接
- 算法原理
- 代码实现
- 76. 最小覆盖子串(困难)
- 题目链接
- 算法原理
- 代码实现
209. 长度最小的子数组(中等)
题目链接
209. 长度最小的子数组
算法原理
暴力枚举:
这里可以枚举出所有子数组的和,然后从中选出符合条件的,最后再选出长度最小的那组,这样的时间复杂度为O(N2)
滑动窗口:
代码实现
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums){int sz = nums.size();int ret = INT_MAX;int sum = 0;for(int left=0,right=0;right<sz;right++){sum+=nums[right];while(sum>=target){ret = min(ret,right-left+1);sum-=nums[left++];}}return ret==INT_MAX?0:ret;}
};
3. 无重复字符的最长子串(中等)
题目链接
3. 无重复字符的最长子串
算法原理
暴力枚举+哈希表:
每个位置都进行从前往后枚举,然后用哈希表统计是否出现了重复元素
滑动窗口:
在暴力枚举的思想上做出优化
代码实现
class Solution {
public:int lengthOfLongestSubstring(string s){int left = 0;int right = 0;int hash[128] = { 0 };int ret = INT_MIN;while(right<s.size()){//进窗口hash[s[right]]++;//值有重复,出窗口while(hash[s[right]]>1){hash[s[left++]]--;}ret = max(ret,right-left+1);right++;}return ret==INT_MIN?0:ret;}
};
1004. 最大连续1的个数 III(中等)
题目链接
1004. 最大连续1的个数 III
算法原理
暴力枚举+0计数器
连续的1
,再加上k
个0
滑动窗口:
代码实现
class Solution {
public:int longestOnes(vector<int>& nums, int k){int left = 0;int right = 0;int zeroCount = 0;int ret = INT_MIN;while(right<nums.size()){if(nums[right] == 0)zeroCount++;while(zeroCount>k){if(nums[left] == 0)zeroCount--;left++;}ret = max(ret,right-left+1);right++;}return ret;}
};
1658. 将 x 减到 0 的最小操作数(中等)
题目链接
1658. 将 x 减到 0 的最小操作数
算法原理
思路转换:
找出最长的子数组长度,让这个子数组中元素的和正好等于sum-x
(sum为整个数组的和),然后采用滑动窗口思想
代码实现
class Solution {
public:int minOperations(vector<int>& nums, int x){int left = 0;int right = 0;int len = INT_MIN;int arrSum=0;for(auto e:nums){arrSum+=e;}int sum = 0;int target = arrSum-x;//target<0的话,滑动窗口就不适用if(target < 0)return -1;while(right<nums.size()){sum+=nums[right];while(sum>target){sum-=nums[left];left++;}if(sum == target)len = max(len,right-left+1);right++;}return len==INT_MIN?-1:nums.size()-len;}
};
904. 水果成篮(中等)
题目链接
904. 水果成篮
算法原理
这里原始思路也是暴力枚举+哈希表,再原思路上作出优化,采用滑动窗口思想
代码实现
使用库里面的哈希表:
class Solution {
public:int totalFruit(vector<int>& fruits){unordered_map<int,int> mp;int ret = INT_MIN;int left = 0;int right = 0;while(right<fruits.size()){mp[fruits[right]]++;while(mp.size() > 2){mp[fruits[left]]--;if(mp[fruits[left]] == 0)mp.erase(fruits[left]);left++;}ret = max(ret,right-left+1);right++;}return ret==INT_MIN?0:ret;}
};
这里提交会发现,时间还是较长的,虽然量级是在O(N),但因为这里涉及到哈希表的多次插入和删除,所以还是费些时间;
然后这里发现,题目给的数据范围有限:
1 <= fruits.length <= 105
,所以我们可以模拟哈希表的操作,自己造一个建议的哈希表
简易哈希表:
class Solution {
public:int totalFruit(vector<int>& fruits){//unordered_map<int,int> mp;int hash[100001] = { 0 };int ret = INT_MIN;int left = 0;int right = 0;int kinds = 0;while(right<fruits.size()){if(hash[fruits[right]] == 0)kinds++;hash[fruits[right]]++;while(kinds > 2){hash[fruits[left]]--;if(hash[fruits[left]] == 0)kinds--;left++;}ret = max(ret,right-left+1);right++;}return ret==INT_MIN?0:ret;}
};
对比:
438. 找到字符串中所有字母异位词(中等)
题目链接
438. 找到字符串中所有字母异位词
算法原理
滑动窗口+哈希表:
将字符丢入哈希表,然后当窗口大小等于p
的大小的时候,开始判断这个哈希表是否相同
代码实现
class Solution
{
public:bool checkHash(int h1[], int h2[]){for (int i = 0, j = 0; i < 26; i++,j++){if (h1[i] != h2[j])return false;}return true;}vector<int> findAnagrams(string s, string p){int left = 0;int right = 0;vector<int> ret;int hash1[26] = { 0 };int hash2[26] = { 0 };for (auto e : p){hash1[e - 97]++;}while (right < s.size()){hash2[s[right] - 97]++;if (right - left + 1 == p.size()){if (checkHash(hash1, hash2))ret.push_back(left);hash2[s[left++] - 97]--;right++;continue;}right++;}return ret;}
};
这里每次都要比较哈希表,复杂度其实是O(26*N),我们可以将比较方法改变一下
优化:
不对比哈希表,用count
记录窗口有效字符的个数
class Solution
{
public:vector<int> findAnagrams(string s, string p){int left = 0;int right = 0;vector<int> ret;int hash1[26] = { 0 };int hash2[26] = { 0 };for (auto e : p){hash1[e - 97]++;}int count = 0;while (right < s.size()){hash2[s[right] - 97]++;if(hash2[s[right]-97] <= hash1[s[right]-97])count++;if(right-left+1>p.size()){if(hash2[s[left]-97]<=hash1[s[left]-97]){count--;}hash2[s[left++]-97]--;}if(count == p.size())ret.push_back(left);right++;}return ret;}
};
对比
30. 串联所有单词的子串(困难)
题目链接
30. 串联所有单词的子串
算法原理
采用438. 找到字符串中所有字母异位词
的思路,将这些字符串看作字符
代码实现
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words)
{vector<int> ret;unordered_map<string, int> hash1;for (auto e : words){hash1[e]++;}int sz = s.size();int len = words[0].size();int m = words.size();for(int i =0;i<len;i++){ int count = 0;unordered_map<string, int> hash2;for (int left = i, right = i; right < sz;){string tmp = s.substr(right, len);hash2[tmp]++;//如果表1里面没有这个元素,就直接不比较了,避免又再临时去哈希表里面创建一个if (hash1.count(tmp) && hash2[tmp] <= hash1[tmp])count++;if (right - left + 1 > m*len){string out = s.substr(left, len);if (hash1.count(out) && hash2[out] <= hash1[out])count--;hash2[out]--;left += len;}if (count == m)ret.push_back(left);right += len;}}return ret;
}
};
76. 最小覆盖子串(困难)
题目链接
76. 最小覆盖子串
算法原理
哈希表+滑动窗口:
2个哈希表:一个放t
的元素,然后统计有多少种元素;另一个用滑动窗口来放入元素,当这个哈希表中包含目标字符串,并且对应个数不小于目标串哈希表中各字符的个数时,那就可以更新这个窗口的大小
代码实现
class Solution
{
public:string minWindow(string s, string t){int hash1[128] = { 0 };int kinds = 0; //字符种类for(auto e:t){if(hash1[e] == 0)kinds++;hash1[e]++;}int count = 0;int len = INT_MAX;int begin = -1;int hash2[128] = { 0 };for(int left=0,right=0;right<s.size();right++){int in = s[right];if(++hash2[in] == hash1[in])count++;while(count == kinds){if(right-left+1<len){len = right-left+1;begin = left;}int out = s[left++];if(hash2[out]-- == hash1[out])count--;}}return len==INT_MAX?"":s.substr(begin,len);}
};