242.有效的字母异位词
1.哈希
思路
字母的异位词意味着两个词中字符的种类和次数都相等。因为只有26个字符，所以我们可以通过数组实现一个26位的哈希表。先记录一个词中字符的种类和个数，再对另一个词进行遍历，减去相同的字符，如果数组中所有字符的个数最终全部为0，则互为字母异位词。
实现
点击查看代码
class Solution {
public:
bool isAnagram(string s, string t) {
vector<int> A(26,0);
for(int i=0; i < s.size(); i++){
A[s[i]-'a']++;
}
for(int i = 0; i < t.size(); i++){
A[t[i]-'a']--;
}
for(int i = 0; i < 26; i++){
if(A[i] != 0){
return false;
}
}
return true;
}
};
复杂度分析
- 时间复杂度：O(n)，n为s的大小
- 空间复杂度：O(m), m=26
2.排序+遍历
思路
互为异位词意味着两个字符串的大小相等。如果大小相等，在对字符串进行排序，如果每一位上的字母都相等，则互为字母异位词。
实现
点击查看代码
class Solution {
public:
bool isAnagram(string s, string t) {
if(s.size() != t.size())return false;
sort(s.begin(),s.end());
sort(t.begin(),t.end());
return s==t;
}
};
复杂度分析
- 时间复杂度：O(nlog(n)+n),n为s的长度
- 空间复杂度：O(logn),排序算法的开销
349.两个数组的交集
1.哈希
思路
两个数组的交集不需要有序，只是一个集合，一次选择使用unordered_set容器。通过遍历一个数组，check记录数组中的数字。在对另一个数组进行遍历，如果在check中，就将该数字输入结果vector数组中，并将check中的该数字擦除。
实现
点击查看代码
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
vector<int> result;
unordered_set<int> check;
for(auto& a:nums1){
check.insert(a);
}
for(auto& b:nums2){
if(check.count(b)){
result.push_back(b);
check.erase(b);
}
}
return result;
}
};
复杂度分析
- 时间复杂度：O(n),n为数组的长度
- 空间复杂度：O(n)
2.排序+双指针
思路
通过对两个数组进行排序，然后使用指针对两个数组进行遍历，因为数组有序，所以从小到大，为了保证唯一性，使用pre保证不与前一个数字相等。
实现
点击查看代码
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
vector<int> result;
sort(nums1.begin(),nums1.end());
sort(nums2.begin(),nums2.end());
int pre =INT32_MAX;
for( int i = 0, j = 0; i < nums1.size() && j < nums2.size();){
if(nums1[i] == nums2[j]&&nums1[i] != pre){
result.push_back(nums1[i]);
pre = nums1[i];
i++;
j++;
}
else if(nums1[i] > nums2[j]){
j++;
}
else{
i++;
}
}
return result;
}
};
复杂度分析
- 时间复杂度：O(nlogn+mlogm)
- 空间复杂度：O(logn+logm)
202 快乐数
1.哈希
思路
要记录一个数字有没有重复出现，第一应该想到的方法就是哈希。将出现过的数字记录在set中，再判断是否重复出现。
实现
点击查看代码
class Solution {
public:
bool isHappy(int n) {
unordered_set<int> check;
check.insert(n);
while(1){
int sum = 0;
while(n){
sum += (n%10)*(n%10);
n=n/10;
}
n=sum;
if(n == 1)return true;
else if(check.count(n)){
return false;
}
check.insert(n);
}
}
};
复杂度分析
- 时间复杂度：logn,n每次进行换算的复杂度为logn
- 空间复杂度：O(n)？
2.快慢指针
思路
能否实现循环其实与环形链表的情况相似，只是不用指针和节点而已。
实现
点击查看代码
class Solution {
public:
bool isHappy(int n) {
int fast = n;
int slow = n;
while(1){
fast = getNext(getNext(fast));
slow = getNext(slow);
if(fast == 1)return true;
if(fast == slow)return false;
}
}
int getNext(int n){
int sum = 0;
while(n){
sum += (n%10)*(n%10);
n/=10;
}
return sum;
}
};
复杂度分析
- 时间复杂度：O(logn)
- 空间复杂度：O(1)
1.两数之和
1.哈希
思路
因为要同时返回数值和数的下标，因此需要使用键值对，map就可以派上用场。对数组进行遍历，将数字和下标放进map中，然后检查target-nums[i]是否出现在map中。
实现
点击查看代码
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
std::unordered_map<int,int> check;
for(int i = 0; i < nums.size(); i++){
auto iter = check.find(target-nums[i]);
if(iter != check.end()){
return{iter->second,i};
}
check.insert(pair<int,int>(nums[i],i));
}
return{};
}
};
复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(n)
2.暴力解法
思路
对数组进行两次遍历，看和是否等于target。
实现
点击查看代码
class Solution {
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
return new int[0];
}
}
复杂度分析
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)