贵州营销型网站,番禺定制型网站建设,电子邮箱号大全免费,微信营销app给定一个放有字母和数字的数组#xff0c;找到最长的子数组#xff0c;且包含的字母和数字的个数相同。
返回该子数组#xff0c;若存在多个最长子数组#xff0c;返回左端点下标值最小的子数组。若不存在这样的数组#xff0c;返回一个空数组。
示例 1:
输入: […给定一个放有字母和数字的数组找到最长的子数组且包含的字母和数字的个数相同。
返回该子数组若存在多个最长子数组返回左端点下标值最小的子数组。若不存在这样的数组返回一个空数组。
示例 1:
输入: [A,1,B,C,D,2,3,4,E,5,F,G,6,7,H,I,J,K,L,M]输出: [A,1,B,C,D,2,3,4,E,5,F,G,6,7]示例 2:
输入: [A,A]输出: []提示
array.length 10000
记录出错’ for i in array: if 0i9: nums.append(1) else: nums.append(-1) 我就是这样判断是不是数字的这个bug改了30多分钟真离谱这样只能看到1-9的数字一旦超过9就会出错--
--------------------------------------------------------------------------------------------------------------------------------- 思路
将数字变成1字母变成-1题目就变成了给你一个nums[1,-1,1,1,1,1,-1,-1.....],然后让你求最长等于0的子数组子数组一定是连续的这个时候就可以使用前缀和 根据前缀和公式只要presum出现了两次相同,例如 pre[i]pre[j],则说明nums[i1]到nums[j]的和为0这一点可以很直观的看出来不清楚的可以自己在草稿纸上面画一画 代码如下
class Solution(object):def findLongestSubarray(self, array):nums[]for i in array:if Aiz:nums.append(1)else:nums.append(-1)count0presum0dict{0:-1}right0left0for i in range(len(nums)):presumnums[i]if presum in dict:if i-dict[presum]count:counti-dict[presum]rightileftdict[presum]1else:dict[presum]iif count0:return []return (array[left:right1])#左闭右开所以要right1具体的实现步骤如下 遍历输入的数组 array将每个元素转换为数字字符时标记为 1否则标记为 -1将这些标记存储在列表 nums 中。 初始化变量 ans 为 0表示最长子数组的长度presum 表示当前的前缀和pre 是一个字典用于存储前缀和及其对应的索引right 和 left 分别表示最长子数组的右边界和左边界。 遍历 nums 列表计算当前的前缀和 presum。如果 presum 已经在字典 pre 中出现过则计算当前索引与之前出现的索引的差值即当前子数组的长度。如果当前子数组长度大于 ans则更新 ans、right 和 left。 如果 ans 仍然为 0则表示没有找到满足条件的子数组直接返回空列表否则返回数组 array 中从 left 到 right 的子数组。
总体来说这段代码的作用是找到数组中包含相同数量数字字符和非数字字符的最长子数组并返回该子数组。
