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