例题练习
217. 存在重复元素
将数组中每个数用map存起来，并记录数量，依照题意返回即可。
AC代码
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
map<int,int>mp;
for(auto c:nums)
mp[c]++;
int f=0;
for(auto d:nums)
{
if(mp[d]>1)
return true;
}
return false;
}
};
推荐练习：219. 存在重复元素 II
389. 找不同
只需要用两个map分别存s和t中字母的个数，然后遍历比较，若不同，就是被添加的字母。
AC代码
class Solution {
public:
char findTheDifference(string s, string t) {
map<char,int>mp;
for(auto c:s)
mp[c]++;
map<char,int>m;
for(auto x:t)
m[x]++;
char f
for(auto d:t)
{
if(mp[d]!=m[d])
{
f=d;
break;
}
}
return f;
}
};
推荐练习：136. 只出现一次的数字
3. 无重复字符的最长子串
滑动窗口+哈希，很简单，一个一个将s中的字符存进去，若数量大于一了，就让最前面的一个一个出去直到数量不大于1，然后每次都更新一下最大值。
AC代码
class Solution {
public:
int lengthOfLongestSubstring(string s) {
map<char,int>mp;
int ans=0;
for(int i=0,j=0;i<s.size();i++)
{
mp[s[i]]++;
while(mp[s[i]]>1)
{
mp[s[j]]--;
j++;
}
ans=max(ans,i-j+1);
}
return ans;
}
};
2799. 统计完全子数组的数目
用哈希，可以定义一个unordered_set可以自动去重且不会自动排序，节省时间，令res=s.size(),也就是不同元素的数目，由于这道题范围很小，可以双重循环遍历，让i为每个位置是作为其实位置有几个符合条件的完全子数组，一个一个插入set中，直到长度为res,每个外循环记得清空s.
AC代码
class Solution {
public:
int countCompleteSubarrays(vector<int>& a) {
unordered_set<int>s(a.begin(),a.end());
int res=s.size();
int ans=0,n=a.size();
for(int i=0;i<n;i++)
{
s.clear();
for(int j=i;j<n;j++)
{
s.insert(a[j]);
if(s.size()==res)
ans++;
}
}
return ans;
}
};
139. 单词拆分
动态规划+哈希
f[i]表示这个单词中【0~i】的状态，如果为true，就说明能表示出来，否则不能。
如果在 i 之前存在一个 j ，使得f[j] = true([0,j]的子串可以被拼出来)，并且[j, i]之间的子串刚好是某个单词表中的单词，那么就说明 [0, i]的子串可以被拼出来。这就是状态转移，直到f[n]=true,表示所有这个单词整体都能被表示出来。
AC代码
class Solution {
public:
bool wordBreak(string s, vector<string>& a) {
unordered_set<string>st(a.begin(),a.end());//用哈希表来存
int n=s.size();
s=' '+s;//便于处理边界问题
vector<bool>f(n+1);//状态数组
f[0]=true;//初始化为0
for(int i=1;i<=n;i++)
{
for(int j=i;j>0;j--)
{
if(f[j-1]&&st.count(s.substr(j,i-j+1)))
{
f[i]=true;
break;
}
}
}
return f[n];
}
};