生活随笔
收集整理的這篇文章主要介紹了
两个数组包含
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
http://blog.csdn.net/yysdsyl/article/details/5421200
題目：
You have given two arrays, say
?
answer is （1，5）
?
先給出代碼，再結合代碼解釋，如下：
[cpp] ?view plaincopy
#include?<iostream> ?? #include?<map> ?? ?? using ? namespace ?std;?? ?? void ?FindConsecutiveSubarrLocation( int ?A[],? int ?lenA,? int ?B[],? int ?lenB)?? {?? ????map<int ,? int >?bmap;?? ????map<int ,? int >?windowmap;?? ????map<int ,? int >?diffmap;?? ????for ( int ?i?=?0;?i<?lenB;?i++)?? ????{?? ????????if (bmap.count(B[i])?==?0)?? ????????????bmap[B[i]]?=?1;?? ????????else ?? ????????????++bmap[B[i]];?? ????????if (windowmap.count(A[i])?==?0)?? ????????????windowmap[A[i]]?=?1;?? ????????else ?? ????????????++windowmap[A[i]];?? ????}?? ?? ????map<int ,? int >::iterator?it?=?bmap.begin();?? ????int ?sameElement?=?0;?? ????while (it?!=?bmap.end())?? ????{?? ????????if (windowmap.count((*it).first)?!=?0)?? ????????{?? ????????????diffmap[(*it).first]?=?windowmap[(*it).first]?-?(*it).second;?? ????????????if (diffmap[(*it).first]??==?0)?? ????????????????sameElement++;?? ????????}?? ????????else ?? ????????????diffmap[(*it).first]?=?-(*it).second;;?? ????????it++;?? ????}?? ?? ????if (sameElement?==?lenB)?? ????{?? ????????cout<<"----------find?one---------" <<endl;?? ????????cout<<"start?index:" <<0<<endl;?? ????????cout<<"end?index:" <<lenB-1<<endl;?? ????}?? ?? ????for ( int ?i?=?lenB;?i?<?lenA;?i++)?? ????{?? ????????if (diffmap.count(A[i-lenB])?!=?0)?? ????????{?? ????????????diffmap[A[i-lenB]]--;?? ????????????if (diffmap[A[i-lenB]]?==?0)?? ????????????????sameElement++;?? ????????????else ? if (diffmap[A[i-lenB]]?==?-1)?? ????????????????sameElement--;?? ????????}?? ????????if (diffmap.count(A[i])?!=0)?? ????????{?? ????????????diffmap[A[i]]++;?? ????????????if (diffmap[A[i]]?==?0)?? ????????????????sameElement++;?? ????????????else ? if (diffmap[A[i]]?==?1)?? ????????????????sameElement--;?? ????????}?? ????????if (sameElement?==?diffmap.size())?? ????????{?? ????????????cout<<"----------find?one---------" <<endl;?? ????????????cout<<"start?index:" <<i-lenB+1<<endl;?? ????????????cout<<"end?index:" <<i+1<<endl;?? ????????}?? ????}?? }?? ?? int ?main()?? {?? ????int ?A[]?=?{4,?1,?2,?1,?8,?9,?2,?1,?2,?9,?8,?4,?6};?? ????int ?B[]?=?{1,?1,?2,?8,?9};?? ????int ?lenA?=? sizeof (A)/ sizeof ( int );?? ????int ?lenB?=? sizeof (B)/ sizeof ( int );?? ????FindConsecutiveSubarrLocation(A,?lenA,?B,?lenB);?? ????return ?0;?? }??
?
?
思路：
ex，
??? int A[] = {4, 1, 2, 1, 8, 9, 5, 3, 2, 9, 8, 4, 6};
首先初始化map:
???? 代碼中的變量"sameElement"代表的是diffmap中有多少pair與bmap匹配,?顯然，初始化后的“sameElement”變量值會是3 ( 1:0, 2:0, 8:0 in diffmap).
?????? if(diffmap.count(A[i-lenB]) != 0)
這個題目有一個陷阱，就是B數組可能有重復的數字。
上面的思路很精妙，既然要求B中的元素在A中連續出現，則A中的窗口就是B的大小。每次就是減少窗口最左邊的元素，增加窗口最右邊的元素
但是，上面的算法有些錯誤，47和55行，不應該判斷是否為0，而是直接--或者直接++
總結
以上是生活随笔 為你收集整理的两个数组包含 的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔 網站內容還不錯，歡迎將生活随笔 推薦給好友。
