大厂笔试面试八股文-算法-数组常考题-final

刷了200道数组题,笔试面试还是不会做?这10道搞懂就够了刷了200道数组题,面试还是不会做?问题不是你刷得不够多,而是没抓住核心套路。我整理了35道大厂真题,发现其实就5个核心技巧。今天把最重要的10道题和背后的套路,全部分享给你。offer直通车-大厂校招大礼包入口 这10道题是:两数之和- 哈希表基础三数之和- 双指针经典合并两个有序数组- 双指针应用盛最多水的容器- 对撞指针接雨水- 单调栈经典最大子序和- 动态规划入门螺旋矩阵- 矩阵遍历旋转图像- 矩阵操作缺失的第一个正数- 原地哈希最长连续序列- 哈希表优化 为什么是这10道题?数据不会骗人我分析了35道数组高频题,发现:这10道题覆盖了5个核心技巧掌握这10道,其他题目都能举一反三不是题目多就好,而是要抓住本质不是题海战术,是套路识别很多人刷题的问题在于:刷了100道,每道都是新题看到题目,不知道用什么方法面试时,脑子一片空白真正高效的刷题方法:先掌握核心套路再通过题目强化套路最后做到看到题目就知道用什么套路这10道题,就是帮你建立套路识别能力的最佳选择。 核心技巧1:双指针为什么双指针这么重要?双指针是数组题的瑞士军刀,适用场景最广。核心思想:用两个指针,从不同位置或方向遍历数组,降低时间复杂度。三种模式:对撞指针:从两端向中间快慢指针:一个快一个慢滑动窗口:维护一个区间题目1:两数之和题目描述: 给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。为什么重要:最基础的哈希表应用面试出现频率极高是三数之和、四数之和的基础核心思路:用哈希表存储已遍历的数字,查找时间从O(n)降到O(1)。代码实现:vectorint twoSum(vectorint nums, int target) { unordered_mapint, int hash; for (int i 0; i nums.size(); i) { int complement target - nums[i]; if (hash.count(complement)) { return {hash[complement], i}; } hash[nums[i]] i; } return {}; }时间复杂度: O(n)空间复杂度: O(n)面试要点:能说出暴力解法(O(n²))和优化解法(O(n))注意边界:数组为空、只有两个元素注意重复元素的处理题目2:三数之和题目描述: 给定一个数组,找出所有和为0的三元组。为什么重要:双指针的经典应用考察去重能力是N数之和的通用模板核心思路:先排序固定一个数,剩下两个数用双指针注意去重代码实现:vectorvectorint threeSum(vectorint nums) { vectorvectorint result; sort(nums.begin(), nums.end()); for (int i 0; i nums.size(); i) { if (i 0 nums[i] nums[i-1]) continue; // 去重 int left i 1, right nums.size() - 1; while (left right) { int sum nums[i] nums[left] nums[right]; if (sum 0) { result.push_back({nums[i], nums[left], nums[right]}); while (left right nums[left] nums[left1]) left; // 去重 while (left right nums[right] nums[right-1]) right--; // 去重 left; right--; } else if (sum 0) { left; } else { right--; } } } return result; }时间复杂度: O(n²)空间复杂度: O(1)面试要点:为什么要先排序?如何去重?(三个位置都要去重)能扩展到四数之和吗?题目3:合并两个有序数组题目描述: 将两个有序数组合并到第一个数组中,保持有序。为什么重要:双指针最简单的应用考察从后往前遍历的技巧归并排序的基础核心思路:从后往前填充,避免覆盖未处理的元素。代码实现:void merge(vectorint nums1, int m, vectorint nums2, int n) { int i m - 1, j n - 1, k m n - 1; while (i 0 j 0) { if (nums1[i] nums2[j]) { nums1[k--] nums1[i--]; } else { nums1[k--] nums2[j--]; } } while (j 0) { nums1[k--] nums2[j--]; } }时间复杂度: O(mn)空间复杂度: O(1)面试要点:为什么从后往前?如果从前往后会怎样?只需要处理nums2剩余元素,为什么?题目4:盛最多水的容器题目描述: 给定n个非负整数,每个数代表坐标中的一个点(i, ai)。找出其中的两条线,使得它们与x轴共同构成的容器可以容纳最多的水。为什么重要:对撞指针的经典应用考察贪心思想面试高频题核心思路:双指针从两端向中间移动,每次移动较短的那条边。为什么移动短边?容器的容量由短边决定移动长边,容量只会变小移动短边,容量可能变大代码实现:int maxArea(vectorint height) { int left 0, right height.size() - 1; int maxWater 0; while (left right) { int h min(height[left], height[right]); int w right - left; maxWater max(maxWater, h * w); if (height[left] height[right]) { left; } else { right--; } } return maxWater; }时间复杂度: O(n)空间复杂度: O(1)面试要点:能解释为什么移动短边能证明这个贪心策略的正确性和接雨水的区别是什么? 核心技巧2:单调栈什么是单调栈?单调栈是一种特殊的栈,栈内元素保持单调递增或递减。适用场景:找下一个更大/更小的元素找左右边界矩形面积问题题目5:接雨水题目描述: 给定n个非负整数表示每个宽度为1的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。为什么重要:单调栈的经典应用有多种解法(动态规划、双指针、单调栈)面试超高频题核心思路(单调栈):维护一个单调递减栈,遇到比栈顶大的元素时,说明可以接水。代码实现:int trap(vectorint height) { stackint st; int water 0; for (int i 0; i height.size(); i) { while (!st.empty() height[i] height[st.top()]) { int top st.top(); st.pop(); if (st.empty()) break; int distance i - st.top() - 1; int h min(height[i], height[st.top()]) - height[top]; water distance * h; } st.push(i); } return water; }时间复杂度: O(n)空间复杂度: O(n)面试要点:能说出至少2种解法单调栈解法的核心思想和盛最多水的容器有什么区别? 核心技巧3:动态规划动态规划的核心四步走:定义状态写出状态转移方程初始化确定遍历顺序题目6:最大子序和题目描述: 给定一个整数数组,找到一个具有最大和的连续子数组。为什么重要:动态规划入门题Kadane算法的经典应用面试必考核心思路:dp[i]表示以i结尾的最大子序和。状态转移方程:dp[i] max(dp[i-1] nums[i], nums[i])代码实现:int maxSubArray(vectorint nums) { int maxSum nums[0]; int currentSum nums[0]; for (int i 1; i nums.size(); i) { currentSum max(currentSum nums[i], nums[i]); maxSum max(maxSum, currentSum); } return maxSum; }时间复杂度: O(n)空间复杂度: O(1)面试要点:能写出状态转移方程能优化空间复杂度(滚动变量)如果要返回子数组的起止位置怎么办? 核心技巧4:矩阵操作矩阵题的通用技巧找规律(旋转、螺旋)原地修改(用特殊值标记)分层处理题目7:螺旋矩阵题目描述: 给定一个m x n的矩阵,按照螺旋顺序返回矩阵中的所有元素。为什么重要:考察边界处理能力模拟类题目的代表面试常考核心思路:按层遍历,每层按照右→下→左→上的顺序。代码实现:vectorint spiralOrder(vectorvectorint matrix) { vectorint result; if (matrix.empty()) return result; int top 0, bottom matrix.size() - 1; int left 0, right matrix[0].size() - 1; while (top bottom left right) { // 右 for (int i left; i right; i) { result.push_back(matrix[top][i]); } top; // 下 for (int i top; i bottom; i) { result.push_back(matrix[i][right]); } right--; // 左 if (top bottom) { for (int i right; i left; i--) { result.push_back(matrix[bottom][i]); } bottom--; } // 上 if (left right) { for (int i bottom; i top; i--) { result.push_back(matrix[i][left]); } left; } } return result; }时间复杂度: O(m×n)空间复杂度: O(1)面试要点:边界条件的处理(为什么左和上要加判断?)能画图说明遍历过程螺旋矩阵II(生成螺旋矩阵)会做吗?题目8:旋转图像题目描述: 给定一个n×n的二维矩阵表示一个图像,将图像顺时针旋转90度。要求原地旋转。为什么重要:考察找规律能力原地操作的经典题面试常考核心思路:先转置,再翻转每一行。代码实现:void rotate(vectorvectorint matrix) { int n matrix.size(); // 转置 for (int i 0; i n; i) { for (int j i 1; j n; j) { swap(matrix[i][j], matrix[j][i]); } } // 翻转每一行 for (int i 0; i n; i) { reverse(matrix[i].begin(), matrix[i].end()); } }时间复杂度: O(n²)空间复杂度: O(1)面试要点:为什么先转置再翻转?如果是逆时针旋转怎么办?如果是旋转180度呢? 核心技巧5:原地修改 哈希表什么时候用原地修改?空间复杂度要求O(1)数组元素范围有限可以用特殊值标记题目9:缺失的第一个正数题目描述: 给定一个未排序的整数数组,找出其中没有出现的最小的正整数。要求O(n)时间和O(1)空间。为什么重要:原地哈希的经典应用考察空间优化能力面试难题核心思路:把每个数放到它应该在的位置(nums[i] i1)。代码实现:int firstMissingPositive(vectorint nums) { int n nums.size(); // 把每个数放到正确位置 for (int i 0; i n; i) { while (nums[i] 0 nums[i] n nums[nums[i] - 1] ! nums[i]) { swap(nums[i], nums[nums[i] - 1]); } } // 找第一个不在正确位置的数 for (int i 0; i n; i) { if (nums[i] ! i 1) { return i 1; } } return n 1; }时间复杂度: O(n)空间复杂度: O(1)面试要点:为什么时间复杂度是O(n)?(每个元素最多交换一次)如何实现原地哈希?边界条件的处理题目10:最长连续序列题目描述: 给定一个未排序的整数数组,找出最长连续序列的长度。要求O(n)时间。为什么重要:哈希表的巧妙应用考察优化思维面试高频题核心思路:用哈希表存储所有数字,然后只从序列的起点开始计数。代码实现:int longestConsecutive(vectorint nums) { unordered_setint numSet(nums.begin(), nums.end()); int maxLen 0; for (int num : numSet) { // 只从序列起点开始 if (!numSet.count(num - 1)) { int currentNum num; int currentLen 1; while (numSet.count(currentNum 1)) { currentNum; currentLen; } maxLen max(maxLen, currentLen); } } return maxLen; }时间复杂度: O(n)空间复杂度: O(n)面试要点:为什么只从序列起点开始?(避免重复计算)如何保证时间复杂度是O(n)?如果要求O(1)空间怎么办?(先排序,O(nlogn)时间) 如何举一反三?套路识别清单看到题目,先问自己:1. 是否需要查找/去重?→ 考虑哈希表2. 是否需要优化时间复杂度?→ 考虑双指针、二分查找3. 是否有下一个更大/更小?→ 考虑单调栈4. 是否有最优子结构?→ 考虑动态规划5. 是否需要原地操作?→ 考虑原地哈希、标记法刷题建议第一遍:理解套路这10道题,每道都要手写一遍理解为什么用这个方法能说出时间和空间复杂度第二遍:变形练习两数之和 → 三数之和 → 四数之和螺旋矩阵 → 螺旋矩阵II旋转图像 → 逆时针旋转第三遍:总结模板双指针模板单调栈模板动态规划模板面试技巧1. 先说思路,再写代码不要上来就写先和面试官确认思路得到认可再动手2. 注意边界条件数组为空只有一个元素所有元素相同3. 分析复杂度写完代码后主动说明能说出优化方向4. 测试用例正常用例边界用例特殊用例