【面试HOT100】子串普通数组矩阵

系列综述： 💞目的：本系列是个人整理为了秋招面试的，整理期间苛求每个知识点，平衡理解简易度与深入程度。 🥰来源：材料主要源于LeetCodeHot100进行的，每个知识点的修正和深入主要参考各平台大佬的文章，其中也可能含有少量的个人实验自证。 🤭结语：如果有帮到你的地方，就点个赞和关注一下呗，谢谢🎈🎄🌷！！！ 🌈【C++】秋招&实习面经汇总篇

---

文章目录 基本算法子串篇560. 和为 K 的子数组239. 滑动窗口最大值(单调队列)76. 最小覆盖子串 普通数组篇53. 最大子数组和56. 合并区间189. 轮转数组238. 除自身以外数组的乘积41. 缺失的第一个正数 矩阵篇73. 矩阵置零54. 螺旋矩阵48.旋转图像240. 搜索二维矩阵 II 参考博客

---

😊点此到文末惊喜↩︎

基本算法 排序set去重哈希：数组全部扔入unordered_map可通过O(1)时间进行查找

---

子串篇 560. 和为 K 的子数组 问题 给你一个整数数组 nums 和一个整数 k请你统计并返回 该数组中和为 k 的连续子数组的个数 。 思路 滑动窗口：无法通过sum>k判断负数问题暴力方法前缀和（公式变换思想） [left,right]区间的和为k 等价于 前right项的和 - 前left-1项的和 = k单下标转化：前left-1项的和（历史值） = 前right项的和（先锋值） - k。先锋值需要一直记录求解，而历史值可以将先锋值记录在map中，方便以O(1)时间查找 int subarraySum(vector<int>& nums, int k) { int sum = 0, res = 0; // 第一次前缀和恰好等于k时，则sum为0，值为1 unordered_map<int, int> umap{{0, 1}}; for (int& c : nums) { sum += c; // 记录和 if (umap.count(sum - k) > 0) res += umap[sum - k]; ++umap[sum]; // 如果有负数，不同位置可能有相同的前缀和 } return res; } 总结 unordered_map比map更加节省空间使用if (umap.count(target_key) > 0)，判断目标元素是否存在 239. 滑动窗口最大值(单调队列) 问题 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回每次滑动窗口中的最大值 。 思路 定义大根堆处理最值，每次滑动将新元素加入堆中并记录滑出元素，如果弹出最大元素不在滑出元素中即为结果，若是滑出元素则继续弹出堆顶元素。单调队列：维护一个单调队列（从大到小） push时：从与队尾元素比较，如果小于cur则从队尾弹出，直到最后压入元素pop时： vector<int> maxSlidingWindow(vector<int>& nums, int k) { // 单调队列 deque<int> que; // 弹出元素：若为left元素则弹出 auto pop = [&que](int value){ if (!que.empty() && value == que.front()) que.pop_front(); }; // 压入元素：从尾部弹出所有比压入值小的，保证队首元素是最大的 auto push =[&que](int value){ while (!que.empty() && value > que.back()) que.pop_back(); que.push_back(value); }; vector<int> result; for (int i = 0; i < k; i++) { // 先将前k的元素放进队列 push(nums[i]); } result.push_back(que.front()); // result 记录前k的元素的最大值 for (int i = k; i < nums.size(); i++) { pop(nums[i - k]); // 滑动窗口移除最前面元素 push(nums[i]); // 滑动窗口前加入最后面的元素 result.push_back(que.front()); // 记录对应的最大值 } return result; } 76. 最小覆盖子串 问题 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。输入：s = “ADOBECODEBANC”, t = “ABC”输出：“BANC” 思路 代码手法：先记录值，然后进行增量条件，最后再对值进行复杂的条件判断 // 返回字符串 s 中包含字符串 t 的全部字符的最小窗口 string SlideWindow(string s, string t) { // need记录子串情况，window记录合适窗口 unordered_map<char, int> need, window; for (char c : t) need[c]++; int left = 0, right = 0; // 记录最小覆盖子串的起始索引及长度 int start = 0, len = INT_MAX; int valid = 0; while (right < s.size()) { // 记录操作值，然后再进行复杂条件判断 char c = s[right]; // c 是将移入窗口的字符 right++; // 右移窗口 // 进行窗口内数据的一系列更新 if (need.count(c)) { // 判断need中是否存在c window[c]++; if (window[c] == need[c]) valid++; } while (valid == need.size()) { // TODO：收缩条件 // TODO：更新结果记录 if (right - left < len) { start = left;// 更新起始值 len = right - left;// 最小长度 } // 收缩窗口 char d = s[left]; left++; // TODO：收缩处理 if (need.count(d)) { if (window[d] == need[d]) valid--; window[d]--; } } } // 返回最小覆盖子串 return len == INT_MAX ? "" : s.substr(start, len); }

---

普通数组篇 53. 最大子数组和 问题 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组子数组最少包含一个元素，返回其最大和。（子数组 是数组中的一个连续部分） 思路 贪心思路：负数一定是拉低总和。一直保存连续区间的最大值，如果连续区间值为负数，则重新开始计算连续区间值动态规划：对于过去状态是否选择的一个标准 // 贪心 int maxSubArray(vector<int>& nums) { int result = INT32_MIN; int count = 0; for (int i = 0; i < nums.size(); i++) { count += nums[i]; if (count > result) { // 取区间累计的最大值（相当于不断确定最大子序终止位置） result = count; } if (count <= 0) count = 0; // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和 } return result; } // 动态规划 int maxSubArray(vector<int>& nums) { int len = nums.size(); // dp[i] 表示：以 nums[i] 结尾的连续子数组的最大和 vector<int> dp(len); dp[0] = nums[0]; for (int i = 1; i < len; i++) { // 状态转移：是否选择过去状态dp[i-1] + 当前nums[i] if (dp[i - 1] > 0) { dp[i] = dp[i - 1] + nums[i]; } else { dp[i] = nums[i]; } } // 也可以在上面遍历的同时求出 res 的最大值，这里我们为了语义清晰分开写，大家可以自行选择 int res = dp[0]; for (int i = 1; i < len; i++) { res = max(res, dp[i]); } return res; } 56. 合并区间 问题 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 思路 双指针：数组的原地条件删除 vector<vector<int>> merge(vector<vector<int>>& intervals) { if (!intervals.size()) return {}; sort(intervals.begin(), intervals.end(), less<vector<int>>()); int slow = 0; int fast = 1; while (fast < intervals.size()) { if (intervals[slow][1] >= intervals[fast][0]) { intervals[slow][1] = max(intervals[fast][1], intervals[slow][1]); } else { slow++; intervals[slow] = intervals[fast]; } fast++; } intervals.resize(slow+1); return intervals; } 189. 轮转数组 问题 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。 思路 辅助存储空间，直接分段存储两次反转：整体反转，然后部分反转每次跳k个，进行覆盖，但是需要判断结束条件。 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); } 238. 除自身以外数组的乘积 问题 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 思路 分解的思想：将 n 2 n^2 n2 转化为 n + n n+n n+n 时间复杂度，res[i] = MUL(0, i-1) * MUL(i+1, end)（写公式，分析公式） vector<int> productExceptSelf(vector<int>& nums) { const int n = nums.size(); vector<int> res(n, 0); // res中每个位置左边的乘积 int k = 1; for (int i = 0; i < n; i ++) { res[i] = k; k *= nums[i]; } // res中每个位置乘以右边的乘积 k = 1; for (int i = n - 1; i >= 0; i --) { res[i] *= k; k *= nums[i]; } return res; } 41. 缺失的第一个正数 问题 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。 思路 数组+交换：可以降低时间复杂度和空间复杂度原地哈希 将数组视为哈希表， 1放在下标为0位置上，2放在下标为1位置上。最后，即 n u m s [ i ] = i + 1 nums[i]=i+1 nums[i]=i+1 // 原地交换 int firstMissingPositive(vector<int>& nums) { int n = nums.size(); for(int i = 0; i < n; i++){ // while继续确定交换回来数的位置 while(nums[i] >= 1 && nums[i] <= n // 规定遍历范围 && nums[i] != nums[nums[i] - 1]){ // 避免原地交换，因为已经成功了 swap(nums[i], nums[nums[i] - 1]); // 将值nums[i]交换到目标位置num[nums[i] - 1] } } for(int i = 0; i < n; i++){ if(nums[i] != i + 1) return i + 1; } return n + 1; } // 哈希法（空间O(n)） int firstMissingPositive(vector<int>& nums) { int n=nums.size(); unordered_map<int,bool> hashmap; for(int& num:nums){ hashmap[num]=true; } for(int i=1;i<=n;i++){ if(hashmap[i]==false) return i; } return n+1; }

---

矩阵篇

解决的问题： 给定一个线性表（字符串、数组等），一次遍历求满足指定条件的连续子部分

73. 矩阵置零 问题 给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。 思路 有重复则去重：通过unordered_set记录，并去除行和列中的重复整体标记法（一个标记可以表示一个整体的属性）：遍历对角线上每个个元素对应的行和列，若存在0则将对象线元素标记为0，最后再将标记为0的对象线元素对应的行列置为0 typedef struct { int x; int y; } Cord; void setZeroes(vector<vector<int>>& matrix) { // 使用两个unordered_set分别存储需要置为0的行和列 unordered_set<int> row_record; unordered_set<int> col_record; for (int i = 0; i < matrix.size(); ++i) { for (int j = 0; j < matrix[0].size(); ++j) { if (matrix[i][j] == 0) { row_record.emplace(i); col_record.emplace(j); } } } for (auto i : row_record) { for (int p = 0; p < matrix[0].size(); ++p) { matrix[i][p] = 0; } } for (auto j : col_record) { for (int p = 0; p < matrix.size(); ++p) { matrix[p][j] = 0; } } } 54. 螺旋矩阵 问题 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。 思路 边界变化：通过规定四个边界进行处理 vector<int> spiralOrder(vector<vector<int>>& matrix) { // 健壮性检查 if (matrix.empty()) return vector<int>(); vector<int> res; int up = 0, down = matrix.size()-1; int left = 0, right = matrix[0].size()-1; while (up <= down && left <= right) { // 从左到右 for (int i = left; i <= right; ++i) res.push_back(matrix[up][i]); ++up; // 缩小上边界 if (up > down) break; // 从上到下 for (int i = up; i <= down; ++i) res.push_back(matrix[i][right]); --right; if (left > right) break; // 从左到右 for (int i = right; i >= left; i--) res.push_back(matrix[down][i]); --down; // 从左到右 for (int i = down; i >= up; i--) res.push_back(matrix[i][left]); ++left; } return res; } 48.旋转图像 问题 给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。必须在 原地 旋转图像 思路 找映射规律：原索引位置matrix[i][j] -> 旋转后索引位置matrix[i][n-1-i] // 直接映射 void rotate(vector<vector<int>>& matrix) { int n = matrix.size(); // 深拷贝 matrix -> tmp vector<vector<int>> tmp = matrix; // 根据元素旋转公式，遍历修改原矩阵 matrix 的各元素 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { matrix[j][n - 1 - i] = tmp[i][j]; } } } // 空间优化 void rotate(vector<vector<int>>& matrix) { // 设矩阵行列数为 n int n = matrix.size(); // 起始点范围为 0 <= i < n / 2 , 0 <= j < (n + 1) / 2 // 其中 '/' 为整数除法 for (int i = 0; i < n / 2; i++) { // 一共转的圈数 for (int j = i; j < n-i-1; j++) { // 每一圈要处理一行对应旋转一次 // 暂存 A 至 tmp int tmp = matrix[i][j]; // 元素旋转操作 A <- D <- C <- B <- tmp matrix[i][j] = matrix[n - 1 - j][i]; matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]; matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]; matrix[j][n - 1 - i] = tmp; } } } 总结 while循环一定要注意增量条件：while(条件) { ··· ++p;}看好是不是矩形，是m*n还是n*n 240. 搜索二维矩阵 II 问题 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target每行的元素从左到右升序排列。每列的元素从上到下升序排列。 思路 找映射规律：原索引位置matrix[i][j] -> 旋转后索引位置matrix[i][n-1-i] bool searchMatrix(vector<vector<int>>& matrix, int target) { if(!matrix.size() && !matrix[0].size()) return false; int i = 0, j = matrix[0].size() - 1; //矩阵右上角 while(i < matrix.size() && j >= 0) { if(matrix[i][j] == target) return true; else if( matrix[i][j] < target) i++; //排除一行 else if( matrix[i][j] > target) j--; //排除一列 } return false; }

---

少年，我观你骨骼清奇，颖悟绝伦，必成人中龙凤。 不如点赞·收藏·关注一波

---

🚩点此跳转到首行↩︎

参考博客 前缀和问题 单调队列 快速链表quicklist《深入理解计算机系统》侯捷C++全系列视频 待定引用 待定引用 待定引用