专门做dnf补丁的网站,甘孜州手机网站建设,建筑服务网站企业,承德做网站优化今天#xff0c;带来哈希表和双指针相关算法的讲解。文中不足错漏之处望请斧正#xff01;
理论基础点这里 四数之和
题意简化
四数之和#xff0c;去重版#xff1a;找不重复的四元组
四元组四个元素下标不同, 和为target四元组不重复 由于输出四元组的顺序没有限制, …今天带来哈希表和双指针相关算法的讲解。文中不足错漏之处望请斧正
理论基础点这里 四数之和
题意简化
四数之和去重版找不重复的四元组
四元组四个元素下标不同, 和为target四元组不重复 由于输出四元组的顺序没有限制, 所以四元组之间, 元素的值必须完全不同 一个四元组中的元素能以任意顺序构成另一个四元组, 就称两个四元组是重复的只对a/b/c/d的某一个去重, 还会遇到重复的四元组
题意转化
在数组nums中收集所有满足条件的四元组不能重复四元组条件
四个元素下标不同四元素和为target
解决思路(抽象)
根据《三数之和》我们还是选择用双指针的方法来做。 循环不断拿取四元组, 满足条件就收割(不能收割重复的结果)。
怎么拿数
怎么拿数能最快拿到结果(避免暴力遍历全部组合)
排序根据有序性动态控制双指针, 控制四数之和的大小, 保证自己逐渐接近结果, 而不是死板地暴力遍历所有可能性。
两层循环静态拿数, 两个指针动态拿数 静态拿数i, j动态拿数双指针根据四数之和与target的大小移动
怎么去重
对a/b/c/d都要去重。
对ab的去重: ab是每次固定拿取的元素, 从这里去重, 是静态去重。 解释假如本轮的a/b和上一轮的a/b相同, 并且上一轮的a和b可以和后面的某两个元素cd组成结果集, 那么我这一轮的ab也会找到上一轮已经组合过的cd再次组合, 成为重复的结果集
对cd的去重cd是每次动态拿取的元素, 从这里去重, 是动态去重 解释[0, -1, -1, -1, 1, 1, 1]这个例子只有一个结果集[0, -1, 0]当我们收获了第一个结果集[0, -1, 1]后left和right按理讲都往里面收缩一下。但不一定只是一下如果只收缩一下那就可能会重复收割相同的结果集。
编程实现(具体)
剪枝有细节。
剪枝
有些朋友可能会延续三数之和的思路直接这样剪枝
if(nums[i] target) break;但这样其实是默认了a、b、c、d都是正数。本题会有这样的情况
nums [-4, -1, 0, 0]
target -5再看看[-4, -1, 0, 0]明明是符合条件的结果集但是nums[i](-4) target(-5)直接break了。
所以我们只有nums[i]和target都为正数才能剪枝。
class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {vectorvectorint result;// 排序sort(nums.begin(), nums.end());// 取固定的ab, 取动态变化的cd, 收割结果集for (int i 0; i nums.size(); i) { // 固定取a// 对a剪枝: 本题有负数, 只有二者都为正数才能这样剪枝if (nums[i] 0 target 0 nums[i] target) break; if (i 0 nums[i] nums[i - 1]) continue; // a的去重for (int j i 1; j nums.size(); j) { // 固定取b// 对ab的和剪枝:if (nums[i] nums[j] 0 target 0 nums[i] nums[j] target) break;if (j i 1 nums[j] nums[j - 1]) continue; // b的去重int left j 1; // 移动取c dint right nums.size() - 1;while (left right) { // left 和 right 移动取 cd , 收割结果集long long sum (long long)nums[i] nums[j] nums[left] nums[right]; // long long 防止相加溢出if (sum target) --right; // 四数之和大于target, 某个数需要变小, 让right--else if (sum target) left; // 四数之和小于target, 某个数需要变大, 让leftelse { // 收割结果集, 并跳过相同结果集(去重)result.push_back({nums[i], nums[j], nums[left], nums[right]});while (left right nums[left] nums[left 1]) left; // c的去重while (left right nums[right] nums[left - 1]) --right; // d的去重// left 和 right 迭代, 继续移动, 收割结果集left;--right; }}}}return result;}
};步骤概括
排序fori静态取a 对a剪枝对a去重, 跳过已经收割过的结果集forj静态取b 对ab剪枝对b去重, 跳过已经收割过的结果集left和right动态取cd 四数之和小于target, 某个数需要变大, 让left四数之和大于target, 某个数需要变小, 让right–四数之和等于target, 收割结果 对cd去重 因为本身就在移动找结果集, 所以取到结果后才能开始去重 left 和 right 迭代, 继续移动, 收割结果集 返回结果集 今天的分享就到这里了感谢您能看到这里。
这里是培根的blog期待与你共同进步
