- 哈希表
- 242. 有效的字母异位词
- 349. 两个数组的交集
- 202. 快乐数
- 1. 两数之和
- 454. 四数相加 II
- 383. 赎金信
- 15. 三数之和
- 四数之和
哈希表的思想起始非常简单，就是通过o(1)的时间复杂度从n个对象中找出你所需要的。
下面来看题目
题目
这题就是通过一个数组来模拟哈希表，统计字母出现的次数，只要次数相同那么就是可以的。
class Solution {
public:
bool isAnagram(string s, string t) {
int* nums = new int[26];
for (int i = 0; i < 26; i++) {
nums[i] = 0;
}
for (char& c : s) {
nums[c - 97]++;
}
for (char& c : t) {
nums[c - 97]--;
}
for (int i = 0; i < 26; i++) {
if (nums[i] != 0)return false;
}
return true;
}
};
349. 两个数组的交集
题目
这题就是统计两次均出现的数字，因为限制了大小，所以直接创建数组进行统计就可以。
class Solution {
public:
vector intersection(vector& nums1, vector& nums2) {
int* nums = new int[1010];
for (int i = 0; i < 1010; i++) {
nums[i] = 0;
}
for (int& c : nums1) {
nums[c]++;
}
vector ans;
for (int& c : nums2) {
if (nums[c] > 0) {
ans.push_back(c);
nums[c] = 0;
}
}
return ans;
}
};
202. 快乐数
题目
这题的思想就是要快速的判断这个数在之前是否出现过，首先int的范围是小于2^31的，这是一个十位数，每一位是9的话，每一位平方和加起来也就810，三位数全是9的和也就243，想要节省空间的话用243来做，用810也是不会遇到任何问题的
class Solution {
public:
bool isHappy(int n) {
int* nums = new int[900];
for (int i = 0; i < 900; i++) {
nums[i] = 0;
}
while (n != 1) {
int sum = 0;
while (n > 0) {
sum += (n % 10) * (n % 10);
n /= 10;
}
if (nums[sum] == 1) return false;
n = sum;
nums[sum] = 1;
}
return true;
}
};
1. 两数之和
题目
这题主要是学习使用c++的unordered_map，可以使用o(1)的时间复杂度找到你想要的值，而且存储的key是你的值，而value是下标。
class Solution {
public:
vector twoSum(vector& nums, int target) {
std::unordered_map map;
for (int i = 0; i < nums.size(); i++)
{
auto iter = map.find(target - nums[i]);
if (iter != map.end()) {
return {iter->second,i};
}
map.insert(pair(nums[i], i));
}
return {};
}
};
454. 四数相加 II
题目
这题呢起始和上一题差不多，如果一个全部去找呢那就是n^4的复杂度，两两组合，然后再找一次那就是n^3的复杂度了。
class Solution {
public:
int fourSumCount(vector& nums1, vector& nums2, vector& nums3, vector& nums4) {
std::unordered_map map1;
for (int i = 0; i < nums1.size(); i++)
{
for (int j = 0; j < nums2.size(); j++)
{
map1[nums1[i] + nums2[j]]++;
}
}
int ans = 0;
for (int i = 0; i < nums3.size(); i++)
{
for (int j = 0; j < nums4.size(); j++)
{
int x = nums3[i] + nums4[j];
auto iter = map1.find(-x);
if (iter != map1.end()) {
ans += iter->second;
}
}
}
return ans;
}
};
383. 赎金信
题目
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int* nums = new int[26];
for (int i = 0; i < 26; i++) {
nums[i] = 0;
}
for (char& c : magazine) {
nums[c - 97]++;
}
for (char& c : ransomNote) {
nums[c - 97]--;
if (nums[c - 97] < 0) {
return false;
}
}
return true;
}
};
15. 三数之和
题目
class Solution {
public:
vector> threeSum(vector& nums) {
vector> result;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++) {
if (nums[i] > 0) {
return result;
}
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (right > left) {
if (nums[i] + nums[left] + nums[right] > 0) right--;
else if (nums[i] + nums[left] + nums[right] < 0) left++;
else {
result.push_back(vector{nums[i], nums[left], nums[right]});
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
right--;
left++;
}
}
}
return result;
}
};
四数之和
题目
class Solution {
public:
vector> fourSum(vector& nums, int target) {
vector> result;
sort(nums.begin(), nums.end());
for (int k = 0; k < nums.size(); k++) {
if (nums[k] > target && nums[k] >= 0 && target >= 0) {
break;
}
// 对nums[k]去重
if (k > 0 && nums[k] == nums[k - 1]) {
continue;
}
for (int i = k + 1; i < nums.size(); i++) {
if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0 && target >= 0) {
break;
}
if (i > k + 1 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (right > left) {
if ((long) nums[k] + nums[i] + nums[left] + nums[right] > target) {
right--;
} else if ((long) nums[k] + nums[i] + nums[left] + nums[right] < target) {
left++;
} else {
result.push_back(vector{nums[k], nums[i], nums[left], nums[right]});
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
right--;
left++;
}
}
}
}
return result;
}
};
