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

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

---

---

😊点此到文末惊喜↩︎

基本算法

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

---

子串篇

560. 和为 K 的子数组

1. 问题
   • 给你一个整数数组 nums 和一个整数 k
   • 请你统计并返回 该数组中和为 k 的连续子数组的个数 。
2. 思路
   • 滑动窗口：无法通过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，值为1unordered_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;
}

3. 总结
   • unordered_map比map更加节省空间
   • 使用if (umap.count(target_key) > 0)，判断目标元素是否存在

239. 滑动窗口最大值(单调队列)

1. 问题
   • 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
   • 你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回每次滑动窗口中的最大值 。
2. 思路
   • 定义大根堆处理最值，每次滑动将新元素加入堆中并记录滑出元素，如果弹出最大元素不在滑出元素中即为结果，若是滑出元素则继续弹出堆顶元素。
   • 单调队列：维护一个单调队列（从大到小）
     • 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. 最小覆盖子串

1. 问题
   • 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。
   • 如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
   • 输入：s = “ADOBECODEBANC”, t = “ABC”
   • 输出：“BANC”
2. 思路
   • 代码手法：先记录值，然后进行增量条件，最后再对值进行复杂的条件判断

// 返回字符串 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中是否存在cwindow[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. 最大子数组和

1. 问题
   • 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组
   • 子数组最少包含一个元素，返回其最大和。（子数组 是数组中的一个连续部分）
2. 思路
   • 贪心思路：负数一定是拉低总和。一直保存连续区间的最大值，如果连续区间值为负数，则重新开始计算连续区间值
   • 动态规划：对于过去状态是否选择的一个标准

// 贪心
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. 合并区间

1. 问题
   • 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
   • 请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间
2. 思路
   • 双指针：数组的原地条件删除

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. 轮转数组

1. 问题
   • 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
2. 思路
   • 辅助存储空间，直接分段存储
   • 两次反转：整体反转，然后部分反转
   • 每次跳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. 除自身以外数组的乘积

1. 问题
   • 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
   • 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
2. 思路
   • 分解的思想：将 $n^2$ 转化为 $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. 缺失的第一个正数

1. 问题
   • 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
2. 思路
   • 数组+交换：可以降低时间复杂度和空间复杂度
   • 原地哈希
     • 将数组视为哈希表， 1放在下标为0位置上，2放在下标为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. 矩阵置零

1. 问题
   • 给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。
2. 思路
   • 有重复则去重：通过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. 螺旋矩阵

1. 问题
   • 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
2. 思路
   • 边界变化：通过规定四个边界进行处理

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.旋转图像

1. 问题
   • 给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
   • 必须在 原地 旋转图像
2. 思路
   • 找映射规律：原索引位置matrix[i][j] -> 旋转后索引位置matrix[i][n-1-i]

// 直接映射
void rotate(vector<vector<int>>& matrix) {int n = matrix.size();// 深拷贝 matrix -> tmpvector<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) {// 设矩阵行列数为 nint 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 至 tmpint tmp = matrix[i][j];// 元素旋转操作 A <- D <- C <- B <- tmpmatrix[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;}}
}

3. 总结
   • while循环一定要注意增量条件：while(条件) { ··· ++p;}
   • 看好是不是矩形，是m*n还是n*n

240. 搜索二维矩阵 II

1. 问题
   • 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target
   • 每行的元素从左到右升序排列。
   • 每列的元素从上到下升序排列。
2. 思路
   • 找映射规律：原索引位置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;
}

---

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

---

🚩点此跳转到首行↩︎

参考博客

1. 前缀和问题
2. 单调队列
3. 快速链表quicklist
4. 《深入理解计算机系统》
5. 侯捷C++全系列视频
6. 待定引用
7. 待定引用
8. 待定引用