赞
踩
这道题目的暴力解法是O(n^4),可以与两数之和一样使用哈希法解决,但是必要两个嵌套for循环了!
这道题可以采用的哈希结构为map类型的,key值作元素值,value值作为同一个key值出现的次数
- class Solution {
- public:
- int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
- //2024.2.27二刷
- //这道题目的暴力解法是O(n^4),可以与两数之和一样使用哈希法解决,但是必要两个for循环了!
- //这道题可以采用的哈希结构为map类型的,key值作元素值,value值作为同一个key值出现的次数
- //因此用的是unordered_map
- unordered_map<int, int> mymap;
- //首先遍历前两个数组
- for (int i = 0; i < nums1.size(); i++) {
- for (int j = 0; j < nums2.size(); j++) {
- mymap[-nums1[i] - nums2[j]]++;//这个存数据的方式太巧妙了!
- }
- }
- int count = 0;//统计个数
- for (int i = 0; i < nums3.size(); i++) {
- for (int j = 0; j < nums4.size(); j++) {
- if (mymap.find(nums3[i] + nums4[j]) != mymap.end()) {
- count += mymap[nums3[i] + nums4[j]];
- }
- }
- }
- return count;
- }
- };
这道题有哈希法的影子!与字母异位那题很像。由题知不可重复,采用数组
- class Solution {
- public:
- bool canConstruct(string ransomNote, string magazine) {
- //这道题有哈希法的影子!与字母异位那题很像。由题知不可重复,
- //采用数组
- int record[26] = {0};//初始化为0
- for (int i = 0; i < ransomNote.size(); i++) {
- record[ransomNote[i] - 'a']++;
- }
- for (int j = 0; j < magazine.size(); j++) {
- record[magazine[j] - 'a']--;
- }
- for (int k = 0; k < 26; k++) {
- if (record[k] > 0) return false;
- }
- return true;
- }
- };
想到了哈希法,但是不太会做。
无
同三数之和
无
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。