第JavaC++算法leetcode828統(tǒng)計子串中唯一字符乘法原理目錄題目要求思路：模擬javaC++Rust

題目要求

思路：模擬

解題的核心思想在于逆向思維，不考慮每個子數(shù)組中的唯一字符個數(shù)，轉(zhuǎn)而考慮每個字符可以作為多少個子數(shù)組的唯一字符；

所以在計算答案時的算式和示例中給出的是不一樣的；在計算每個字符貢獻(xiàn)【即當(dāng)前向左向右分別可組成的答案個數(shù)】的時候要用到乘法原理。

對每一個字符s[i]s[i]s[i]都記錄其左邊和右邊的第一個相同字符位置，分別記為l[i]l[i]l[i]和r[i]r[i]r[i]，這兩個位置中間構(gòu)成的就是s[i]s[i]s[i]能夠作為唯一字符的最長子串，在這個最長的子串中還有若干個較短的子串，此時s[i]s[i]s[i]的貢獻(xiàn)可由到左邊和到右邊的距離相乘計算得出。

java

classSolution{

publicintuniqueLetterString(Strings){

char[]cs=s.toCharArray();

intn=cs.length,res=0;

int[]l=newint[n],r=newint[n];

int[]letters=newint[26];

Arrays.fill(letters,-1);

for(inti=0;ii++){

intidx=cs[i]-'A';

l[i]=letters[idx];//左邊第一個相同的字符所在位置

letters[idx]=i;//更新當(dāng)前字母最新左位置

Arrays.fill(letters,n);

for(inti=n-1;ii--){

intidx=cs[i]-'A';

r[i]=letters[idx];//右邊第一個相同的字符所在位置

letters[idx]=i;//更新當(dāng)前字母最新右位置

for(inti=0;ii++)

res+=(i-l[i])*(r[i]-i);

returnres;

時間復(fù)雜度：O(n)空間復(fù)雜度：O(n)

C++

因為memset初始化問題，所以在構(gòu)成結(jié)果的時候多一步判斷。

classSolution{

public:

intuniqueLetterString(strings){

intn=s.size(),res=0;

coutnendl;

intl[n],r[n];

intletters[26];

memset(letters,-1,sizeof(letters));

for(inti=0;ii++){

intidx=s[i]-'A';

l[i]=letters[idx];//左邊第一個相同的字符所在位置

letters[idx]=i;//更新當(dāng)前字母最新左位置

memset(letters,-1,sizeof(letters));

for(inti=n-1;ii--){

intidx=s[i]-'A';

r[i]=letters[idx];//右邊第一個相同的字符所在位置

letters[idx]=i;//更新當(dāng)前字母最新右位置

for(inti=0;ii++){

intri=r[i]==-1n:r[i];

res+=(i-l[i])*(ri-i);

returnres;

時間復(fù)雜度：O(n)空間復(fù)雜度：O(n)

Rust

用Rust的遍歷稍微改一下，思路一樣

implSolution{

pubfnunique_letter_string(s:String)-i32{

letcs=s.as_bytes();

(0..s.len()).into_iter().map(|i|{

let(mutl,mutr)=(i-1,i+1);

whilels.len()cs[l]!=cs[i]{

l-=1;

whilers.len()cs[r]!=cs[i]{

r+=1;

((i-l)*(r-i))asi32

}).sum::i32()