身為開發人員,我們經常被要求找出陣列中是否存在總和為 0 的子陣列。這可以透過使用前綴和的概念來完成。我們將追蹤到目前為止看到的子數組元素的總和並將其儲存在雜湊圖中。如果之前看到了sum,則表示具有該sum的子數組存在且sum為0。我們將使用迄今為止看到的元素總和不斷更新雜湊圖。這樣我們就可以判斷數組中是否存在sum為0的子數組。
將變數「sum」初始化為 0,並將「hash_map」物件初始化為將總和值儲存為鍵,將其索引儲存為值。
循環遍歷給定數組,對於每個元素 -
#將目前元素加入到總和中。
如果目前總和為 0 或已存在於 hash_map 中,則傳回 true,因為存在總和為 0 的子陣列。
否則,將總和值及其索引插入 hash_map 中。
如果循環完成,則傳回 false,因為不存在總和為 0 的子陣列。
hash_map 有助於追蹤累積和並確定是否存在重複和。
如果找到重複和,則表示這兩個和之間存在一個和為 0 的子陣列。
此方法的時間複雜度為 O(n),其中 n 是給定陣列中的元素數量。
這是一個完整的 JavaScript 程式範例,用於尋找是否存在總和為 0 的子數組 -
function hasZeroSum(arr) { let sum = 0; let set = new Set(); for (let i = 0; i < arr.length; i++) { sum += arr[i]; if (set.has(sum)) return true; set.add(sum); } return false; } const arr = [4, 2, -3, 1, 6]; console.log(hasZeroSum(arr));
函數hasZeroSum採用陣列arr作為其參數。
我們初始化兩個變數sum和set。sum變數用於追蹤子數組中元素的當前總和,set用於儲存先前看到的總和。
李>然後我們使用for迴圈來迭代數組的元素。
在每次迭代中,我們將目前元素新增到sum中,並檢查set是否已包含sum 的值。
#如果sum的值已經在集合中,表示從第一次出現該sum開始到目前元素結束的子數組總和為0,因此我們返回true。
#如果sum的值不在集合#中,我們將其加入集合。
如果我們迭代了整個數組並且沒有傳回true,則表示不存在總和為 0 的子數組,因此我們傳回false。
最後,我們使用範例陣列測試函數並將結果記錄到控制台。
以上是JavaScript 程式會找出是否存在總和為 0 的子數組的詳細內容。更多資訊請關注PHP中文網其他相關文章!