Given an array of N non-negative integers, and a number K, we need to find two non-overlapping contiguous subarrays that have a total sum of K. Our algorithm is supposed to find the minimum total length of the two subarrays that have total sum K.
Also, after I checked the biggest test cases that we got, N doesn't go above $10^4$ and K doesn't go above $10^6$ (but specific subarrays can have a sum way larger than that)
The algorithm implementation (using C++), must have a time complexity of at most
O(logN * N^2).
The only idea I've had that is better than
O(n^3) is to find all possible contiguous subarrays and their sum (
O(N^2) using a prefix sum array), then sort them by sum (
O(logN * N^2)), and for each subarray I do a binary search to find the subarray that has the remaining sum (which is K - (sum of first subarray)).
While this idea has better time complexity than
O(n^3), its space complexity is pretty bad, because I have to save three arrays of size
N(N+1)/2, and the C++ program ends up using 1-2 GB of RAM for large N (>1000).
So my question is: Is there any way to solve the problem efficiently, without the need of the longer arrays?? Or is there any other way I can implement the idea above with C++ so that I don't use up so much memory?