Re: [闲聊] 每日leetcode

楼主: HGK (HGK)   2024-03-17 11:19:18
程式码解释:
初始化
n:储存输入向量 nums 的大小。
mp:建立一个非排序哈希表 mp,用来储存到目前为止遇到的前缀和 (prefix sum) 以及
它们首次出现的索引位置。
prefix:初始化整数变量 prefix 为 0,用于を追踪当前的前缀和 (迄今遇到的 0 的数
量减去 1 的数量)。
ans:初始化整数变量 ans 为 0,用于储存到目前为止找到的包含相同数量 0 和 1 的连
续子阵列的最大长度。
mp[0] = -1:预先将哈希表填入一个键值对,键为 0 (空子阵列的前缀和),值为 -1 (表
示不存在先前的子阵列)。
迭代处理阵列
程式码使用 for 循环迭代遍历 nums 向量。
对于每个元素 nums[i]:
基于当前元素更新 prefix:
如果 nums[i] 是 0,则将 prefix 减 1 (又遇到一个 0)。
如果 nums[i] 是 1,则将 prefix 加 1 (又遇到一个 1)。
检查当前的 prefix 是否存在于哈希表 mp 中:
如果 mp.find(prefix) != mp.end(),表示当前前缀和之前曾被遇到过。这意味着在当前
元素之前存在一个子阵列,该子阵列具有与当前子阵列 (截至目前)相同的 0 和 1 的数
量差。
如果当前子阵列的长度 (即 i + 1 - 在哈希表中找到相同 prefix 的索引位置) 大于当
前的 ans,则更新 ans (最大长度)。
如果 prefix 不存在于哈希表中 (else ):
将当前 prefix 作为键添加到哈希表 mp 中 ( mp[prefix] = i ),并将值设为该前缀和
首次出现的索引位置。 这样做对于追踪具有相同 0 和 1 个数差的潜在子阵列至关重要

传回结果
迭代完整个阵列后,ans 变量将会存储找到的包含相同数量 0 和 1 的子阵列的最大长度
。 函式返回此值。
重点
程式码有效地使用哈希表来跟踪前缀和及其对应的索引。
它利用了这样一个事实:具有相同数量 0 和 1 的子阵列将具有前缀和 0。
时间复杂度为 O(n),由于只需迭代一次阵列。
空间复杂度为 O(n),因为哈希表最多可以存储 n 个独特的 prefix sum。
这个实作有效地解决了这个问题,并且与先前回复中解释的最佳实践保持一致。
作者: oin1104 (是oin的说)   2023-03-17 11:19:00
gpt

Links booklink

Contact Us: admin [ a t ] ucptt.com