Задачка от Яндекса; Longest subarayy with equal count of 0 and 1

[betazold]

Дан массив длины n из нулей и единиц. Найдите в нём подмассив макисмальной длины, в котором количество единиц равно количеству нулей. Ограничения: O(n) по времени и O(n) по дополнительной памяти.

 
function getLongest(s) {
    var begin = 0,
        finish = 0,
        len = 0,
        b = {},
        sum = 0,
        i,
        n = s.length;
        prefix,
        padding = '',
        cursor;
 
    for (i = -n; i < n; i++) {
        b[i] = null;
    }
    b[0] = -1;
 
    for (i = 0; i < n; i++) {
        sum += (s[i] == 1 ? 1 : -1);
        if (b[sum] == null) {
            b[sum] = i;  
            console.log('for sum = ' + sum + ' index = ' + i);  
        } else {
            console.log('for sum = ' + sum + ' at index = ' + i + ' b = ' + b[sum]);  
            if (len < i - b[sum]) {
                begin = b[sum] + 1;
                finish = i;
                len = i - b[sum];
                console.log('begin = ' + begin + ' finish = ' + finish + ' len = ' + len);
            }  
        }
    }
 
    if (begin === finish) {
        console.log('No subarray');
        return;
    }
 
    prefix = '['+begin+':'+finish+'] = ';
 
    for (i = 0; i < prefix.length + s.length; i++) {
        cursor = i - prefix.length;
        padding += (cursor === begin || cursor === finish) ? '^' : ' ';
    }
 
    console.log(prefix + s);
    console.log(padding)
    console.log(padding.substr(0, prefix.length + begin) + s.substr(begin, finish - begin + 1));
}
 
(function(tests) {
    var i, j, s, len;
    for (i = 0; i < tests; i++) {
        len = Math.round(Math.random() * 10) + 1;
        s = '';
        for (j = 0; j < len; j++) {
            s += Math.round(Math.random());
        }
        console.log(s);
        getLongest(s);
    }
})(3);
 
 

@темы: JavaScript, PHP, Algorithms