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.
nightcatzhou
@nightcatzhou
Posts made by nightcatzhou

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

straightforward Java solution
I am not clever, it's quite difficult for me the handle the indexing. So I give out my straightforward solution. Do down and then go up. End when we iterate the total String
public String convert(String s, int nRows) { if(nRows == 1){ return s; } char[] c = s.toCharArray(); StringBuffer[] sb = new StringBuffer[nRows]; for (int i = 0; i < sb.length; i++) { sb[i] = new StringBuffer(); } boolean down = true; int index = 0; for(char c1:s.toCharArray()){ sb[index].append(c1); if(down){ index++; }else{ index; } if(index == nRows){ index = index 2; down = !down; }else if(index == 1){ index = index + 2; down = !down; } } for (int idx = 1; idx < sb.length; idx++){ sb[0].append(sb[idx]); } return sb[0].toString(); }

Question may asked in the interview
We know that mainly we have two solution for this question. One is utilize the PriorityQueue while the other is using the Divide and conquer with the same idea of merged sort. And the RT is O(n*logk).
So in your opinion, which one is better? What factor you will be considered when you have to choose one of them? 
RE: Java solution and explanation using invariants
That's awesome. I like you solution. Just one more thing may make the logic better.
At the return statement, using the following code is enough.
return nums[left]<nums[right]?right:left;
For we hold the state of nums[left]>nums[left1] && nums[right]>nums[right+1]
and the loop will end when left and right sit near to each other. Then we can say the bigger one between nums[left] and nums[right] will be the solution. 
easily understand code, you see and know
public boolean isOneEditDistance(String s, String t) { if(Math.abs(s.length()t.length())>1){ return false; } int edit = 0; int len1 = s.length(); int len2 = t.length(); int i = 0; int j = 0; while(i<len1 && j<len2){ if(s.charAt(i)!=t.charAt(j)){ edit++; if(len1 != len2){ if(len1>len2){ i++; }else{ j++; } }else{ i++; j++; } }else{ i++; j++; } if(edit>1){ return false; } } if(edit == 0 && len1!=len2){ return true; } return edit ==1; }

Should think about multithread solution
The followup is easy, but if I am the interviewer, I may ask how will you consider the multithread solution.
One more thing is that, when it is in a distributed environment?
Fortunately, I am still seeking a job and it seems that I will never find a job. So I won't be the interviewer. Good luck man. 
I think it's easy to understand
public class Solution { public boolean isInterleave(String s1, String s2, String s3) { if(s1 == null  s2 == null  s3 == null) return false; if(s1.length() + s2.length() != s3.length()) return false; Node root = new Node(0,0,0); Set<Node> cur = new HashSet<>(Arrays.asList(root)); int i = 0; for(;i<s3.length();i++){ Set<Node> temp = new HashSet<>(); for(Node n:cur){ temp.addAll(n.grow(s1, s2, s3)); } cur = temp; if(cur.size() == 0) return false; } return true; } } class Node{ int i = 1; int j = 1; int k = 1; Node(int i,int j,int k){ this.i = i; this.j = j; this.k = k; //System.out.println(this); } List<Node> grow(String s1,String s2,String s3){ List<Node> list = new ArrayList<>(); if(i < s1.length() && s3.charAt(k) == s1.charAt(i)){ list.add(new Node(i+1,j,k+1)); } if(j<s2.length() && s3.charAt(k) == s2.charAt(j)){ list.add(new Node(i,j+1,k+1)); } return list; } @Override public int hashCode(){ Integer value = new Integer(i + j*10 + k*100); return value.hashCode(); } @Override public boolean equals(Object obj){ if(obj == null) return false; if(!(obj instanceof Node)){ return false; } Node n = (Node)obj; if(this.i != n.i  this.j != n.j  this.k != n.k) return false; return true; } }

RE: AC Java solution without extra space
Just let you that, modify the parameter is a very very bad practice. An experienced programmer won't do that.