哈希
1. 两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
1.1 解法1
依次取第i个数与第j个数相加，判断是否等于目标值，若相等则返回索引号i，j。两个for循环嵌套，时间复杂度O（n^2）。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target)
{
int num = size(nums);
int i,j;
for(i = 0 ; i < num ; i++)
{
for(j = i+1; j < num ; j++)
{
if((nums[i]+nums[j]) == target)
{
return vector({
i,j});
}
}
}
return {
};
}
};
1.1 解法2
索引数组每个元素，每次从哈希表中寻找target与该元素的差值。若不存在则将元素值作为key，索引号作为value放入哈希表中；若存在则返回当前元素的索引号i和找到的对应key的value。由于只需要遍历一次数组，时间复杂度为O（n）。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hashtable;
int num = nums.size();
for (int i = 0; i < num ; ++i) {
auto it = hashtable.find(target - nums[i]);
if (it != hashtable.end()) {
return {
it->second, i};
}
hashtable[nums[i]] = i;
}
return {
};
}
};
2. 字母异位词分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
2.1 解法1
采用排序法、哈希表。字母异位词排序后的字符串一定相等，可以将其作为key，value为存放key对应的所有字母异位词（每发现一个符合条件的新字母异位词，则在value中添加该元素），之后遍历哈希表即可得到分组。
//采用unordered_map
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> mp;
for (string& str: strs) {
string key = str;
sort(key.begin(), key.end());
mp[key].emplace_back(str);
}
vector<vector<string>> ans;
for (auto it = mp.begin(); it != mp.end(); ++it) {
ans.emplace_back(it->second);
}
return ans;
}
};
//or
//采用unordered_multimap
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_multimap<string, vector<string>> mp;
for (string& str: strs) {
string key = str;
sort(key.begin(), key.end());
//mp[key].emplace_back(str);
//vstr = {str};
auto it = mp.find(key);
if(it != mp.end())
{
it->second.push_back(str);
}
else
{
vector<string> v;
v.push_back(str);
mp.emplace(key, v);
}
}
vector<vector<string>> ans;
for (auto it = mp.begin(); it != mp.end(); ++it) {
ans.emplace_back(it->second);
}
return ans;
}
};
2.2 解法2
采用计数法、哈希表。记录每个词每个字母的出现频次在一个26大小的数组中，可以将数组作为key，value为存放key对应的所有字母异位词（每发现一个符合条件的新字母异位词，则在value中添加该元素），之后遍历哈希表即可得到分组。由于C++ 哈希表不知道如何计算26数组的哈希值，因此还需传入一个hash function（函数对象，lambda表达式）。
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
// 自定义对 array<int, 26> 类型的哈希函数
auto arrayHash = [fn = hash<int>{
}] (const array<int, 26>& arr) -> size_t {
return accumulate(arr.begin(), arr.end(), 0u, [&](size_t acc, int num) {
return (acc << 1) ^ fn(num);
});
};
unordered_map<array<int, 26>, vector<string>, decltype(arrayHash)> mp(0, arrayHash);
for (string& str: strs) {
array<int, 26> counts{
};
int length = str.length();
for (int i = 0; i < length; ++i) {
counts[str[i] - 'a'] ++;
}
mp[counts].emplace_back(str);
}
vector<vector<string>> ans;
for (auto it = mp.begin(); it != mp.end(); ++it) {
ans.emplace_back(it->second);
}
return ans;
}
};
3. 最长连续序列
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
3.1 解法
- 采用基于哈希表实现的容器unordered_set（对元素不继续排序，key需不同）存储所有整数，可以去除重复元素。
- 之后遍历容器中整数，依次查看当前整数是否为一个序列的开头整数，即判断x-1是否存在于容器中。如果存在，则跳过，并遍历下一个整数；如果不存在，则说明该元素是一个序列的首元素，则开始依次判断x+1，x+2…是否存在，同时记录序列最长长度。
- 容器unordered_map是基于哈希表实现，插入与判断key是否存在均为O(1)，外层遍历元素次数为n，每个整数被外层循环访问了一次；内部中对于单个无连续的整数访问一次（因为x+1不存在），对于存在连续的整数序列也仅对序列中每个整数从小到大遍历一次，所以外层循环内部总共也只访问了n次。总共2n次，所以时间复杂度O(n) 。
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> num_set;
for (const int& num : nums) {
num_set.insert(num);
}
int longestStreak = 0;
for (const int& num : num_set) {
if (!num_set.count(num - 1)) {
int currentNum = num;
int currentStreak = 1;
while (num_set.count(currentNum + 1)) {
currentNum += 1;
currentStreak += 1;
}
longestStreak = max(longestStreak, currentStreak);
}
}
return longestStreak;
}
};
小结
针对算法实现过程中需要插入、查找或判断元素是否存在的功能，可以考虑基于哈希表实现的容器unordered_map，unordered_set。unordered_map需要选择合适的数据分别作为key和vaule。unordered_set仅需要一个key即可，主要也是为了迅速判断key是否存在。
双指针
4. 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
4.1 解法1
遍历数组中每个元素，并记录前方已经出现了几个0元素，以便明确后续非0元素需要往前移几位。首先判断该元素是否为0，如果为0则0元素计数加一；如果不为0，则按照之前出现的0个数zeronum将当前非0元素前移zeronum位，并将该位置0（当遍历到第一个元素时，非0元素需进行移动；前面0个数为0时，非0元素也无序移动）。
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int zeronum = 0;
int i = 0;
for(auto& num:nums)
{
if(num == 0)
{
zeronum += 1;
}
else
{
if(i !=0 && zeronum != 0 )
{
nums[i-zeronum] = num;
num = 0;
}
}
i += 1;
}
}
};
4.2 解法2
使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部。只有当右指针所指元素非0，则需要将该元素放到已处理好的序列尾部（交换）。
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n = nums.size(), left = 0, right = 0;
while (right < n) {
if (nums[right]) {
swap(nums[left], nums[right]);
left++;
}
right++;
}
}
};
5. 盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器
5.1 解法一
采用双for循环，依次计算出两垂线之间的容水体积，并找出最大值。虽然通过比较当前最大容量与当前左垂线的最大容量潜力减少不必要的计算，但双for循环最坏情况依然需要n*n。
class Solution {
public:
int maxArea(vector<int>& height) {
int max_capacity = 0;
int n = height.size();
int tmp;
for(int i = 0; i < n-1 ; i++)
{
if(max_capacity > height[i]*(n-i-1)) continue;
for(int j = i+1; j < n ; j++)
{
tmp = min(height[i],height[j]) * ( j - i );
if( tmp > max_capacity )
{
max_capacity = tmp;
}
}
}
return max_capacity;
}
};
5.2 解法二
采用双指针分别指向数组两端，每次让短板一端的指针往中间收拢一格，依次计算两指针所指垂线间的容水体积并保留最大值，总共只用遍历一次数组。该方法关键在于，向内移动短板，容水体积可能增大也可能减小；向内移动长板，容水体积必然减小（因为容水体积主要由短板决定，向内移动长板后，短板可能不变或者变得更短，同时两板距离必然缩短，所以容水体积必然缩短）。
class Solution {
public:
int maxArea(vector<int>& height) {
int i = 0, j = height.size() - 1, res = 0;
while(i < j) {
res = height[i] < height[j] ?
max(res, (j - i) * height[i++]):
max(res, (j - i) * height[j--]);
}
return res;
}
};
6. 三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
6.1 解法1
直接用三层for循环，每次取其中一个元素求和再判断。由于可能存在多个相同的三元组，因此还需要去重。时间复杂度O（n^3）.
6.2 解法2
采用排序+双指针。为了便于实现取得不重复的三元组，对数组先进行排序，从而保证后续三元组（a,b,c）中a <= b <= c ，就不会出现（c,a,b）、（b,c,a）…重复三元组。其次排序后可以利用有序的特性，结合双指针减少计算次数。(当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法，将枚举的时间复杂度从O(n^2)减少至 O(n)。使用双指针有一个必要的步骤就是左右指针碰面时即停止，使得n个元素只被遍历n次)。固定第一个参数a，左指针元素为b，右指针元素为c（一开始指向尾端），a+b+c>0，则右移，重复至a+b+c<=0，此时右指针不用回退，由于左指针下一个遍历元素一定大于等于前一个遍历的元素，所以a+b+c必然比之前大，此时右指针要么不动，要么往左移动（三者之和大于0），直至左指针右指针碰面，结束第二层for循环。此外，还需注意若前一个b和后一个b相等，则无需重复遍历记录三元组。总时间复杂度为O(n^2)。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
// 枚举 a
for (int first = 0; first < n; ++first) {
// 需要和上一次枚举的数不相同
if (first > 0 && nums[first] == nums[first - 1]) {
continue;
}
// c 对应的指针初始指向数组的最右端
int third = n - 1;
int target = -nums[first];
// 枚举 b
for (int second = first + 1; second < n; ++second) {
// 需要和上一次枚举的数不相同
if (second > first + 1 && nums[second] == nums[second - 1]) {
continue;
}
// 需要保证 b 的指针在 c 的指针的左侧
while (second < third && nums[second] + nums[third] > target) {
--third;
}
// 如果指针重合，随着 b 后续的增加
// 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
if (second == third) {
break;
}
if (nums[second] + nums[third] == target) {
ans.push_back({
nums[first], nums[second], nums[third]});
}
}
}
return ans;
}
};
7. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
7.1 解法1
class Solution {
public:
int trap(vector<int>& height) {
int i=0,j=1,k=0;
int h_size = height.size();
int tmp = 0;
int capacity = 0;
while(j < h_size)
{
if(height[i] == 0)
{
i++;
j++;
}
if( ((j-i) == 1) || (height[j] < height[i]) )
{
if( height[j] >= height[i] )
{
i = j;
tmp = 0;
}
else
{
tmp += height[j];
}
j++;
}
else
{
capacity = height[i]*(j-i-1)-tmp +capacity;
tmp = 0;
i = j;
j++;
}
}
if(tmp != 0)
{
tmp = 0;
k = j-1;
j = j-2;
// i = i-1;
while(k != i)
{
if(height[k] == 0)
{
k--;
j--;
}
if( ((k-j) == 1) || (height[j] < height[k]) )
{
if( height[j] >= height[k] )
{
k = j;
tmp = 0;
}
else
{
tmp += height[j];
}
j--;
}
else
{
capacity = height[k]*(k-j-1)-tmp +capacity;
tmp = 0;
k = j;
j--;
}
}
}
return capacity;
}
};
小结
双指针主要用于需要遍历两次时，左右指针分别指向头尾，两者依次往中间靠拢，可以找到某一规律（例如计算规律）使得两个指针不用回溯，直至两者碰面结束。将遍历两次的复杂度O(n^2)降至O(n)。
滑动窗口
8. 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。
8.1 解法1
采用哈希表记录已出现且不重复的字符，key为每个字符，value为每个不同字符当前最大的索引号（方便移动指针到刚好除去旧的重复字符的位置）。采用双指针，一个指向当前搜索子串的前一个位置，一个指向当前搜索子串字符的最后一个字符位置（一直从头找到尾）。当有重复字符出现，下一个搜索的子串开头则是该重复字符上次出现的位置的后一个位置。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> dic;
int i = -1, res = 0, len = s.size();
for(int j = 0; j < len; j++) {
if (dic.find(s[j]) != dic.end())
i = max(i, dic.find(s[j])->second); // 更新左指针
dic[s[j]] = j; // 哈希表记录，保证当有重复字符出现时，i能直接指到重复字符上次出现的位置
res = max(res, j - i); // 更新结果
}
return res;
}
};
9. 找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1:
输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。
示例 2:
输入: s = “abab”, p = “ab”
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。
9.1 解法一
时间超出限制。
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
unordered_map<char,int> mp;
vector<int> result;
int i = 0, psize = p.size();
int ssize = s.size();
if(psize > ssize) return result;
//将p中的字符存储至哈希表中,key为单个字符，value为该字符出现的次数
while(i < psize )
{
if(mp.find(p[i]) == mp.end())
mp[p[i]] = 1;
else
mp[p[i]] += 1;
i++;
}
unordered_map<char,int> tmpmp;
for(int j = 0; j < ssize - psize + 1; j++)
{
tmpmp = mp;
for(i = 0; i < psize; i++)
{
if(tmpmp.find(s[j+i]) != tmpmp.end())
{
if(tmpmp[s[j+i]] == 0)
{
break;
}
else
{
tmpmp[s[j+i]] -= 1;
}
}
else
{
j = j + i;
break;
}
}
if(i == psize)
{
result.push_back(j);
}
}
return result;
}
};
9.2 解法二
- 用一个数组记录p字符串中26个字母出现频次（记录每个字符还需要几个，为0则表示刚好满足条件且不需要，负数则表示已经出现的太多了），采用左右指针分别指向搜索s字符串的当前子串的头和尾，整数count记录剩余所需继续匹配字符个数。
- 左右指针均先指向s的首个字符，右指针依次往右移动，同时对应的字符在数组中的频次减1（仍待匹配的字符频次为正数，无需匹配的字符频次为非正数），每次检查右指针所指字符是否在p串中（即p中对应的字符频次大于0），若在则说明找到匹配的字符，则count–。
- 当count为0时，则说明当前字串已经完全匹配p，返回子串首位置。
- 当已经核验过的字符数量与p串的字符数量相等时，搜索窗口已经到达最大，因此需要收缩一下窗口，则左指针需要往右移，丢掉前面的一个字符，对应的也需增加被丢掉字符的频次。如果被丢掉字符所需要匹配的频次大于等于0（只有是p串中出现的字符，频次才会有可能大于等于0（可能为负数则表明该字符本应该只需要n次，子串中却已经有n+1个，则直接丢掉即可），未出现在p串中的字符一定是负数（因为前面会对索引过的字符频次进行减一，0-1=-1）），则count需要加1。由于对每个被右指针索引过的字符频次均会被减1，因此丢掉该字符时，频次均需要加1。
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int sLen = s.length(), pLen = p.length();
vector<int> result;
if (sLen < pLen) {
return result; // 如果输入为空或者s的长度小于p的长度，则直接返回空结果
}
int pFreq[26] = {
0}; // 数组记录字符出现频率，长度为26表示小写字母的26个字符
// 记录p中每个字符的出现次数
for (char c : p) {
pFreq[c - 'a']++; // 将字符映射到数组的索引，增加出现次数
}
int left = 0, right = 0, count = pLen; // 初始化左右指针和计数器
while (right < sLen) {
// 步骤一
if (pFreq[s[right] - 'a'] > 0) {
count--; // 如果当前字符在p中存在，则减少count计数
}
pFreq[s[right] - 'a']--; // 更新频率数组，出现过的字符频率值-1
right++; // 右指针向右移动
// 步骤二
if (count == 0) {
result.push_back(left); // 如果找到一个异位词，记录起始索引
}
// 步骤三
if (right - left == pLen) {
// 当窗口大小等于p的长度时
if (pFreq[s[left] - 'a'] >= 0) {
count++; // 如果左边界对应字符在p中，则增加count计数
}
pFreq[s[left] - 'a']++; // 恢复频率值
left++; // 左指针向右移动
}
}
return result; // 返回结果
}
};
子串
10 和为k的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
解法1
暴力求解法，采用双for循环，遍历每一个子数组，看是否满足条件和为k。时间复杂度为O（n^2）。
解法2
序号[0…j…i…n]的数组，当[j…i]子数组之和等于k时，可以看作（前i个数之和）-（前j-1个数之和）。因此，通过这一点可以实现仅用i遍历一遍数组即可求得所有满足条件的子数组个数。
- 每次将前i个元素的和pre[i]作为哈希表的key，value用来记录第i个元素之前有几个子数组【0…j-1】的和等于key。
- 每当遍历到第i个元素时，则会寻找第i个元素前面有哪些【0…j-1】子数组（j < i）的和满足pre[i] - k == pre[j-1]，找到的话即表示存在【j…i】的子数组之和等于k。
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> mp;
mp[0] = 1;
int count = 0, pre = 0;
for (auto& x:nums) {
pre += x;
if (mp.find(pre - k) != mp.end()) {
count += mp[pre - k];
}
mp[pre]++;//可能有不同的【0...j-1】子数组和相同
}
return count;
}
};
11. 滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
解法一
不妥，虽然速度快
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int i = 0,j = k-1,p,maxorder;
int max = -2147483647;
int flag = 0;
int flag2 = 0;
int numsize = nums.size();
vector<int> result;
while(j < numsize)
{
p = i;
max = -2147483647;
if(flag == 1) flag2 = 1;//若上次得到窗口内是单调递减的序列，则表示可以开始利用前一次的全是单调递减特性进行优化
if(i == 0 || maxorder < i)//若目前为第一个窗口或上次最大值已不在窗口内
{
if(flag == 1)//若上次得到窗口内是单调递减的序列
{
if(nums[j] <= nums[j-1])
{
max = nums[i];
maxorder = i;
}
else
{
flag = 0;
}
}
if(flag2 == 1 && i < k)//若之前有过窗口内是单调递减的序列的情况
{
if(nums[i] >= nums[j])//则直接拿新加入窗口的值，与当前窗口的第一个值比较
{
result.push_back(nums[i]);
i++;
j++;
continue;
}
}
if(flag == 0)
{
while(p <= j)//遍历窗口里所有元素，获取最大值，同时记录单调性
{
if(nums[p] > max )
{
max = nums[p];
maxorder = p;
}
if(i == p )
flag = 1;
else if(nums[p-1] >= nums[p] && flag != 0 )
flag = 1; //单调递减
else
flag = 0;
p++;
}
}
}
else//若前一个窗口的最大值仍在当前窗口内，则只需拿出前一个窗口的最大值与新加入窗口的值进行比较
{
max = result.back() > nums[j] ? result.back():nums[j];
if(result.back() > nums[j])
{
max = result.back();
}
else
{
max = nums[j];
maxorder = j;
}
}
result.push_back(max);
i++;
j++;
}
return result;
}
};
解法二
采用单调队列。
- 假设第i个元素在第j个元素的前面（【0…i…j…n】），并且第i个元素不大于第j个元素（nums[j] >= nums[i]）。当滑动窗口向右移动时，只要第i个元素还在窗口中，那么第j个元素一定也还在窗口中。因此，由于 nums[j]的存在，nums[i]一定不会是滑动窗口中的最大值了，我们可以将 nums[i]永久地移除。
- 可以用一个队列存储这些不被永久移出的元素下标，每次将一个新元素入队时严格循环检查该新元素是不是比队列的最后一个元素要大，如果是的，则可以永久地移出目前处于队尾的元素，在进行反复判断，至队列为空或有比新元素更大的元素在队尾；如果不是，直接将新元素插入队尾。这个队列将严格保证元素序列时单调递减的，因此队首元素是整个队列的最大值。
- 窗口右移过程中，当队列的队首元素已经离开窗口后，则需要及时将该队首元素弹出。
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
deque<int> q;
for (int i = 0; i < k; ++i) {
while (!q.empty() && nums[i] >= nums[q.back()]) {
q.pop_back();
}
q.push_back(i);
}
vector<int> ans = {
nums[q.front()]};
for (int i = k; i < n; ++i) {
while (!q.empty() && nums[i] >= nums[q.back()]) {
q.pop_back();
}
q.push_back(i);
while (q.front() <= i - k) {
q.pop_front();
}
ans.push_back(nums[q.front()]);
}
return ans;
}
};
12. 最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
解法1
哈希表+双指针。
- 首先用哈希表存储t串中的字符以及出现的次数；
- 用双指针i，j，指向当前子串的首尾。j 依次向右移动，至 i 到 j 的子串中出现了 t 串的所有字符且频次更大于或等于，则 i 就往右移，开始收缩子串；
- 至子串中字符出现频次小于 t 串中的，则 j 继续右移，循环往复，记录满足条件的最短子串。
class Solution {
public:
unordered_map<char,int> mp,tmpmp;
bool check()
{
for (const auto &p: mp) {
if (tmpmp[p.first] < p.second) {
return false;
}
}
return true;
}
string minWindow(string s, string t) {
int tsize = t.size();
int ssize = s.size();
int i = 0,j = 0;
int si=-1,sj=-1;
int minlenth = 10000000;
for(i = 0;i < tsize; i++)
{
mp[t[i]] = mp.find(t[i]) == mp.end()? 1: mp[t[i]] + 1 ;
}
i = j = 0;
while(j < ssize)
{
if(tmpmp.find(s[j]) != tmpmp.end())
{
tmpmp[s[j]]++;
}
else
{
if(mp.find(s[j]) != mp.end())
tmpmp[s[j]] = 1;
}
while(check())
{
if(minlenth > j-i+1 )
{
si = i;
sj = j;
minlenth = j-i+1;
}
if(tmpmp.find(s[i]) != tmpmp.end())
{
tmpmp[s[i]]--;
}
i++;
}
j++;
}
if(si == -1) return string("");
return s.substr(si, sj-si+1);
}
};
数组
13 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
解法1
动态规划法:
- 每次计算以第 i 个元素结尾的最大子数组和。
- 如果第 i - 1 个元素结尾的最大子数组和为负数，则说明第 i 个元素加上前面最大子数组的总和肯定更小，因此直接放弃前面的所有子数组，以第 i 个元素当作以第 i 个元素结尾的最大子数组和（自立门户）；
- 如果第 i - 1 个元素结尾的最大子数组和为正数，则说明第 i 个元素加上前面最大子数组的总和肯定更大，可以组成以第 i 个元素结尾最大的子数组和。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int pre = 0, maxAns = nums[0];
for (const auto &x: nums) {
pre = max(pre + x, x);
maxAns = max(maxAns, pre);
}
return maxAns;
}
};
14. 合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
解法1
- 首先按照每个区间的第一个元素进行排序；
- 之后遍历每个区间，每次检查当前第 i 个 区间[a,b]的右侧是否大于等于下一个（第 i + 1个）区间[c,d]的左侧。如果是则表示可以融合为更大的区间[a,d]；如果不是则表明两者不可融合，后面要重新开启一个新的区间。
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
vector<vector<int>> ans;
for (int i = 0; i < intervals.size();) {
int t = intervals[i][1];
int j = i + 1;
while (j < intervals.size() && intervals[j][0] <= t) {
t = max(t, intervals[j][1]);
j++;
}
ans.push_back({
intervals[i][0], t });
i = j;
}
return ans;
}
};
15. 轮转数组
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
解法1
利用vector特性，先插入数组后k个元素到数组的首段，之后再删除数组后k个元素。
class Solution {
public:
void rotate(vector<int>& nums, int k) {
if(nums.size() == 1 || nums.size() == k) return;
k = k % nums.size();
nums.insert(nums.begin(),nums.end()-k,nums.end());
nums.erase(nums.end()-k,nums.end());
}
};
解法2
数组多次反转：
class Solution {
public:
void reverse(vector<int>& nums, int start, int end) {
while (start < end) {
swap(nums[start], nums[end]);
start += 1;
end -= 1;
}
}
void rotate(vector<int>& nums, int k) {
k %= nums.size();
reverse(nums, 0, nums.size() - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.size() - 1);
}
};
15. 除自身以外数组的乘积
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
解法1
所有的结果如下图所示。根据规律，可采用两次循环，分别遍历数组计算下三角的累乘和上三角的累乘。
- 第一次for循环计算下三角的累乘并存储下来到B数组中。
- 第二次for循环可以从n至1遍历，计算下三角每层的累乘，顺便直接与B数组中对应层相乘，直接计算出该层的最终结果值。
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int len = nums.size();
if (len == 0) return {
};
vector<int> ans(len, 1);
ans[0] = 1;
int tmp = 1;
for (int i = 1; i < len; i++) {
ans[i] = ans[i - 1] * nums[i - 1];
}
for (int i = len - 2; i >= 0; i--) {
tmp *= nums[i + 1];
ans[i] *= tmp;
}
return ans;
}
};
