Given an array of integers (positive and negative). find the sub-array with sum closest to a number T.
I was asked to answer M queries and in each query we are give number T.
I came up with a solution of nlogn + m*n*logn but interviewer was not satisfied and wanted me to come up with nlogn + m*n solution.

Can anyone suggest me what can be optimised solution for this.
My solution involves storing prefix sum in set and finding prefix[i]-T value in set.