难度4

字符串中的变位词 原题链接：https://leetcode.cn/problems/MPnaiL/ 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。第一个字符串的排列之一是第二个字符串的 子串 。 1.静态滑动窗口1由于知道目标字符串的长度，故可以通过暴力枚举的方式（一个静态的滑动窗口）来枚举出所有的情况， 并对枚举的每种情况进行字母数量的统计，利用哈希表实现字母数量的统计， 123456789101112131415class Solution {public: bool checkInclusion(string pattern, string text) { for (int i = 0, j = i + pattern.length(); j <= text.length(); ++i, ++j) { int flag = 0; vector<int> cnt(26); for (int k = 0; k < pattern.length(); ++k) cnt[pattern[k] - 'a']++;//查找目标的字母数量统计 for (int k = i; k < j; ++k) cnt[text[k] - 'a']--;//遍历的字符串的字母数量统计 for (int i = 0; i < 26; ++i) if (cnt[i] != 0) flag = 1;//判断字母数量是否相同 if (flag) continue; return true; } return false; }}; 勉强能过，时间复杂度与空间复杂度都很高。 2.静态滑动窗口2对每次的字母数量判断操作进行修改，对边界值进行加入与减出操作，思路没有问题的，先做记录在此。 1234567891011121314151617181920212223class Solution {public ...

和大于等于target的最短子数组 原题链接：https://leetcode.cn/problems/2VG8Kg/ 给定一个含有 n 个正整数的数组和一个正整数 target ， 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。 如果不存在符合条件的子数组，返回 0 。 1.静态滑动窗口1遍历滑动窗口大小，每次for循环滑动窗口大小值固定，每次对滑动窗口中的内容进行求和，尝试更新答案，时间超时： 1234567891011121314151617181920class Solution {public: int minSubArrayLen(int target, vector<int>& nums) { int flag = 0; int ans = nums.size(); //遍历滑动窗口的大小 for (int len = 1; len <= nums.size(); ++len) { for (int i = 0, j = i + len; j <= nums.size(); ++i, ++j) { int sum = 0; for (int k = i; k < j; ++k) sum += nums[k]; if (sum >= target && len <= ans) { ans = len; flag = 1; } } } if (!flag) return 0; return ans; }}; 2.静态滑动窗口2遍历滑动窗口大小，每次for循环滑动窗口大小值固定， 维护一个sum值 进行加入与减出，每次窗口移动加入与减出 ...

乘积小于K的子数组 原题链接：https://leetcode.cn/problems/ZVAVXX/ 1.静态滑动窗口 维护一个mul乘积 对乘积进行 * / 操作 当是当滑动窗口的长度len 非常大时， 乘积mul可能会超出数据范围 如果多个 0 ~ 1000 范围的num[i]相乘 可能超出 int 数据范围 这种方法非常容易超出int的数据范围 认定为失败的方法 123456789101112131415161718class Solution {public: int numSubarrayProductLessThanK(vector<int>& nums, int k) { if (k == 0) return 0; int ans = 0; //遍历滑动窗口的长度 for (int len = 1; len <= nums.size(); ++len) { int mul = 1; int flag = 1; for (int i = 0; i < len; ++i) mul *= nums[i]; if (mul < k) ans++; for (int i = 1; i + len <= nums.size(); ++i) { mul /= nums[i - 1]; mul *= nums[i + len - 1]; if (mul < k) ans++; } } return ans; }}; 2.动态滑动窗口 从前往后处理所有的nums[i]，使用变量i、j代表窗口的左右端点（静态窗口弊端完美解决），使用变量mul记录当前窗口的乘积， 当 mul>=k 时，我们考虑将左端点i右移，同时消除左端点元素 nums[i] 对 mul 的贡献，直到mul>=k不再满足 这样就可以得到每个右端点 nums[i] 的最远左端 ...

单词长度的最大乘积 原题链接：https://leetcode.cn/problems/aseY1I/ 给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。 1.暴力法暴力法虽然测试用例能正确输出，但是程序时间复杂度太高直接超时， 1234567891011121314151617181920212223242526class Solution {public: bool have_same_char(string str1, string str2) { for (char c = 'a'; c <= 'z'; ++c) { int flag1 = 0; int flag2 = 0; for (int i = 0; i < str1.size(); ++i) if (str1[i] == c) {flag1 = 1; break;} for (int i = 0; i < str2.size(); ++i) if (str2[i] == c) {flag2 = 1; break;} if (flag1 && flag2) return true; } return false; } int maxProduct(vector<string>& words) { int max = 0; for (int i = 0; i < words.size(); ++i) { for (int j = i; j < words.size(); ++j) { int temp = words[i].size() * words[j].size() ...

