题目 1移除有序数组中的重复元素题目描述给定一个升序排列的数组nums请你原地删除重复出现的元素使每个元素只出现一次返回删除后数组的新长度。不要使用额外的数组空间必须在原地修改输入数组并在使用 O (1) 额外空间的条件下完成。解题思路采用快慢双指针法慢指针slow指向当前已去重数组的最后一个位置快指针fast遍历整个数组当nums[fast]与nums[slow]不相等时说明遇到了新元素将慢指针后移一位把快指针的值复制到慢指针位置最终慢指针索引 1 就是去重后的数组长度代码实现cpp运行int removeDuplicates(vectorint nums) { if (nums.empty()) return 0; int slow 0; for (int fast 1; fast nums.size(); fast) { if (nums[fast] ! nums[slow]) { slow; nums[slow] nums[fast]; } } return slow 1; }复杂度分析时间复杂度O (n)仅遍历数组一次空间复杂度O (1)原地修改无额外空间开销面试考点双指针思想是数组题的核心技巧面试官常延伸问如果允许每个元素最多出现 2 次怎么改只需将判断条件改为nums[fast] ! nums[slow-1]即可。题目 2旋转数组题目描述给定一个数组将数组中的元素向右移动k个位置其中k是非负数。要求使用空间复杂度 O (1)的原地算法解决。解题思路经典三次反转法无需额外空间先反转整个数组反转前 k 个元素反转后 n-k 个元素 注意k 可能大于数组长度需要先对 k 取模k % n。代码实现cpp运行void reverse(vectorint nums, int left, int right) { while (left right) { swap(nums[left], nums[right]); left; right--; } } void rotate(vectorint nums, int k) { int n nums.size(); k % n; reverse(nums, 0, n - 1); // 反转整个数组 reverse(nums, 0, k - 1); // 反转前k个 reverse(nums, k, n - 1); // 反转后n-k个 }复杂度分析时间复杂度O (n)每个元素被反转两次总操作次数为 2n空间复杂度O (1)原地操作面试考点考察数组的原地操作技巧。面试官常追问向左旋转怎么实现如果用额外数组怎么写对比不同方案的时空开销。题目 3最长公共前缀题目描述编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀返回空字符串。解题思路纵向扫描法 以第一个字符串为基准逐字符检查其他所有字符串在该位置是否相同遇到不同字符或某字符串提前结束时停止返回当前前缀。代码实现cpp运行string longestCommonPrefix(vectorstring strs) { if (strs.empty()) return ; // 以第一个字符串为基准 for (int i 0; i strs[0].size(); i) { char c strs[0][i]; // 检查其他所有字符串的第i位 for (int j 1; j strs.size(); j) { // 其他字符串长度不足i或字符不相等 if (i strs[j].size() || strs[j][i] ! c) { return strs[0].substr(0, i); } } } return strs[0]; }复杂度分析时间复杂度O (m*n)m 是字符串平均长度n 是字符串数量空间复杂度O (1)面试考点考察字符串边界处理能力。延伸问法用分治法怎么实现字典树Trie解法的优劣题目 4两数之和题目描述给定一个整数数组nums和一个整数目标值target请你在该数组中找出和为目标值target的那两个整数并返回它们的数组下标。你可以假设每种输入只会对应一个答案且同一个元素不能重复使用。解题思路哈希表一次遍历法 遍历数组时用哈希表存储「元素值 → 索引」的映射。对于当前元素nums[i]检查target - nums[i]是否在哈希表中存在直接返回两个索引不存在将当前元素和索引存入哈希表继续遍历代码实现cpp运行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 (1)空间复杂度O (n)哈希表最多存储 n 个元素面试考点考察空间换时间的优化思想。面试官常对比暴力法 O (n²)、排序 双指针法、哈希表法三种方案的优劣与适用场景。文档 2链表专项面试题题目 1反转单链表题目描述给你单链表的头节点head请你反转链表并返回反转后的链表。分别用迭代和递归两种方式实现。解题思路迭代法三指针 用三个指针prev、curr、next遍历链表逐个改变节点的 next 指向最终 prev 成为新的头节点。递归法 递归反转当前节点之后的子链表然后将当前节点的下一个节点的 next 指向当前节点当前节点的 next 置空。代码实现cpp运行struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} }; // 迭代法 ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; ListNode* curr head; while (curr) { ListNode* next curr-next; // 保存下一个节点 curr-next prev; // 反转指针 prev curr; // prev后移 curr next; // curr后移 } return prev; } // 递归法 ListNode* reverseList(ListNode* head) { if (!head || !head-next) return head; ListNode* newHead reverseList(head-next); head-next-next head; head-next nullptr; return newHead; }复杂度分析迭代法时间 O (n)空间 O (1)递归法时间 O (n)空间 O (n)递归栈开销面试考点链表基础必考题。面试官常延伸反转链表的前 k 个节点反转指定区间内的链表谢谢