# Prefix Sum Solution O(n^2) time Complexity

• 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;
}
}

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