2023JavaScript 程序查找是否存在总和为 0 的子数组

作为开发人员，我们经常被要求查找数组中是否存在总和为 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。

• 最后，我们使用示例数组测试该函数并将结果记录到控制台。