Prefix Sum Solution O(n^2) time Complexity


  • 0
    C

    Using prefix sum, Time complexity is O(n^2), if there is any solution can optimize solution, feel free to discuss with me, Thanks

    public class Solution {
        public boolean checkSubarraySum(int[] nums, int k) {
            
            // if there are two continuous zero 
            // k*0 = 0 it means meet the requirements 
            for(int i = 0; i + 1 < nums.length; ++i){
                if(nums[i] == 0 && nums[i + 1] == 0)    
                    return true; 
            }
            
            // k==0 it means 0*k==0 except the previous situation, it will not meet the requirements at all
            if(k==0) return false;
            
            int[] sums = new int[nums.length+1];
            
            //caculate the prefixSum
            // for example  nums = [1,2,3,4,5] prefixSum array's length should be +1
            //         prefixSum = [0,1,3,6,10,15]
            // 
            //         sum[i,j] = prefix[j+1]-prefix[i]
            
            for(int i=0;i<nums.length;i++){
                sums[i+1] = sums[i] + nums[i];
                // System.out.println(sums[i+1]);
            }
            
            for(int i=0;i<sums.length;i++){
                for(int j=i+1;j<sums.length;j++){
                    //deal with the special condition, for example, nums = [1], k=1
                    if(j==1) continue;
                    if((sums[j]-sums[i])%k==0){
                        return true;
                    }
                }
            }
            
            return false;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.