代码随想录算法训练营第七天| 454. 两数相加Ⅱ、383.赎金信、15.三数之和、18.四数之和

454题拆成两块 各自匹配 化成两个O(n^2)运算

 1 class Solution {
 2 public:
 3     int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
 4         //四个数组拆分成两块 两块 
 5         unordered_map<int,int> sum;
 6         int ans = 0;
 7         for (int n1:nums1) {
 8             for (int n2:nums2) {
 9                 sum[n1+n2]++;
10             }
11         }
12         for (int n3:nums3) {
13             for (int n4:nums4) {
14                 if (sum.find(0-n3-n4) != sum.end()) {
15                     ans += sum[0-n3-n4];//加上这个要求的次数 
16                 }
17             }
18         }
19         return ans;
20     }
21 };

383题笨方法 统计 计数

 1 class Solution {
 2 public:
 3     bool canConstruct(string ransomNote, string magazine) {
 4         unordered_map<char, int> charCount;
 5         for (char t:ransomNote) {
 6             charCount[t]--;
 7         }
 8         for (char s:magazine) {
 9             charCount[s]++;
10         }
11         for (char ch = 'a'; ch <= 'z'; ++ch) {
12             if (charCount[ch] < 0) {
13                 return false;
14             }
15         }
16         return true;
17     }
18 };

15题琢磨了很久 哈希表法太容易超时了 还得是双指针法啊

 1 //上来就三重循环 有点难绷得住
 2 //那不能三重循环 直接空间换时间？
 3 //第一遍 遍历 我按下标存放
 4 class Solution {
 5 public:
 6     vector<vector<int>> threeSum(vector<int>& nums) {
 7         vector<vector<int>> ans;
 8         unordered_map<int, vector<pair<int, int>>> myMap;
 9 
10         // 构建哈希表，存储所有满足条件的 (i, j) 组合
11         for (int i = 0; i < nums.size(); ++i) {
12             for (int j = i + 1; j < nums.size(); ++j) {
13                 int sum = nums[i] + nums[j];
14                 myMap[sum].push_back({i, j});
15             }
16         }
17 
18         // 查找满足条件的三元组 (i, j, k)
19         for (int k = 0; k < nums.size(); ++k) {
20             int target = 0 - nums[k];
21 
22             if (myMap.find(target) != myMap.end()) {
23                 for (auto& pair : myMap[target]) {
24                     int i = pair.first;
25                     int j = pair.second;
26                     if (k != i && k != j) {
27                         vector<int> triplet = {nums[i], nums[j], nums[k]};
28                         sort(triplet.begin(), triplet.end());
29                         ans.push_back(triplet);
30                     }
31                 }
32             }
33         }
34 
35         // 使用 set 去重
36         set<vector<int>> unique_ans(ans.begin(), ans.end());
37         ans.assign(unique_ans.begin(), unique_ans.end());
38 
39         return ans;
40     }
41 };
42 //辛辛苦苦写的哈希算法 直接超时 好好好好 换到双指针法

 1 class Solution {
 2 public:
 3     vector<vector<int>> threeSum(vector<int>& nums) {
 4         vector<vector<int>> ans;
 5         sort(nums.begin(), nums.end());
 6         int n = nums.size();
 7         for (int i = 0; i < n - 2; ++i) {
 8             if (i > 0 && nums[i] == nums[i - 1]) continue; // 跳过重复的元素
 9 
10             int left = i + 1;
11             int right = n - 1;
12             while (left < right) {
13                 int sum = nums[i] + nums[left] + nums[right];
14                 if (sum == 0) {
15                     ans.push_back({nums[i], nums[left], nums[right]});
16                     while (left < right && nums[left] == nums[left + 1]) left++; // 跳过重复的元素
17                     while (left < right && nums[right] == nums[right - 1]) right--; // 跳过重复的元素
18                     left++;
19                     right--;
20                 } else if (sum < 0) {
21                     left++;
22                 } else {
23                     right--;
24                 }
25             }
26         }
27  
28     // sort(ans.begin(), ans.end());
29     // ans.erase(unique(ans.begin(), ans.end()), ans.end());
30     //这个去重操作要好好学学  不用学了 多余的 
31     return ans;
32     }
33 };

18题就是15题套皮 多加一层循环

 1 class Solution {
 2 public:
 3     vector<vector<int>> fourSum(vector<int>& nums, int target) {
 4         //可不可以在三数之和基础上加一层循环
 5         vector<vector<int>> ans;
 6         sort(nums.begin(), nums.end());
 7         int n = nums.size();
 8         
 9         for (int i = 0; i < n - 3; ++i) {
10             if (i > 0 && nums[i] == nums[i - 1]) continue; // 跳过重复的元素
11             
12             for (int j = i + 1; j < n - 2; ++j) {
13                 if (j > i + 1 && nums[j] == nums[j - 1]) continue; // 跳过重复的元素
14                 
15                 int left = j + 1;
16                 int right = n - 1;
17                 
18                 while (left < right) {
19                     long long sum = static_cast<long long>(nums[i]) + nums[j] + nums[left] + nums[right];
20                     if (sum == target) {
21                         ans.push_back({nums[i], nums[j], nums[left], nums[right]});
22                         while (left < right && nums[left] == nums[left + 1]) left++; // 跳过重复的元素
23                         while (left < right && nums[right] == nums[right - 1]) right--; // 跳过重复的元素
24                         left++;
25                         right--;
26                     } else if (sum < target) {
27                         left++;
28                     } else {
29                         right--;
30                     }
31                 }
32             }
33         }
34         
35         return ans;
36     }
37 };

许久没跟着刷题了，不说了 开工！