Prefix Sum and Sliding Window 02

Given an array of positive and negative numbers. Find if there is a subarray(of at-least one) with 0 sum.

Problem link :- click here

Code

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

// 	CHECK IF THERE IS A SUBARRAY WITH 0 SUM

public class Prefix_sum__Sliding_window_02
{
	
	static boolean containsSubarrayWith0sum(int[] arr, int n)
	{
		//	Calculating prefix sum array(psa)
		int[] psa = new int[n];
				
		psa[0] = arr[0];
		for(int i=1; i<n; i++)
			psa[i] = psa[i-1] + arr[i];
		
		
		/*
		 	LOGIC: -	
		 		*) In `psa` we have sum of elements starting from index 0 to that index.
		 		*) If any element in `psa` is == 0 then there is a sub-array starting from index 0 
		 			having sum of elements = 0
		 		*) How to verify sub-arrays which doesn't start with index 0?
		 		*) Consider a example :	arr = {3, 4, -4, 7, 9}
		 								psa = {3, 7, 3, 10, 19}
		 			If we have a sub-array with sum 0, then the `psa` will have some elements repeated.
		 			In this example psa[0] == psa[2]
		 			 			      psa[0]  =  psa[1] + arr[2]
		 			 			      psa[0]  =  psa[0] + arr[1] + arr[2]
		 			which means arr[1] + arr[2] == 0.
		 			
		 		*) So if we get any element in the `psa` twice, then there is a sub-array with sum 0
		 */
		
		for(int i=0; i<n; i++)
		{
			for(int j=i+1; j<n; j++)
			{
				if(psa[i] == psa[j])
					return true;
			}
		}
		
		return false;
	}
	
	static boolean containsSubarrayWith0sum2(int[] arr, int n)
	{
		Set<Integer> hs = new HashSet<Integer>();
		
		/*
		 	Here instead of storing the sum in `psa` we will store it in a hash set 
		 	so it will be easy to check if the sum is already stored in the hash set.
		 */
		
		Integer sum = 0;
		for(int i=0; i<n; i++)
		{
			sum += arr[i];
			
			if( arr[i]==0 || sum==0 || hs.contains(sum) )
				return true;
			
			hs.add(sum);
		}
		
		return false;
	}

	public static void main(String[] args)
	{
		Scanner s = new Scanner(System.in);
		
		//	Taking size of array and array as input from the user
		System.out.print("Enter the size of the array : ");
		int n = s.nextInt();
		
		int[] arr = new int[n];
		System.out.println("Enter the array elements : ");
		for(int i=0; i<n; i++)
			arr[i] = s.nextInt();
		
		
		//	Calculating prefix sum array(psa)
		int[] psa = new int[n];
		
		psa[0] = arr[0];
		for(int i=1; i<n; i++)
			psa[i] = psa[i-1] + arr[i];
		
		boolean ans = containsSubarrayWith0sum(arr, n);		//Time complexity: O(n^2)
		boolean ans2 = containsSubarrayWith0sum2(arr, n);	//Time complexity: O(n)
		
		if(ans)
			System.out.println("\n\nYES by first method");
		if(ans2)
			System.out.println("\nYES by second method");
	}

}