每日算法——快乐数、两数之和
202. 快乐数
class Solution {
public:bool isHappy(int n) {unordered_set<int> result_set;while(true){int sum = 0;while(n>0){sum+= (n%10)*(n%10);n/=10;}if(sum==1){return true;}else{if(result_set.find(sum) != result_set.end()){return false;}result_set.insert(sum);}n=sum;}}
};
由于题目中明确了只有循环和==1两种情况，使用快慢指针法同样可以求解：
class Solution {
public:int bitSquareSum(int n) {int sum = 0;while(n > 0){int bit = n % 10;sum += bit * bit;n = n / 10;}return sum;}bool isHappy(int n) {int slow = n, fast = n;do{slow = bitSquareSum(slow);fast = bitSquareSum(fast);fast = bitSquareSum(fast);}while(slow != fast);return slow == 1;}
};两数之和
时间复杂度为o(n)的解法：使用hash map（存储键值对）；
可以利用的细节：
由于是两数之和，根据当前遍历到的值，去map中找是否有target- nums[i]的值即可
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {std::unordered_map<int,int> set;for(int i = 0;i<nums.size();i++){auto iter = set.find(target -nums[i]);if(iter != set.end()){return {iter->second,i};}set.insert(pair<int,int>(nums[i],i));}return {};}
};