JavaScript program to find if there is a subarray that sums to 0

As developers, we are often asked to find if there is a subarray in an array that sums to 0. This can be done by using the concept of prefix sum. We will keep track of the sum of subarray elements seen so far and store it in a hashmap. If sum was seen before, then a subarray with that sum exists and sum is 0. We will continuously update the hashmap with the sum of the elements we have seen so far. In this way, we can determine whether there is a subarray with a sum of 0 in the array.

method

• Initialize the variable "sum" to 0, and initialize the "hash_map" object to store the sum value as the key and its index as the value.

• Loop through the given array, for each element -

• Add the current element to the sum.

• Returns true if the current sum is 0 or already exists in hash_map, because there is a subarray with a sum of 0.

• Otherwise, insert the sum value and its index into the hash_map.

• If the loop completes, return false because there is no subarray that sums to 0.

• hash_map helps track cumulative sums and determine if there are duplicate sums.

• If a duplicate sum is found, it means that there is a subarray between the two sums with a sum of 0.

• The time complexity of this method is O(n), where n is the number of elements in the given array.

Example

This is a complete JavaScript program example to find if there is a subarray that sums to 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));

illustrate

• Function hasZeroSum takes an array arr as its parameter.

• We initialize two variables sum and set. The sum variable is used to track the current sum of the elements in the subarray, and the set is used to store the previously seen sum.

  李>

• Then we use a for loop to iterate over the elements of the array.

• On each iteration, we add the current element to sum and check if set already contains the value of sum.

• If the value of sum is already in the collection, means that the sum of the subarrays from the first occurrence of the sum to the end of the current element is 0, so we return true.

• If the value of sum is not in the set, we add it to the set.

• If we iterate over the entire array and don't return true, it means there is no subarray that sums to 0, so we return false.

• Finally, we test the function using the sample array and log the results to the console.

The above is the detailed content of JavaScript program to find if there is a subarray that sums to 0. For more information, please follow other related articles on the PHP Chinese website!