腾讯数组面试题目与详细答案解析

腾讯经典数组面试题目与详细答案解析考试时间：______分钟总分：______分姓名：______一、单选题1.给定一个整数数组`nums`，其中恰好有两个元素只出现一次，其余所有元素均出现两次。请找出这两个只出现一次的元素。要求算法的时间复杂度为O(n)，空间复杂度为O(1)。以下哪种方法能够满足要求？A.对数组进行排序，然后遍历排序后的数组查找不同的元素。B.使用哈希表记录每个元素的出现次数，然后遍历哈希表找到出现次数为1的元素。C.首先将所有元素异或，得到两个只出现一次元素异或的结果，然后通过该结果的某一位将原数组分成两组，分别异或得到两个只出现一次的元素。D.使用快速排序对数组排序，然后检查相邻元素是否相同，不同的即为只出现一次的元素。2.请实现一个算法，判断一个非空整数数组是否可以被划分为两个子集，使得这两个子集的元素和相等。例如，给定nums=[1,5,11,5]，返回true，因为可以划分为[1,5,5]和[11]两个子集。以下哪种方法适合解决该问题？A.暴力枚举所有可能的子集，检查其和是否为总和的一半。B.使用哈希表记录所有子集的和，然后检查总和的一半是否在哈希表中。C.将问题转化为子数组和等于特定值的问题，使用动态规划解决。D.基于快速选择算法，尝试找到数组中一半的和，然后检查是否存在这样的子集。3.给定一个包含`n`个整数的数组`nums`，其中`n`是偶数。请将数组分成`n/2`对，使得每对数字的乘积最大。例如，给定nums=[1,4,3,2]，可以分成(1,4)和(2,3)，其乘积分别为4和6，最大乘积为24。以下哪种方法能够高效地找到最大乘积对？A.首先对数组进行排序，然后将最小的数与最大的数配对，次小的数与次大的数配对，以此类推。B.遍历数组，找到最大的数和第二大的数，将它们配对，然后从剩余数组中找到最大的数和第二大的数配对，以此类推。C.使用动态规划，定义`dp[i][j]`表示前`i`个数中分成`j`对的最大乘积和。D.使用贪心算法，每次选择当前最大的两个数进行配对。4.请实现一个算法，找到数组中不重复的数字。即，只出现一次的数字。其他数字均出现两次。假定你能够修改数组，并在原地更新不重复的数字，使得所有重复的数字都移动到数组的末尾，同时保持不重复数字的相对顺序。例如，给定nums=[4,3,2,7,8,2,3,1]，调用算法后，数组可以变为[4,7,8,1,2,2,3,3]。不重复的数字为[4,7,8,1]。以下哪种方法能够满足要求？A.使用哈希表记录每个数字的出现次数，然后遍历哈希表将出现次数为1的数字移动到数组前面。B.对数组进行排序，然后遍历排序后的数组，将连续的相同数字移动到数组末尾，同时记录不重复的数字。C.遍历数组，对于每个元素，使用二分查找在数组中查找其重复元素，找到则将其与当前元素交换到数组末尾，否则保留。最后保留数组前面的元素为不重复数字。D.使用异或运算。首先对所有元素进行异或，得到不重复数字的异或结果。然后找到数组中任意一个与异或结果不同的数字，再通过异或运算将整个数组分成两组，分别异或得到两个不重复的数字。5.给定一个整数数组`nums`，返回数组中和为`target`的所有唯一子数组的个数。例如，给定nums=[2,3,5,7],target=8，满足条件的子数组有[2,3,3],[3,5],[5,3],[7]共4个。以下哪种方法适合解决这个问题？A.暴力枚举所有可能的子数组，计算其和是否等于target。B.使用哈希表记录前缀和，通过前缀和之差查找target，并计算满足条件的子数组数量。C.使用动态规划，定义`dp[i][j]`表示以`nums[i]`结尾，和为`j`的子数组数量。D.使用双指针技术，维护一个滑动窗口，窗口内元素和等于target，并统计满足条件的窗口数量。二、多选题1.在以下哪些情况下，使用哈希表（HashMap）来处理数组中的元素会更高效？A.需要频繁地检查某个元素是否存在于数组中。B.需要统计数组中每个不同元素的出现频率。C.需要按照元素的值对数组进行快速排序。D.需要找到数组中和为特定值的两个元素。2.以下哪些算法或技术可以用于解决“在数组中查找连续的递增或递减子数组（子序列）”的问题？A.单向遍历数组，记录当前递增/递减序列的长度和起始位置。B.使用二分查找在数组中寻找递增/递减序列的边界。C.使用动态规划，定义`dp[i]`表示以`nums[i]`结尾的最长递增/递减子序列的长度。D.将数组排序后，再寻找最长的递增子序列。3.请判断以下关于数组排序的说法哪些是正确的？A.快速排序在最坏情况下的时间复杂度为O(n^2)，但可以通过随机化选择枢轴来优化。B.归并排序的时间复杂度在所有情况下均为O(nlogn)，但它需要额外的内存空间。C.堆排序是一种原地排序算法，其时间复杂度为O(nlogn)。D.插入排序对于近乎有序的数组效率很高，其时间复杂度最好为O(n)。4.在处理包含大量重复元素的数组时，以下哪些策略有助于提高算法的效率？A.使用哈希表记录每个元素的出现次数，然后基于频率进行优化处理。B.在排序后，使用双指针技术来处理配对、查找或划分问题。C.利用异或运算的性质来处理只出现一次的元素相关的问题。D.采用基于快速选择（Quickselect）的算法来寻找中位数或特定位置的元素，而不是完整排序。5.对于一个包含正数和负数的整数数组，以下哪些操作或计算是可以通过数组本身或简单的线性遍历实现的？A.找到数组中和最大的子数组（Kadane算法）。B.找到数组中所有和为0的子数组。C.计算数组中所有元素的前缀和。D.判断数组是否是一个有效的山脉数组（即存在一个峰值，左边严格递增，右边严格递减）。三、判断题1.对于查找数组中是否存在重复元素的问题，使用哈希表的时间复杂度为O(n)，空间复杂度也为O(n)。（）2.在最坏情况下，快速排序的时间复杂度总是比归并排序的时间复杂度高。（）3.假设数组已经排好序，那么任何基于排序的算法（如二分查找）都能达到O(logn)的时间复杂度。（）4.可以使用动态规划解决所有涉及数组的子序列和或计数的问题。（）5.在原地修改数组以满足特定条件（如将所有0移动到数组末尾，所有1移动到数组开头）的问题，通常可以通过一次遍历实现。（）四、编码题（请实现以下算法）1.给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素都出现两次。请找出那个只出现一次的元素。你可以假设数组中只有一个元素出现一次。要求：不使用额外的存储空间，且时间复杂度优于O(nlogn)。2.给定一个非递减的整数数组和一个目标值，找出数组中第一个大于或等于目标值的位置。如果数组中没有这样的元素，返回数组长度。要求：实现二分查找算法。3.给定一个整数数组`nums`和一个正整数`k`，判断是否可以将数组分成`k`个连续的子数组（子数组中的元素在原数组中是连续的），且每个子数组中的元素和都相同。例如，nums=[1,2,3,4,5],k=3，可以分成[1,2],[3,4],[5]三个子数组，每个子数组的和为3。返回true或false。4.给定一个整数数组`nums`，返回数组中第三大的数。如果数组中少于三个不同的数，返回最大的数。例如，给定nums=[1,2,-2147483648,2,3],返回1。给定nums=[1,2,2,5,3,5],返回2。5.给定一个由非负整数组成的非空数组，该数组表示一个柱状图，其中每个元素代表一个柱子的高度。找出两个柱子，使得它们与x轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。你不能倾斜容器。例如，给定height=[1,8,6,2,5,4,8,3,7],返回49。试卷答案一、单选题1.C解析思路：利用异或运算的性质（相同为0，不同为1）和交换律、结合律。首先对所有元素进行异或，得到两个只出现一次元素的异或结果`diff`，该结果的二进制表示中至少有一位是1，表示两个只出现一次的元素在这一位上不同。通过`diff`的任意一位设置一个mask，将原数组分成两组，第一组的元素在该位为1，第二组的元素在该位为0。然后分别对两组进行异或，每组内部元素都出现两次，异或结果为0，最终得到两个只出现一次的元素。该方法满足O(n)时间复杂度和O(1)空间复杂度。2.C解析思路：这是一个典型的子集和问题，可以转化为0-1背包问题。定义`dp[i][j]`为前`i`个元素中是否可以选取若干元素，使得它们的和恰好为`j`。初始状态`dp[0][0]=true`，`dp[0][j>0]=false`。状态转移方程为`dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i-1]]`（如果选取第`i`个元素，则看`dp[i-1][j-nums[i-1]]`是否为真）。最后检查`dp[n][sum/2]`是否为真，其中`sum`是数组总和。动态规划方法可以保证在O(n*sum)的时间复杂度内找到解。其他方法或时间复杂度过高或无法保证唯一子集的计数。3.A解析思路：为了使配对的乘积最大，应将数组排序。排序后，为了使乘积最大，应将最小的数与最大的数配对，次小的数与次大的数配对，以此类推。这样可以确保每一对的乘积尽可能大。例如，排序后为[1,2,3,4]，配对为(1,4)和(2,3)，乘积为4和6，总和为10，是最大的。其他方法可能无法保证得到最大的乘积和。4.B解析思路：可以修改数组，利用排序。首先对数组进行排序。然后遍历排序后的数组，对于当前元素`nums[i]`，如果它与`nums[i-1]`相同，则说明它是重复的，可以将其与数组末尾的元素交换（数组末尾的元素一定是重复的或未被处理的），并将末尾元素索引减一。如果它与`nums[i-1]`不同，则它是第一个不重复的元素，保留在原位置。遍历完成后，数组前面部分是不重复的元素，后面部分是重复的元素。该方法满足原地修改和保持相对顺序的要求。其他方法要么需要额外空间，要么无法保证原地修改或相对顺序。5.B解析思路：使用哈希表记录前缀和是一种有效的方法。定义`prefix_sum[i]`为数组`nums[0..i-1]`的和。对于任意子数组`nums[i..j]`，其和为`prefix_sum[j+1]-prefix_sum[i]`。我们需要找到所有`i`和`j`满足`prefix_sum[j+1]-prefix_sum[i]==target`。可以使用哈希表`memo`记录`prefix_sum`出现的次数，初始化`memo[0]=1`（表示前缀和为0的情况）。遍历`prefix_sum`，对于每个`prefix_sum[k]`，检查`prefix_sum[k]-target`是否在`memo`中，如果在，则说明存在以`i`结尾的子数组满足和为`target`，将`memo[prefix_sum[k]-target]`的值累加到结果中。最后返回结果。该方法可以统计所有满足条件的唯一子数组数量。其他方法要么效率低（如暴力枚举），要么难以处理“唯一”子数组的要求。二、多选题1.A,B解析思路：A.需要频繁检查元素是否存在，哈希表提供O(1)平均时间复杂度的查找。B.需要统计频率，哈希表可以方便地记录和更新元素计数。C.快速排序的平均时间复杂度是O(nlogn)，但排序会打乱元素的原始顺序，可能不满足特定要求。D.寻找和为特定值的两个元素，虽然哈希表可以辅助（记录遍历过的元素），但更优的方法是排序后双指针，或者使用前缀和+哈希表（如单选题第5题解析所述），直接哈希表记录可能需要O(n^2)空间或O(n^2)时间。2.A,C解析思路：A.单向遍历，维护当前递增/递减序列的长度和起始位置，可以在线性时间内找到所有序列。C.动态规划可以定义状态表示最长递增/递减子序列，但通常用于计算长度而非直接找到序列本身。B.二分查找用于在有序数组中查找特定值或范围，不适用于查找连续递增/递减子数组的边界。D.排序会改变元素顺序，无法找到原数组中的连续序列。3.A,B,C,D解析思路：A.快速排序平均O(nlogn)，最坏O(n^2)，随机化枢轴可优化。B.归并排序保证O(nlogn)，需要额外空间。C.堆排序原地排序，时间O(nlogn)。D.插入排序最好O(n)（近乎有序），平均O(n^2)。4.A,B,C解析思路：A.统计频率有助于识别重复模式，进行优化（如判断是否有唯一元素）。B.排序后使用双指针是处理配对、查找、划分等问题的常用高效策略，尤其在重复元素多时。C.异或运算天然适用于处理出现次数为奇数或特定个数的元素问题（如单选题第1题和第4题解析所述）。D.快速选择用于在O(n)平均时间内找到第k小/大元素，虽然效率高，但与大量重复元素处理的核心策略（频率统计、排序双指针）关联性稍弱。5.A,C,D解析思路：A.Kadane算法通过线性遍历找到最大子数组和，时间O(n)。B.找和为0的子数组通常需要哈希表（记录前缀和）或O(n^2)暴力枚举，不能仅通过线性遍历。C.计算前缀和通过一次遍历完成，时间O(n)，空间O(1)或O(n)。D.判断山脉数组可以通过一次遍历，检查严格单调递增后严格单调递减，时间O(n)。E.“有效山脉数组”通常指非空数组，且至少有3个元素，隐含了可以线性判断。三、判断题1.对解析思路：使用哈希表存储元素，遍历数组时检查元素是否已存在于哈希表中。对于每个元素，哈希表查找和插入操作的平均时间复杂度为O(1)，遍历数组的时间复杂度为O(n)，因此总时间复杂度为O(n)，空间复杂度也为O(n)（用于存储哈希表）。2.错解析思路：快速排序和归并排序的平均时间复杂度都是O(nlogn)。但在最坏情况下（例如，数组已排序或几乎排序），快速排序的时间复杂度会退化到O(n^2)，而归并排序的时间复杂度始终为O(nlogn)。因此，不能说快速排序在最坏情况下总是比归并排序的时间复杂度高。3.错解析思路：二分查找算法本身的时间复杂度是O(logn)，但这依赖于数组已经是有序的。如果算法没有利用到数组的有序性（例如，进行了不必要的排序），或者问题的解法本身不适用于二分查找（例如，需要找到所有满足条件的元素），则无法保证达到O(logn)的时间复杂度。例如，在未排序数组中查找特定元素，即使使用二分查找，其前提也是数组有序，否则二分查找会出错。4.错解析思路：动态规划适用于解决具有明确子问题和重叠子问题的优化问题，通常用于计算最大/最小值、计数等。但并非所有子序列和计数问题都适合动态规划。例如，查找和为特定值的子数组，使用哈希表可能是更优的选择；对于某些复杂度高的DP问题，可能存在更高效的非DP解法。因此，不能说动态规划可以解决所有此类问题。5.对解析思路：这类问题通常可以通过一次遍历实现。例如，将所有0向右移动，所有1向左移动，可以维护两个指针，一个指向当前处理的元素，一个指向下一个要填充的位置。遍历过程中，根据当前元素与目标值（这里是0或1）的比较结果，进行元素的交换或移动，可以在线性时间内完成。具体实现可能略有不同，但核心思想是单次遍历即可完成。四、编码题1.解法一：异或运算```javaintsingleNumber(int[]nums){intsingle=0;for(intnum:nums){single^=num;}returnsingle;}```解析思路：利用异或运算的性质：任何数和0异或都是其本身，任何数和自身异或都是0。数组中除了一个元素出现一次，其余都出现两次。因此，将所有元素进行异或，出现两次的元素互相抵消为0，最终结果就是那个只出现一次的元素。该方法满足O(n)时间复杂度和O(1)空间复杂度。2.解法：二分查找```javaintfindFirstGreaterEqual(int[]nums,inttarget){intleft=0,right=nums.length;while(left<right){intmid=left+(right-left)/2;if(nums[mid]>=target){right=mid;//在左半边继续查找更小的满足条件的}else{left=mid+1;//在右半边查找}}returnleft;//left就是第一个大于等于target的元素索引，或数组长度}```解析思路：数组非递减，可以使用二分查找。定义查找区间为`[left,right]`，初始`left=0`,`right=nums.length`。在区间内，计算中间位置`mid`。比较`nums[mid]`和`target`：-如果`nums[mid]>=target`，说明`mid`位置及其左侧可能存在满足条件的元素，因此将`right`缩小到`mid`，继续在左半边查找。-如果`nums[mid]<target`，说明`mid`位置及其左侧的元素都不满足条件，需要将`left`移动到`mid+1`，继续在右半边查找。当`left`和`right`相遇时，`left`的值就是第一个大于等于`target`的元素索引。如果`left`最终等于`nums.length`，说明数组中所有元素都小于`target`，返回`nums.length`。3.解法：动态规划+前缀和```javabooleancanPartitionKSubsets(int[]nums,intk){intsum=0;for(intnum:nums)sum+=num;if(sum%k!=0||nums.length<k)returnfalse;inttarget=sum/k;boolean[]used=newboolean[nums.length];returnbacktrack(nums,target,0,0,0,used,k);}privatebooleanbacktrack(int[]nums,inttarget,intstart,intcurrentSum,intcurrentCount,boolean[]used,intk){if(currentCount==k)returncurrentSum==target;//找到k个子集if(currentSum==target)returnbacktrack(nums,target,0,0,currentCount+1,used,k);//开始找下一个子集for(inti=start;i<nums.length;i++){if(!used[i]&¤tSum+nums[i]<=target){used[i]=true;if(backtrack(nums,target,i+1,currentSum+nums[i],currentCount,used,k))returntrue;used[i]=false;//回溯}}returnfalse;}```解析思路：首先计算数组总和`sum`。如果`sum`不能被`k`整除，或者数组长度小于`k`，则无法划分。否则，计算每个子集的目标和`target=sum/k`。问题转化为：能否找到`k`个子集，每个子集的和为`target`，且包含原数组的所有元素。可以使用回溯算法解决。定义`used`数组记录元素是否已被使用。递归函数`backtrack`尝试构建第`currentCount`个子集，当前和为`currentSum`。对于每个未使用的元素`nums[i]`，如果它没有被使用且加入当前子集后和不超过`target`，则尝试加入。如果加入后能成功构建`k`个子集（即`currentSum==target`），或者能继续构建下一个子集（即`currentCount<k`且`currentSum==0`），则返回true。否则回溯，尝试下一个元素。递归的起始点是`start`，表示从数组的哪个位置开始尝试构建当前子集。4.解法：排序+遍历```javaintthirdMax(int[]nums){Arrays.sort(nums);intdistinctCount=0;intprev=Integer.MIN_VALUE;for(intnum:nums){if(num!=prev){distinctCount++;prev=num;}if(distinctCount==3)returnnum;}returnnums[nums.length-1];//如果少于三个不同数字}```解析思路：首先对数组进行排序。排序后，最大的数在末尾，第三大的数（如果存在）会在倒数第三个位置。遍