Great, thanks! You had me scratching my head for a while at 2.2 when you did not explicitly say U(j) = j - S(j) (because all the elements that are 0 means all the elements all together, except those that are 1.)
I didn't speed up the O(n) of your solution, but I tightened up, In particular there is no need to check for the special case nums,size() < 2, because it will fall out. Also there is no need to treat the array from nums to nums[i] as special, so we can save a conditional. I put a few repeated expressions in const int or int. Especially the size() method on an array may be implemented as a function call.
I don't understand why you are storing the tally (key, imbalance) at each position given that this is single pass, so I store it as scalar variable.
For style I prefer a for loop to a while(true) with a break, and I named some things more explicitly. All together I might be running in half the time as your optimized array solution.