目录
1--有效的字母异位词
2--两个数组的交集
3--两数之和
4--四数相加II
5--三数之和
6--四数之和
1--有效的字母异位词
利用哈希表存储每个字母的出现次数，比较两个字符串各个字母出现次数是否相等即可；
#include <iostream>
#include <string>
#include <vector>
class Solution {
public:
bool isAnagram(std::string s, std::string t) {
// 用数组实现哈希表
std::vector<int> hash(26, 0);
for(auto i = 0; i < s.length(); i++){
hash[s[i] - 'a']++;
}
// 遍历字符串t
for(auto i = 0; i < t.length(); i++){
hash[t[i] - 'a']--;
}
// 遍历哈希表
for(int i = 0; i < 26; i++){
if(hash[i] != 0) return false;
}
return true;
}
};
int main(int argc, char argv[]){
// s = "anagram", t = "nagaram"
std::string s = "anagram", t = "nagaram";
Solution S1;
bool res = S1.isAnagram(s, t);
if(res) std::cout << "true" << std::endl;
else std::cout << "false" << std::endl;
return 0;
}2--两个数组的交集
利用哈希表存储数组1的元素，接着遍历数组2并判断元素是否存储在哈希表中，将交集元素存储并返回；
#include <iostream>
#include <unordered_set>
#include <vector>
class Solution {
public:
std::vector<int> intersection(std::vector<int>& nums1, std::vector<int>& nums2) {
std::unordered_set<int> hash1;
for(int i = 0; i < nums1.size(); i++){
hash1.insert(nums1[i]);
}
std::unordered_set<int> result;
for(int i = 0; i < nums2.size(); i++){
if(hash1.find(nums2[i]) != hash1.end()){
result.insert(nums2[i]);
}
}
std::vector<int> res;
for(auto item : result){
res.push_back(item);
}
return res;
}
};
int main(int argc, char argv[]){
// nums1 = [1,2,2,1], nums2 = [2,2]
std::vector<int> nums1 = {1, 2, 2, 1}, nums2 = {2, 2};
Solution S1;
std::vector<int> res = S1.intersection(nums1, nums2);
for(auto item : res) std::cout << item << " ";
std::cout << std::endl;
return 0;
}3--两数之和
利用哈希表存储，key 为 target - nums[i]，value 为 i；遍历数组判断当前nums[i]是否在哈希表中出现，返回匹配的两个结果对应的索引即可；
#include <iostream>
#include <unordered_map>
#include <vector>
class Solution {
public:
std::vector<int> twoSum(std::vector<int>& nums, int target) {
std::vector<int> res;
std::unordered_map<int, int> hash;
for(int i = 0; i < nums.size(); i++){
if(hash.find(nums[i]) != hash.end()){
res.push_back(hash[nums[i]]);
res.push_back(i);
return res;
}
hash.emplace(target - nums[i], i);
}
return res;
}
};
int main(int argc, char argv[]){
// nums = [2,7,11,15], target = 9
std::vector<int> nums = {2, 7, 11, 15};
int target = 9;
Solution S1;
std::vector<int> res = S1.twoSum(nums, target);
for(auto item : res) std::cout << item << " ";
std::cout << std::endl;
return 0;
}4--四数相加II
利用哈希表，其中key为两个数组对应元素的和，value为出现的次数；接着遍历剩下两个数组的元素和是否在哈希表中出现，记录出现的次数即匹配结果；
#include <iostream>
#include <unordered_map>
#include <vector>
class Solution {
public:
int fourSumCount(std::vector<int>& nums1, std::vector<int>& nums2, std::vector<int>& nums3, std::vector<int>& nums4) {
std::unordered_map<int, int> hash;
for(int i = 0; i < nums1.size(); i++){
for(int j = 0; j < nums2.size(); j++){
hash[(nums1[i] + nums2[j])] ++;
}
}
int res = 0;
for(int i = 0; i < nums3.size(); i++){
for(int j = 0; j < nums3.size(); j++){
if(hash.find(0 - (nums3[i] + nums4[j])) != hash.end()){
res += hash[0 - (nums3[i] + nums4[j])];
}
}
}
return res;
}
};
int main(int argc, char argv[]){
// nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
std::vector<int> nums1 = {1, 2}, nums2 = {-2, -1}, nums3 = {-1, 2}, nums4 = {0, 2};
Solution S1;
int res = S1.fourSumCount(nums1, nums2, nums3, nums4);
std::cout << res << std::endl;
return 0;
}5--三数之和
本题基于双指针算法，需要注意去重；
#include <iostream>
#include <vector>
#include <algorithm>
class Solution {
public:
std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
std::vector<std::vector<int>> res;
std::sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size(); i++){
if(i > 0 && nums[i] == nums[i - 1]) continue; // 去重
int l = i + 1, r = nums.size() - 1;
while(l < r){
if(l > i + 1 && nums[l] == nums[l - 1]){
l++;
continue; // 去重
}
if(nums[i] + nums[l] + nums[r] == 0){
res.push_back({nums[i], nums[l], nums[r]});
l++;
r--;
}
else if(nums[i] + nums[l] + nums[r] > 0){
r--;
}
else{
l++;
}
}
}
return res;
}
};
int main(int argc, char* argv[]){
// nums = [-1,0,1,2,-1,-4]
std::vector<int> nums = {-1, 0, 1, 2, -1, -4};
Solution S1;
std::vector<std::vector<int>> res = S1.threeSum(nums);
for(auto item : res){
for(auto v : item) std::cout << v << " ";
std::cout << std::endl;
}
return 0;
}6--四数之和
类似于三数之和，只需额外多遍历一次，同时注意剪枝和去重的操作；
#include <iostream>
#include <vector>
#include <algorithm>
class Solution {
public:
std::vector<std::vector<int>> fourSum(std::vector<int>& nums, int target) {
std::vector<std::vector<int>> res;
std::sort(nums.begin(), nums.end());
int len = nums.size();
for(int i = 0; i < len; i++){
// 剪枝
if(nums[i] >= 0 && nums[i] > target) break;
// 去重
if(i > 0 && nums[i] == nums[i-1]) continue;
// three sum
for(int j = i + 1; j < len; j++){
// 剪枝
if (nums[i] + nums[j] > target && nums[i] + nums[j] >= 0) break;
// 去重
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int l = j + 1, r = len - 1;
while(l < r){
if((long) nums[i] + nums[j] + nums[l] + nums[r] == target){
res.push_back({nums[i], nums[j], nums[l], nums[r]});
// 去重
while (r > l && nums[r] == nums[r - 1]) r--;
while (r > l && nums[l] == nums[l + 1]) l++;
l++;
r--;
}
else if((long) nums[i] + nums[j] + nums[l] + nums[r] < target){
l++;
}
else{
r--;
}
}
}
}
return res;
}
};
int main(int argc, char* argv[]){
// nums = [-1,0,1,2,-1,-4]
std::vector<int> nums = {1, 0, -1, 0, -2, 2};
int target = 0;
Solution S1;
std::vector<std::vector<int>> res = S1.fourSum(nums, target);
for(auto item : res){
for(auto v : item) std::cout << v << " ";
std::cout << std::endl;
}
return 0;
}
