四数问题以及三数和值问题一般用Brute Force OJ会TLE,面试过程中写出BF算法也不是面试官想看到的,那么我们可以思考一下四数和值问题本质是在考察什么,表面是和值问题,本质是查找问题,对于查找,一般我们会联想到下面几点知识,i.e.,思考方向:
解题思路: 本题虽然是题18的扩展题,但是显然比它简单很多。这题主要考察哈希,我在写在前面点了一下面对四数问题的我们可能会采取的策略,此题可能思路又要变一变,我们可以这么思考,首先四数问题我们可以想到用BF解,但是BF最大的问题是时间复杂度太高,那么如果转换为查找为题,时间复杂度虽然降低一些,但依然无法接受,i.e. ,降低时间复杂度常用方法我们思维备用箱里应该还要能想到空间换时间以降低时间复杂度的原则,OK,想到这一步基本就能想出来要结合hashmap解题,因为题目给定的list是4个互不干扰的list,且没有要求组合不能重复,那么前查找问题时间复杂度就可以降低为,(本质上这里采取的也是解题策略中非常常见也重要的想法,查找数组消耗的时间复杂度为O(n),若有序,时间复杂度为O(lgn)),但是若事先将数组存入hash中,对应查找密集型场景,hash时间复杂度为O(1),能很好地消除O(n)时间复杂度),那么至此还有没有更优的解法呢,我们分析一下前面的做法本质是3+1组合,而正是前3导致的,那么若采取2+2组合,时间复杂度是否可以降低呢,OK,确实是这样,我们先计算A+B能组合出来的和值及其对应个数,然后在计算C+D时分别判断这个和值相反数是否存在,若存在则加上相应个数。
// 考察hash,将4个列表分成两组,先将A和B和值及其对应个数计算出来,
// 然后在计算C和D和值时,判断此和值在hash中是否存在,若存在则加上
// 对应个数
// T:O(n^2), S: O(n)
class Solution {
public:
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
unordered_map<int, int> m;
int res = 0;
for (auto &a : A) {
for (auto &b : B) {
++m[a + b];
}
}
for (auto &c : C) {
for (auto &d : D) {
res += m[-(c+d)];
}
}
return res;
}
};
解题思路: 本题给定的数组个数只有一个,在这个数组中找四数之和等于目标值,此题与题454最大的区别是只给一个数组,在这个数组里找4个数,那么这4个数之间肯定会互相干扰,不能随意选,那么在用BF解时,依然会遇到上面时间复杂度分析问题,但是hashmap不能work了(因为四数存在依赖),但是我们可以在BF基础上进行改进,先确定两个数,另外两个数用Two pointer解,基本思路到这儿题目就解出来了,而且时间复杂度为是可以AC的。目前要求组合不能重复,在解决这个问题时,我解出正确代码之前遇到1个坑点,这里记录一下:
请看代码:
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int n = nums.size();
vector<vector<int>> res;
sort(nums.begin(), nums.end());
for (int i = 0; i < n; ++i) {
if (i != 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < n; ++j) {
if (j != i + 1 && nums[j] == nums[j - 1]) continue;
int left = j + 1, right = n - 1, t = target - (nums[i] + nums[j]);
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == t) {
res.push_back({nums[i], nums[j], nums[left], nums[right]});
++left;
--right;
while (left < right && nums[left] == nums[left - 1]) ++left;
while (right > left && nums[right] == nums[right + 1]) --right;
} else if (sum < t) ++left;
else --right;
}
}
}
return res;
}
};
————————————
本文地址:https://blog.csdn.net/whutshiliu/article/details/107587256
如对本文有疑问, 点击进行留言回复!!
(一)maya2018快速装备创建骨骼和HumanIK创建骨骼、如何增加蒙皮,选择单个骨骼进行控制
荐 511遇见易语言大漠模块制作后台绑定窗口BindWindow
AcWing 324/poj 3345 Bribing FIPA(树形dp,分组背包)
网友评论