第三种方法为位运算的方法。
位运算符: << 左移 & 与 | 或
#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>
#include <unordered_map>
using namespace std;//时间 O(n) 空间 O(1)
bool hasSame(string str)
{
if(str.size() == )
return false;
bool ans = false;
vector<bool> flag(,false);
for(int i = ; i < str.size(); i++)
{
if(flag[str[i]] == true)
return true;
flag[str[i]] = true;
}
return false;
}
//时间 O(n*n) 空间 O(1)
bool hasSame2(string str)
{
if(str.size() == )
return false;
for(int i = ; i < str.size(); i++)
for(int j = i+; j < str.size(); j++)
{
if(str[i] == str[j])
return true;
}
return false;
}
//时间 O(n) 空间 O(1)
bool hasSame3(string str)
{
if(str.size() == )
return false;
if(str.size() > )
return true; int flag = ;
for(int i = ; i < str.size(); i++)
{
int num = <<(str[i] - 'a');
if(flag & num)
return true;
flag = flag | num;
}
return false;
}
int main()
{
cout<< hasSame3("abc");
cout<< hasSame3("aa");
cout<< hasSame3("abac");
cout<< hasSame3("bcb");
cout<< hasSame3("");
cout<< hasSame3(" ");
cout<< hasSame3(" ");
}