腾讯数组面试常见问题及标准答案

腾讯数组面试常见问题及标准答案考试时间：______分钟总分：______分姓名：______一、请编写一个函数，接收一个整数数组`nums`和一个整数`target`，返回数组中和为`target`的第一个连续子数组的起始和结束索引（使用0-based索引）。如果不存在这样的子数组，返回`[-1,-1]`。要求时间复杂度尽可能低。二、给定一个包含`n`个正整数的数组`height`，其中`height[i]`表示第`i`个位置的高度。假设你想要在数组中画`n-1`条垂直线，这些线的高度分别为`height`数组中的值。找出两条线，使得它们与`x`轴共同构成的容器能够容纳最多的水。返回容器可以容纳的最大水量。请给出你的算法思路和关键代码。三、实现一个函数`rotate(nums,k)`，将数组`nums`向右旋转`k`步。例如，`nums=[1,2,3,4,5,6,7]`,`k=3`，旋转后`nums`应该变为`[5,6,7,1,2,3,4]`。要求原地旋转，即不使用额外的数组空间（除了少量用于变量交换的空间）。四、编写一个函数，接收一个非空整数数组`nums`，返回一个新数组，其中每个元素`nums[i]`出现的次数等于`nums[i]`的值。如果`nums[i]`的值大于数组长度，则在该位置后添加足够的`nums[i]`值。如果无法满足条件，返回空数组。例如，`nums=[1,2,3,2,1]`，返回`[1,2,2,1,1,1]`；`nums=[1,1]`，返回空数组。五、假设有一个排好序的数组，但在某个位置上进行了旋转。例如，`nums=[4,5,6,7,0,1,2]`，这是一个`nums=[0,1,2,4,5,6,7]`经过3次旋转得到的数组。请设计一个算法，在`O(logn)`时间复杂度内找到旋转数组的最小值。例如，对于`nums=[4,5,6,7,0,1,2]`，最小值是`0`。六、给定一个包含`n`个整数的数组`nums`，判断该数组是否可以由两个元素组成的子序列交替排列而成。例如，`nums=[1,0,1,0,1]`可以看作是由`[1,0]`交替排列而成，返回`true`。而`nums=[1,2,3,1,2,3]`不能由任何两个元素组成的子序列交替排列而成，返回`false`。七、请编写一个函数，接收一个非递减顺序的整数数组`nums`和一个目标整数`target`，返回`nums`中至少有`k`个连续元素的和等于`target`的最短子数组的长度。如果不存在这样的子数组，返回`-1`。例如，`nums=[1,2,3,4,5],k=3,target=9`，最短子数组是`[4,5]`，长度为`2`，返回`2`。八、有一个长度为`n`的整数数组`nums`，你需要对其进行重新排列，使得`nums[i]<=nums[i+1]`对所有`0<=i<n-k`成立，且`nums[i]>=nums[i+1]`对所有`n-k<=i<n-1`成立。这里`k`是一个给定的整数，`1<=k<=n/2`。请给出一个算法，找到满足条件的最少交换次数。例如，`nums=[9,6,1,3,8]`,`k=2`，可以通过交换`9`和`6`，以及`8`和`3`，得到`[6,9,1,3,8]`，交换次数为`2`。九、编写一个函数，接收一个整数数组`nums`，返回一个布尔值，表示该数组是否包含一个重复的元素。如果存在至少一个元素出现超过一次，则返回`true`；否则，返回`false`。要求不使用额外的存储空间（不能使用哈希表或集合等）。例如，`nums=[1,2,3,1]`返回`true`，`nums=[1,2,3,4]`返回`false`。十、给定一个正整数数组`nums`，返回数组中连续子数组的最大和。例如，`nums=[-2,1,-3,4,-1,2,1,-5,4]`，连续子数组`[4,-1,2,1]`的和最大，为`6`，返回`6`。要求使用动态规划的方法解决。试卷答案一、```pythondeftwoSum(nums,target):left,right=0,len(nums)-1whileleft<right:current_sum=nums[left]+nums[right]ifcurrent_sum==target:return[left,right]elifcurrent_sum<target:left+=1else:right-=1return[-1,-1]```解析：使用双指针法。初始化左指针在数组开头，右指针在数组末尾。计算两指针指向元素之和，与target比较。如果和等于target，返回当前指针索引。如果和小于target，为增加和，左指针右移。如果和大于target，为减少和，右指针左移。如果遍历完仍未找到，返回`[-1,-1]`。时间复杂度O(n)，空间复杂度O(1)。二、思路：要使水槽容量最大，应尽量选择较高且宽度较大的区间。可以使用双指针法，初始指针分别指向数组开头和末尾。移动较矮的指针，每次移动时，计算当前指针之间的宽度乘以当前两指针中较矮的高度，与最大容量比较并更新。移动过程中，记录移动指针之前另一个指针的位置，以便计算宽度。当两个指针相遇时停止。关键代码：```pythondefmaxArea(height):left,right=0,len(height)-1max_water=0whileleft<right:current_height=min(height[left],height[right])current_width=right-leftmax_water=max(max_water,current_height*current_width)ifheight[left]<height[right]:left+=1else:right-=1returnmax_water```解析：双指针从两端向中间移动，每次移动较矮的指针以尝试找到更高的边界，从而可能获得更大的水量。计算当前双指针之间的高度（取两者最小值）乘以宽度，更新最大水量。时间复杂度O(n)，空间复杂度O(1)。三、```pythondefrotate(nums,k):n=len(nums)k=k%n#处理k大于n的情况ifk==0:return#方法一：先整体反转，再分别反转前k个和后n-k个#反转整个数组nums.reverse()#反转前k个元素nums[:k]=reversed(nums[:k])#反转后n-k个元素nums[k:]=reversed(nums[k:])#方法二：使用额外数组（不满足原地要求，略）```解析：将数组分为两部分，前`n-k`个元素和后`k`个元素。将后`k`个元素移动到数组开头，前`n-k`个元素移动到数组末尾。可以通过三次反转实现：首先反转整个数组，然后反转前`k`个元素，最后反转后`n-k`个元素。这样可以将后`k`个元素移动到前面，前`n-k`个元素移动到后面，达到旋转效果。时间复杂度O(n)，空间复杂度O(1)（使用反转方法）。四、```pythondeffindRepeatNumber(nums):count={}result=[]fornuminnums:ifnumincount:count[num]+=1else:count[num]=1fornum,cntincount.items():ifcnt>1:result.extend([num]*cnt)elifcnt>len(result):result.extend([num]*cnt)iflen(result)==len(nums):returnresultelse:return[]```解析：首先遍历数组，统计每个数字出现的次数。然后根据统计结果构建新数组。对于出现次数大于1的数字，将其重复`cnt`次加入结果。对于出现次数等于当前结果长度`cnt`的数字，也将其加入结果（满足`nums[i]`的值大于数组长度时，在该位置后添加）。如果最终结果长度与原数组长度相同，返回结果，否则返回空数组。时间复杂度O(n)，空间复杂度O(n)。五、```pythondeffindMin(nums):left,right=0,len(nums)-1whileleft<right:mid=left+(right-left)//2ifnums[mid]>nums[right]:#最小值在右半部分left=mid+1else:#最小值在左半部分或mid处ifnums[mid]<nums[right]:right=midelse:right-=1returnnums[left]```解析：利用旋转数组的特性。在每一步，比较中间元素与右端元素。如果中间元素大于右端元素，说明旋转点（最小值）在右半部分，因此将左指针移动到`mid+1`。否则，最小值在左半部分或就是`mid`本身。需要特别处理中间元素等于右端元素的情况，此时无法确定最小值在哪边，只能将右指针左移一位继续查找。时间复杂度O(logn)，空间复杂度O(1)。六、```pythondefhasAlternatingSubsequences(nums):n=len(nums)ifn<2:returnFalse#寻找第一个重复的元素对(a,b)a=nums[0]b=Noneforiinrange(1,n):ifnums[i]==a:continueifbisNone:b=nums[i]else:ifnums[i]!=b:returnFalse#重置为新的重复对a,b=b,nums[i]returnTrue```解析：遍历数组，寻找第一个重复的元素对`(a,b)`。找到后，继续遍历，检查后续元素是否按照`a,b,a,b,...`的顺序出现。如果遇到不满足顺序的元素，返回`false`。如果遍历结束都能满足顺序，返回`true`。核心在于找到并验证重复的元素对是否交替出现。时间复杂度O(n)，空间复杂度O(1)。七、```pythondefshortestSubarray(nums,k,min_len):n=len(nums)#构建前缀和数组prefix_sum=[0]*(n+1)foriinrange(n):prefix_sum[i+1]=prefix_sum[i]+nums[i]min_len=float('inf')foriinrange(n):forjinrange(i+min_len,n+1):ifprefix_sum[j]-prefix_sum[i]>=k:min_len=min(min_len,j-i)break#找到满足条件的j即可，可以尝试更小的ireturnmin_lenifmin_len!=float('inf')else-1```解析：使用前缀和数组`prefix_sum`，其中`prefix_sum[i]`表示`nums[0..i-1]`的和。问题转化为寻找`i,j`使得`prefix_sum[j]-prefix_sum[i]>=k`且`j-i`最小。可以固定`i`，然后使用两层循环找到最小的`j`满足条件。为了优化，内层循环可以尝试从`i+min_len`开始，因为更小的`j-i`已经被找到。时间复杂度O(n^2)，对于更优解可以使用双指针或单调队列优化到O(n)，但此处按双层循环实现。空间复杂度O(n)。八、思路：可以将问题转化为在`n-k`个“必须严格递减”的位置上，放置`n-k`个`nums`中的较大值，在`k`个“可以递增”的位置上放置较小的值。关键在于找到这些位置的“可接受”的数值范围。对于每个位置，根据其左右约束，可以确定其可接受的最小值和最大值。然后使用贪心算法，尽量用较大的数填充“必须递减”的位置，用较小的数填充“可以递增”的位置，同时保证数值的唯一性。最后统计实际交换次数。这类似于区间调度问题或差分约束系统。关键代码（使用差分思想简化）：```pythondefminSwaps(nums,k):n=len(nums)#构建差分数组diff=[0]*(n+1)foriinrange(n-k,n):diff[i+1]-=1ifi<n-1:diff[i+1]+=1#计算前缀和得到移动数组move=0foriinrange(1,n+1):move+=diff[i]diff[i]=move#构建目标排列的移动序列target_moves=[0]*nforiinrange(n):ifi<n-k:target_moves[i]=-1else:target_moves[i]=1#计算最小交换次数visited=[False]*nswaps=0foriinrange(n):ifmove[i]==0orvisited[i]:continuecycle_size=0x=iwhilenotvisited[x]:visited[x]=Truex=(x+target_moves[x])%ncycle_size+=1ifcycle_size>0:swaps+=(cycle_size-1)returnswaps```解析：使用差分数组`diff`来表示“必须向右移动”的位置。计算差分前缀和得到实际的移动序列`move`。`target_moves`表示理想情况下每个位置应该向左（`-1`）还是向右（`1`）移动。然后遍历每个位置，如果它需要移动（`move[i]!=0`且未被访问），则找到整个移动循环的长度，交换次数为循环长度减一。时间复杂度O(n)，空间复杂度O(n)。九、```pythondefcontainsDuplicate(nums):seen=set()fornuminnums:ifnuminseen:returnTrueseen.add(num)returnFalse```解析：使用哈希集合`seen`来记录已经遍历过的数字。对于每个数字，检查是否已经在`seen`中。如果在，说明存在重复，返回`true`。如果不在，将其加入`seen`。遍历结束后如果没有找到重复，返回`false`。时间复杂度O(n)，空间复杂度O(n)。```python#不使用额外空间的解法（基于排序）defcontainsDuplicate(nums):nums.sort()for