只出现一次的数字 原题链接：https://leetcode.cn/problems/WGki4K/description/ 给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。 1.暴力法1234567891011121314151617class Solution {public: int singleNumber(vector<int> &nums) { vector<int> ans = nums; sort(ans.begin(), ans.end()); ans.erase(unique(ans.begin(), ans.end()), ans.end()); for (int i = 0; i < ans.size(); ++i) { int count = 0; for (int j = 0; j < nums.size(); ++j) { if (nums[j] == ans[i]) count++; if (count > 1) break; } if (count == 1) return ans[i]; } return -1; }}; 2.哈希法哈希法：哈希映射统计数组中每个元素的出现次数，在统计完成后，遍历哈希映射即可找出只出现一次的元素。 12345678910111213141516class Solution {public: int singleNumber(vector<int>& nums) { int ans = 0; unordered_map<int, int> unmap; for (int num : nums) unmap[num]++; pair<i ...

整数除法 原题链接：https://leetcode.cn/problems/xoh6Oh/ 编程语言可能会提供占据不同内存空间的整数类型，每种类型能表示的整数范围不同， 无符号整数无论二进制表示的最高位是0还是1，其都表示一个正数，32位整数的范围为 ~ 。由于整数范围的限制，如果计算结果超出了范围，就会产生溢出。产生溢出时运行不会出错，但是计算结果可能会出乎意料。 1.减法主要思路：为了求得dividend/divisor，可以不断的从dividend里减去divisor，当不能再减去更多的divisor时，循环执行的次数就是商 存在问题： 当除数很大时，减法操作执行的次数就会很多，导致程序超时，如 没有考虑除数与被除数，在32位int数据类型的范围溢出问题 没有考虑除法结果，在32位int数据类型的范围溢出问题 12345678910111213141516class Solution {public: int divide(int dividend, int divisor) { int flag = 0; int count = 0; if (dividend < 0 && divisor > 0 || dividend > 0 && divisor < 0) flag = 1; dividend = abs(dividend); divisor = abs(divisor); while (dividend - divisor >= 0) { dividend -= divisor; count++; } if (flag) count = -count; return count; }}; 2.减法的优化主要思路： 当被除数大于除数时，继续比较判断被除数是否大于除数的2倍，如果是则继续判断是否大于除数的4倍、8倍、… 倍， 如果被除数最多大于除数的 倍，则将被除数减去除数的 倍，然后将剩余的被除数重复前面的步骤（由于每次 ...

最大子数组和 原题链接：https://leetcode.cn/problems/maximum-subarray/ 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 子数组是数组中的一个连续部分。 12345678class Solution {public: int maxSubArray(vector<int>& nums) { int final = nums[0], ans = nums[0]; ans = max(nums[i], ans + nums[i]); fin = max(fin, ans); }}; 这是一道典型的使用「动态规划」解决的问题，需要我们掌握动态规划问题设计状态的技巧（无后效性）， 并且需要知道如何推导状态转移方程，最后再去优化空间。 1.动态规划step1问题理解「力扣」第 53 题（最大子序和）是「力扣」第 124 题（二叉树的最大路径和）的线性版本，它们的状态设计思想和状态转移是类似的，希望大家能够通过本题题解进一步体会状态是如何想到的（即子问题的定义需要从哪些方面考虑）。 本题接的重点在「关键 1：理解题意」和「关键 2：如何定义子问题（如何定义状态）」和「最后再谈谈「无后效性」。 关键 1：理解题意 题目要我们找出和最大的连续子数组的值是多少，「连续」是关键字，连续很重要，不是子序列。 题目只要求返回结果，不要求得到最大的连续子数组是哪一个。这样的问题通常可以使用「动态规划」解决。 关键 2：如何定义子问题（如何定义状态） 设计状态思路：把不确定的因素确定下来，进而把子问题定义清楚，把子问题定义得简单。动态规划的思想通过解决了一个一个简单的问题，进而把简单的问题的解组成了复杂的问题的解。 友情提示：上面这句话大家姑且这么一看，脑子里有个印象，没有那么绝对。可能不同的人看会有不同的理解。如果我以后讲解的动态规划的设计思想与这里讲解的「设计状态思路」不一样的，我会再和大家说明。如果讲解有误导的地方，还请大家指出。 我们 不知道和最大的连续子数组一定会选哪一个数，那么我们可以求出 所有 经过输入数组的某一个数的连续子数组的最大和。 例如，示例 1 输 ...