直击腾讯数组面试题及其完整答案

直击腾讯数组面试题及其完整答案考试时间：______分钟总分：______分姓名：______1.在Java语言中，以下关于数组的说法正确的是（）A.数组在内存中是连续存储的B.数组的长度在创建后可以随意改变C.数组可以存储基本数据类型和引用数据类型D.数组访问下标越界时一定会抛出NullPointerException异常2.使用二分查找算法在一个有序数组中查找元素，其时间复杂度是（）A.O(n)B.O(n^2)C.O(logn)D.O(1)3.以下哪种算法策略通常用于数组反转或寻找两数之和？（）A.贪心算法B.动态规划C.双指针法D.分治法4.关于数组的空间复杂度，以下描述正确的是（）A.如果不使用额外的辅助数组，空间复杂度通常为O(1)B.空间复杂度总是等于数组的大小C.空间复杂度只取决于输入规模D.递归解法通常比迭代解法空间复杂度低5.在Java中，ArrayList的扩容机制通常是将容量变为原来的（）A.1倍B.2倍C.0.5倍D.3倍6.题目：给定一个有序整数数组nums和一个目标值target，请在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。要求时间复杂度优于O(n^2)，最合适的算法是（）A.暴力枚举法B.哈希表法C.二分查找法D.归并排序法7.题目：盛最多水的容器，使用双指针法求解，指针移动的原则通常是（）A.固定一个指针，移动另一个指针B.移动指向较小数值的那个指针C.移动指向较大数值的那个指针D.两个指针同时向中间移动一半距离8.题目：旋转数组，将一个数组向右移动k步，要求在原数组上操作，空间复杂度O(1)，常用的方法是（）A.直接拼接字符串B.先反转整个数组，再反转前k个，最后反转剩余部分C.使用额外的数组进行拷贝D.使用队列进行辅助9.题目：寻找旋转排序数组中的最小值，如果使用二分查找，当nums[mid]>nums[right]时，说明最小值在（）A.[left,mid]B.[mid,right]C.[left,right]D.[mid+1,right]10.题目：三数之和，为了去重，在固定第一个数后，如果nums[i]==nums[i-1]，应该（）A.继续寻找B.跳过该元素C.交换位置D.重新开始循环11.下列关于数组的描述，正确的是（）A.数组在内存中占用一段连续的存储空间B.数组支持随机访问，访问任意下标的时间复杂度均为O(1)C.数组在插入或删除元素时，通常需要移动后续元素，效率较低D.数组的大小在创建时确定，之后无法修改12.下列哪些算法思想常用于解决数组相关的经典问题？（）A.双指针法B.滑动窗口C.二分查找D.深度优先搜索13.在使用二分查找时，需要满足的条件包括（）A.数组必须是有序的B.数组中的元素不能重复C.可以是升序或降序排列D.查找范围是连续的14.关于数组去重，下列哪些方法可以实现？（）A.使用Set集合去重（会改变空间复杂度）B.先排序，然后相邻比较去重（会改变顺序）C.双指针法原地去重（不改变空间复杂度）D.使用位运算去重（仅适用于特定情况）15.以下哪些题目属于数组中的经典高频面试题？（）A.两数之和B.三数之和C.最长连续递增序列D.路径总和16.请手写代码实现数组反转。要求：(1)输入一个整型数组nums(2)原地修改该数组，使数组元素顺序反转(3)空间复杂度要求O(1)17.请简述“双指针法”在解决数组问题中的核心思想，并结合“移除元素”这一经典题目进行说明。要求：(1)解释双指针法的含义(2)简述如何利用双指针将时间复杂度从O(n^2)降低到O(n)18.给定一个有序数组nums，在原数组中移除重复项，使每个元素只出现一次，返回移除后数组的新长度。要求：(1)不要使用额外的数组空间，必须在原地修改输入数组(2)示例：输入[0,0,1,1,1,2,2,3,3,4]，输出5，并将前5个元素修改为[0,1,2,3,4]19.题目：合并两个有序数组给你两个按非递减顺序排列的整数数组nums1和nums2，另有一个数组merged，它的初始长度为m+n，其中前m个元素代表nums1的前m个元素，后n个元素为0。请将nums1和nums2合并为同一个有序数组，并返回合并后的数组。要求：(1)请描述算法思路(2)从后往前填充，避免覆盖未处理的元素20.题目：接雨水给定n个非负整数表示每个宽度为1的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。要求：(1)描述解题思路（如预处理最大高度数组）(2)给出核心逻辑伪代码试卷答案1.答案：A、C解析：*A正确：数组在内存中是连续存储的，这是数组支持随机访问的基础。*B错误：数组在创建后，其长度（大小）通常是固定的，无法直接改变。Java中的`ArrayList`虽然长度可变，但其底层依然是数组，扩容时是创建新数组并复制元素，而非修改原数组。*C正确：数组既可以存储基本数据类型（如int,char），也可以存储引用数据类型（如Object）。*D错误：数组访问下标越界时抛出的是`ArrayIndexOutOfBoundsException`，而`NullPointerException`是空指针异常，通常发生在访问`null`对象的属性或方法时。2.答案：C解析：二分查找算法通过不断将查找范围对半分割，每次排除一半的数据，因此其时间复杂度为O(logn)。3.答案：C解析：双指针法是指使用两个指针在数组中移动。在解决数组反转、两数之和等需要同时考虑数组两端或距离较远的元素时，双指针法效率极高，能将暴力解法的O(n^2)降低到O(n)。4.答案：A解析：*A正确：如果在原数组上操作，不使用额外的辅助数组（如Set或新数组），且算法本身的递归栈深度固定，空间复杂度通常为O(1)。*B错误：空间复杂度取决于算法的实现和输入规模，而不是仅仅等于数组大小（例如某些算法可能只存储几个变量）。*C错误：空间复杂度还取决于算法内部是否使用了额外的数据结构。*D错误：递归算法通常需要调用栈，空间复杂度较高（O(n)），通常比迭代算法（O(1)）差。5.答案：B解析：在Java中，`ArrayList`的默认扩容机制是：当当前容量不足时，会将容量扩容为原来的1.5倍。6.答案：B解析：*A错误：时间复杂度为O(n^2)，效率低，不符合题目“优于O(n^2)”的要求。*B正确：使用哈希表存储已遍历元素的值及其索引。在遍历过程中，通过`target-num`在哈希表中查找，时间复杂度降为O(n)。*C错误：二分查找仅适用于有序数组，且只能查找一个特定值或判断存在性，无法直接解决“和为target”的问题。*D错误：归并排序是排序算法，时间复杂度为O(nlogn)，不如哈希表法高效。7.答案：B解析：盛最多水的容器问题中，移动指向较小数值的指针更有可能找到更大的面积。因为面积由较短的边决定，移动较长的边无法增加面积，反而可能因为距离缩短而减小面积；而移动较短的边有可能找到更长的边，从而增加面积。8.答案：B解析：空间复杂度O(1)的原地旋转方法通常是“三次反转法”：1.反转整个数组。2.反转前k个元素。3.反转剩余的n-k个元素。这种方法不需要额外的数组空间。9.答案：D解析：在寻找旋转数组的最小值时，如果`nums[mid]>nums[right]`，说明mid在左半边的递增序列中，最小值一定在mid的右边（包含mid，因为mid位置可能就是最小值），所以范围是`[mid+1,right]`。10.答案：B解析：三数之和去重是为了避免输出重复的三元组。在固定第一个数`nums[i]`后，如果`nums[i]`等于上一个数`nums[i-1]`，说明以该数开头的组合已经被枚举过，直接`continue`跳过即可。11.答案：A、B、C、D解析：*A正确：连续内存。*B正确：内存地址连续，计算公式为`base+index*typeSize`，因此访问任意下标都是O(1)。*C正确：插入或删除元素（非末尾）需要移动后续所有元素，时间复杂度为O(n)。*D正确：数组长度在创建时确定，Java中数组是静态的，不能直接改变大小。12.答案：A、B、C解析：*A正确：双指针法是解决数组问题的核心。*B正确：滑动窗口常用于解决子数组/子串问题。*C正确：二分查找是处理有序数组的标准算法。*D错误：深度优先搜索（DFS）主要用于树或图的遍历，虽然可以用数组模拟栈来实现，但在纯数组线性问题中不如双指针直接。13.答案：A、C、D解析：*A正确：二分查找要求数组必须是有序的。*B错误：二分查找可以处理重复元素，只是返回的是任意一个匹配项或判断是否存在。*C正确：可以是升序，也可以是降序，二分查找逻辑只需调整比较方向即可。*D正确：查找范围必须是连续的索引区间。14.答案：A、B、C解析：*A正确：利用Set的自动去重特性，但会消耗O(n)的额外空间。*B正确：排序后，相同的元素相邻，比较相邻元素即可去重，但会改变原数组的相对顺序。*C正确：双指针法可以标记去重后的边界，原地修改数组，空间复杂度为O(1)。*D错误：位运算去重通常用于整数集合的特殊位操作或特定位掩码处理，不适合通用的数组去重场景。15.答案：A、B、C解析：*A正确：两数之和是数组最经典的题。*B正确：三数之和考察多指针和去重，是腾讯面试常见题。*C正确：最长连续递增序列考察单指针遍历，是基础必考题。*D错误：路径总和通常是树的问题，虽然可以用数组模拟，但不是数组题目的核心考察点。16.答案与解析：解析：使用双指针法，一个指针指向头部（left），一个指向尾部（right）。交换两个指针所指的元素，然后左指针右移，右指针左移，直到两个指针相遇。代码示例：```javapublicstaticvoidreverseArray(int[]nums){intleft=0;intright=nums.length-1;while(left<right){//交换inttemp=nums[left];nums[left]=nums[right];nums[right]=temp;left++;right--;}}```17.答案与解析：解析：*核心思想：双指针法是指使用两个指针（如慢指针`slow`和快指针`fast`，或左指针`left`和右指针`right`）在数组中同时移动，以减少循环次数，提高效率。*结合“移除元素”：例如移除数组中的某个值。如果不使用双指针，可能需要两层循环（外层遍历，内层移动元素），复杂度为O(n^2)。使用双指针时，慢指针`j`指向当前有效元素的位置，快指针`i`负责扫描数组。当`nums[i]==val`时，快指针继续前进；当`nums[i]!=val`时，将`nums[i]`赋值给`nums[j]`，然后`i`和`j`同时前进。这样只需要一次遍历，时间复杂度降为O(n)。18.答案与解析：解析：*思路：使用慢指针`j`来记录不重复元素的边界。慢指针初始指向0（第一个元素），快指针`i`从1开始遍历。*逻辑：比较`nums[i]`和`nums[j-1]`。如果相等，说明`nums[i]`是重复的，快指针`i`直接后移，跳过该元素；如果不相等，说明`nums[i]`是新的不重复元素，将`nums[i]`赋值给`nums[j]`，然后`i`和`j`都后移。代码示例：```javapublicintremoveDuplicates(int[]nums){if(nums.length==0)return0;intj=0;for(inti=1;i<nums.length;i++){if(nums[i]!=nums[j]){j++;nums[j]=nums[i];}}returnj+1;}```19.答案与解析：解析：*思路：由于`nums1`的长度是`m+n`，且前`m`个元素是有序的，后`n`个元素是0。为了不覆盖`nums1`中未处理的元素，应该从数组的末尾开始填充。*逻辑：使用三个指针。`p1`指向`nums1`的最后一个有效元素（索引`m-1`），`p2`指向`nums2`的最后一个元素（索引`n-1`），`p`指向`nums1`的合并后最后一个位置（索引`m+n-1`）。比较`nums1[p1]`和`nums2[p2]`，将较大的值放入`nums[p]`，然后移动相应的指针。最后处理`nums1`中剩余的元素（如果`nums2`先移空了）。代码示例：```javapublicvoidmerge(int[]nums1,intm,int[]nums2,intn){intp1=m-1;intp2=n-1;intp=m+n-1;while(p1>=0&&p2>=0){if(nums1[p1]>nums2[p2]){nums1[p]=nums1[p1];p1--;}else{nums1[p]=nums2[p2];p2--;}p--;}//如果p2还没遍历完，剩下的直接覆盖到nums1前面while(p2>=0){nums1[p]=nums2[p2];p2--;p--;}}```20.答案与解析：解析：*思路：预处理法。对于每个位置`i`，接雨水的量取决于该位置左侧的最大高度和右侧的最大高度中的较小值，减去当前高度`height[i]`。*逻辑：1.先创建两个数组`leftMax`和`