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[0] 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.

int findMaxLength(vector<int>& nums) {
const int nums_size = nums.size();
const int firsts_size = 2 * nums_size + 2;
//This will fall out if(nums_size < 2) return 0;
int maxLength = 0;
// This array holds the first i where we find a given Key
// The Key is the imbalance. Negative is how many more 0s, Positive is how many more 1s.
// This is normalized to run from 0 to 2 * nums.size() rather than from -nums.size() to nums.size().
// Since we are starting at nums[0], any time Key is 0 the subArray from 0 to i is balanced,
// and it must be the longest so far because any partial, or any so-far, must be shorter.
// But that is also lowIndex[0] so no need to special case it
// Index of firstTimeWeSaw is nums_size + actual i where it happened
// Before we add nums[0] is position -1
// cout << "nums.size() = " << nums_size << " map firsts size = " << firsts_size << endl;
int *firstTimeWeSaw = new int[firsts_size];
for(int i = 0; i < firsts_size; i++)
firstTimeWeSaw[i] = -2;
int i = -1;
int tally = 0; // KJer stores this in nums[i-1]
int diff = 2 * tally - i; // 1 means balanced because of how we count from -1
int key = diff + nums_size;
firstTimeWeSaw[key] = i; // We are balanced before we start
// cout << "Before nums[0] tally = " << tally << " calculated imbalance (1 + 1s - 0s) is " << diff << " key = " << key << endl;
int length;
for (i = 0; i < nums_size; i++)
{
//number of 1s in nums[] from 0 to i: tally
//number of 0s or 1s in nums[] from 0 to i: i
tally += nums[i];
// diff = 2 * tally - i; // 1 means balanced because of how we count from -1
// cout << "i = "<< i << " tally (total 1s) including nums[" << i << "] (" << nums[i] << ") = "
// << tally << " imbalance (1 + 1s - 0s) = " << diff << endl;
key = 2 * tally - i + nums_size;
// Have we seen this key before?
if(firstTimeWeSaw[key] == -2)
{
// cout << " This is the first time we saw diff " << diff << " (key = " << key << ")\n";
// This is the first time we saw the key
firstTimeWeSaw[key] = i;
}
else
{
// This key looks familiar
// How long since we last saw it?
length = i - firstTimeWeSaw[key];
// cout << " First saw diff " << diff << " was when i was " << firstTimeWeSaw[key] << " length = " << length << endl;
if(length > maxLength)
{
// cout << " New longest length = " << length << " > longest was " << maxLength << endl;
maxLength = length;
}
}
}
return maxLength;
}