I think we can use presum and treemap.
When we compute the presum for the input array, the presum will be represented by array B.
Then we begin to iterator the array B,
for(int k:B),
the target we are looking for is t  k, then we will check the ceil or the floor value for t  k in the treemap. With the information, we know what's the close value of the sum of a sub array ending with a index i
we put the presume to the treemap.
we continue to iterator B, when we finished the iterator, we compute all the possible,
and keep the closest one.
Now we get the solution.
N
nightcatzhou
@nightcatzhou
60
Reputation
48
Posts
343
Profile views
1
Followers
0
Following
Posts made by nightcatzhou

RE: How to find the subarray that has sum closest to zero or a certain value t in O(nlogn)