## Problem Info

Hi! I was doing this problem on Leetcode to practice prefix sums and my code passes 93/94 testcases (the last unpassed testcase is TLE). Could someone please help me check where I could improve my code? Thank you so much!

## My Work

``````class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
// create a prefix sum array
int[] prefixSum = new int[nums.length + 1];
prefixSum = 0; prefixSum = nums;
for (int i = 1; i < nums.length ; i++) {prefixSum[i + 1] = prefixSum[i] + nums[i];}

int sum = 0;
int len = 2; // initial length of sub array or partial sum
while (len <= nums.length)
{

for (int i = 0; i + len<= nums.length; i++)
{
sum = 0;
int addition = prefixSum[i + len] - prefixSum[i]; // calculate the partial sum
if (sum%k == 0) return true; // if sum is a multiple of k, return true
}

len ++; // obtain the next length number
}
return false; // if the code reaches here, then there is no continuous subarray sum that is a multiple of k
}
}
``````

Here’s the last test case that the code didn’t pass:

Is there any way for me to optimize the code to get AC or just to improve it in general? Thank you so much!

I think the problem is with the complexity of your code. Right now it’s around O(N^2), where N can go up to 10^5. In other words, your algorithm is wrong in itself.

Here’s a hint: What can you say about the prefix sums of the beginning and end of a subarray that does sum up to a multiple of k?

Oh, sliding window.
Thanks!