企业官网建设流程全解析

网站建设 天台,卫生局网站模板,佛山公司网站设计团队,高端网站建设设计公司题目#xff08;四数相加 II#xff09;本质是#xff1a;给你 4 个数组 A、B、C、D统计有多少个四元组 (i, j, k, l)满足A[i] B[j] C[k] D[l] 0 关键点数组长度一般 ≤ 200暴力 4 重循环是 O(n^4) → 必超时核心思想#xff1a;把「四数相加」拆成「两数相加 两数相加…题目四数相加 II本质是给你 4 个数组 A、B、C、D统计有多少个四元组(i, j, k, l)满足A[i] B[j] C[k] D[l] 0关键点数组长度一般 ≤ 200暴力 4 重循环是O(n^4)→必超时核心思想把「四数相加」拆成「两数相加 两数相加」这是这道题的灵魂。数学变形A[i] B[j] C[k] D[l] 0 ↓ (A[i] B[j]) -(C[k] D[l])也就是说只要某个 (a b)等于某个 -(c d)那么它们就能凑成 0为什么用 unordered_map因为你需要做两件事统计 A B 的所有可能结果快速查找 -(C D) 是否存在哈希表刚好满足插入O(1)查找O(1)代码int fourSumCount(vectorint A, vectorint B, vectorint C, vectorint D) { unordered_mapint, int umap; //key:ab的数值value:ab数值出现的次数 // 遍历大A和大B数组统计两个数组元素之和和出现的次数放到map中 for (int a : A) { for (int b : B) { umap[a b]; } } int count 0; // 统计abcd 0 出现的次数 // 再遍历大C和大D数组找到如果 0-(cd) 在map中出现过的话就把map中key对应的value也就是出现次数统计出来。 for (int c : C) { for (int d : D) { if (umap.find(0 - (c d)) ! umap.end()) { count umap[0 - (c d)]; } } } return count; }时间复杂度分析部分复杂度构建 ABO(n²)遍历 CDO(n²)哈希查找O(1)