平衡隊(duì)伍拼多多技術(shù)崗 8月2號筆試 第一題題目內(nèi)容某體育俱樂部的nnn名隊(duì)員排成一列每名隊(duì)員的類型用字符串中的字符表示‘AAA’或’BBB’。教練想要選出一個(gè)連續(xù)的區(qū)間組成隊(duì)伍。若區(qū)間內(nèi) ‘AAA’ 類隊(duì)員數(shù)與 ‘BBB’ 類隊(duì)員數(shù)相等則稱該隊(duì)伍為“平衡隊(duì)伍”。請找出平衡隊(duì)伍的最大人數(shù)。輸入描述第111行一個(gè)整數(shù)nnn(1≤n≤2×105)(1 \le n \le 2\times10^5)(1≤n≤2×105)第222行一個(gè)長度為nnn的字符串sss僅包含字符 ‘AAA’ 和 ‘BBB’輸出描述一個(gè)整數(shù)表示平衡隊(duì)伍的最大人數(shù)。若不存在平衡隊(duì)伍輸出000。樣例1輸入4 ABAB輸出4說明整個(gè)字符串有222個(gè) ‘AAA’ 和222個(gè) ‘BBB’滿足平衡條件最大長度為444。樣例2輸入3 AAA輸出0說明無法選出平衡隊(duì)伍輸出000。樣例3輸入5 AAABB輸出4說明“AABBAABBAABB” 子串第222至555位有222個(gè) ‘AAA’ 和222個(gè) ‘BBB’長度為444是最大的平衡隊(duì)伍。題解和思路思路實(shí)現(xiàn)思路前綴和可以將A看作-1B看作1,從前往后進(jìn)行累加。利用前綴和特性可以得出當(dāng)prefix[i] prefix[j]時(shí)說明[i1, j]中1的數(shù)量和-1數(shù)量相同就是題目所描述的均衡情況。為了求出盡可能長度當(dāng)前位置 i 前綴和sum情況下肯定是選取盡量靠前的前綴和也為sum的位置所以只需要使用哈希表記錄各個(gè)前綴和首次出現(xiàn)位置。按照1、2分析從前往后累加前綴和sum 將首次出現(xiàn)前綴和位置記錄在哈希表中遍歷到i時(shí)前綴和sum在哈希表中已經(jīng)存在記錄時(shí)嘗試更新最長均衡長度maxLen max(maxLen, i - mp[sum])算法平均時(shí)間復(fù)雜度為OnC#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;string s;cinn;cins;intmaxLen0;intsum0;// 記錄前綴和首次出現(xiàn)位置unordered_mapint,intmp;mp[0]-1;for(inti0;in;i){sum(s[i]A?-1:1);// 兩個(gè)相同前綴和之間一定平衡if(mp.count(sum)){maxLenmax(maxLen,i-mp[sum]);// 記錄sum首次出現(xiàn)位置}else{mp[sum]i;}}coutmaxLen;}Javaimportjava.io.*;importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args)throwsException{BufferedReaderbrnewBufferedReader(newInputStreamReader(System.in));intnInteger.parseInt(br.readLine());Stringsbr.readLine();intmaxLen0;intsum0;// 記錄前綴和首次出現(xiàn)位置HashMapInteger,IntegermpnewHashMap();mp.put(0,-1);for(inti0;in;i){sum(s.charAt(i)A?-1:1);// 兩個(gè)相同前綴和之間一定平衡if(mp.containsKey(sum)){maxLenMath.max(maxLen,i-mp.get(sum));// 記錄sum首次出現(xiàn)位置}else{mp.put(sum,i);}}System.out.print(maxLen);}}pythonimportsys nint(sys.stdin.readline())ssys.stdin.readline().strip()maxLen0sum0# 記錄前綴和首次出現(xiàn)位置mp{}mp[0]-1foriinrange(n):sum-1ifs[i]Aelse1# 兩個(gè)相同前綴和之間一定平衡ifsuminmp:maxLenmax(maxLen,i-mp[sum])# 記錄sum首次出現(xiàn)位置else:mp[sum]iprint(maxLen)Javascriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});letinput[];rl.on(line,line{input.push(line.trim());});rl.on(close,(){letnNumber(input[0]);letsinput[1];letmaxLen0;letsum0;// 記錄前綴和首次出現(xiàn)位置letmpnewMap();mp.set(0,-1);for(leti0;in;i){sum(s[i]A?-1:1);// 兩個(gè)相同前綴和之間一定平衡if(mp.has(sum)){maxLenMath.max(maxLen,i-mp.get(sum));// 記錄sum首次出現(xiàn)位置}else{mp.set(sum,i);}}console.log(maxLen);});Gopackagemainimport(bufiofmtos)funcmain(){in:bufio.NewReader(os.Stdin)varnintvarsstringfmt.Fscan(in,n)fmt.Fscan(in,s)maxLen:0sum:0// 記錄前綴和首次出現(xiàn)位置mp:make(map[int]int)mp[0]-1fori:0;in;i{ifs[i]A{sum--}else{sum}// 兩個(gè)相同前綴和之間一定平衡ifpos,ok:mp[sum];ok{ifi-posmaxLen{maxLeni-pos}// 記錄sum首次出現(xiàn)位置}else{mp[sum]i}}out:bufio.NewWriter(os.Stdout)deferout.Flush()fmt.Fprint(out,maxLen)}