1748. 唯一元素的和

题目链接

计数法

使用一个数组，记录每一个数出现的次数，第一次出现就加上，第二次出现就减去

class Solution {
public:int sumOfUnique(vector<int>& nums) {int sum=0;int cnt[110]={0};int n=nums.size();for(int i=0;i<n;i++){if(cnt[nums[i]]==0) sum+=nums[i];else if(cnt[nums[i]]==1) sum-=nums[i];cnt[nums[i]]++;}return sum;}
};

哈希表（STL）

class Solution {
public:int sumOfUnique(vector<int>& nums) {int sum=0;unordered_map<int,int>mp;for(int i=0;i<nums.size();i++) mp[nums[i]]++;for(auto t:mp){if(t.second==1) sum+=t.first;}return sum;}
};

387. 字符串中的第一个唯一字符

题目链接

计数法统计出现次数，然后一次循环返回索引

class Solution {
public:int firstUniqChar(string s) {int cnt[26]={0};int n=s.size();for(int i=0;i<n;i++){cnt[s[i]-'a']++;}for(int i=0;i<n;i++){if(cnt[s[i]-'a']==1) return i;}return -1;}
};

哈希表存次数

class Solution {
public:int firstUniqChar(string s) {unordered_map<int, int> mp;for (auto t: s) {mp[t]++;}for (int i = 0; i < s.size(); ++i){if (mp[s[i]] == 1) return i;}return -1;}
};

1941. 检查是否所有字符出现次数相同

题目链接

统计每一个字符出现的次数，然后都和第一个次数比较相等与否就可以了

class Solution {
public:bool areOccurrencesEqual(string s) {unordered_map<int,int>mp;for(auto t:s) mp[t]++;int flag=mp[s[0]];for(auto t:mp){if(t.second!=flag) return false;}return true;}
};

448. 找到所有数组中消失的数字

题目链接

不多说，直接暴力

class Solution {
public:vector<int> findDisappearedNumbers(vector<int>& nums) {vector<int>res;int n=nums.size();bool st[100010];memset(st,false,sizeof(st));for(int i=0;i<nums.size();i++) st[nums[i]]=true;for(int i=1;i<=n;i++){if(!st[i]) res.push_back(i);}return res;}
};

然后考虑一下时空的优化

试了一下STL发现我错了。。。还是老老实实自己写吧

class Solution {
public:vector<int> findDisappearedNumbers(vector<int>& nums) {vector<int>res;int n=nums.size();unordered_map<int,int>mp;for(int i=0;i<nums.size();i++) mp[nums[i]]=1;for(int i=1;i<=n;i++){if(mp.find(i)==mp.end()) res.push_back(i);}return res;}
};

最省空间的那不就是用原数组了嘛

终极版

最好的方法基本还是用哈希表吧。不使用额外数组的思路就是直接用当前数组做哈希表了。手动实现哈希表先要想一个公式，注意到（nums[i]-1)%n==(nums[i]-1+n)%n==(num[i]-1+2*n)%n==…于是我们就可以直接使用(nums[i]-1)%n作为计算索引的公式（%n保证了新索引不会越界）。我们给所有数组中有的数字的索引除都加了若干次n，如果一个位置的数字最后都小于n那他就一定不存在了

class Solution {
public:vector<int> findDisappearedNumbers(vector<int>& nums) {vector<int> res;int n = nums.size();for (int i = 0; i < n; i++) {int t = (nums[i] - 1) % n;nums[t] += n;}for (int i = 0; i < n; i++)if (nums[i] <= n) res.push_back(i + 1);return res;}
};

1512. 好数对的数目

题目链接

计数法直接统计

class Solution {
public:int numIdenticalPairs(vector<int>& nums) {int cnt[110]={0};int flag=0,sum=0;int n=nums.size();for(int i=0;i<n;i++){cnt[nums[i]]++;flag=max(flag,nums[i]);}for(int i=1;i<=flag;i++){sum+=(cnt[i]-1)*cnt[i]/2;}return sum;}
};

1711. 大餐计数

题目链接

枚举一个数，然后枚举2的整数幂，寻找差是否存在

class Solution {
public:int countPairs(vector<int>& deliciousness) {const int MOD=1e9+7;int cnt[(1<<21)+1]={0};int i,sum=0;int ans=0;for(i=0; i<deliciousness.size(); i++){         for(sum = 1;sum<=(1<<21); sum*=2) {   int t = sum-deliciousness[i];         if (t>=0) ans += cnt[t];                 ans%=MOD;}cnt[deliciousness[i]]++;                }return ans;   }
};