class Solution { public: vector<vector<int> > fourSum(vector<int> &num, int target) { sort(num.begin(),num.end()); vector<vector<int> > res; int* a = &num[0]; int len = num.size(); for (int i = 0; i < len; i++) { if (i > 0 && num[i] == num[i-1]) continue; for (int j = i+1; j < len; j++) { if (j > i+1 && num[j] == num[j-1]) continue; int x = j+1, y = len - 1; while (x < y) { int t = a[i] + a[j] + a[x] + a[y]; if (t == target) { res.push_back({a[i], a[j], a[x], a[y]}); while (x < y && a[x+1] == a[x]) x++; while (x < y && a[y-1] == a[y]) y--; x++; y--; } else if (t > target) { y--; } else { x++; } } } } return res; } };
@2013-10-07
N3
写了个复杂版本的。好处是方便拓展sum(a1...ai)都可以。i=2,3,4,5...
class Solution { public: vector<vector<int> > fourSum(vector<int> &num, int target) { vector<vector<int> > res; int n = num.size(); if (n < 4) return res; sort(num.begin(), num.end()); vector<int> v; gen(num, res, v, target, 0, 4); return res; } void gen(const vector<int>& a,vector<vector<int> >&res, vector<int>& v, int tar, int cur, int total) { if (v.size() == total) return; if (total - v.size() == 2) { int i = cur, j = a.size() - 1; while (i < j) { if (a[i] + a[j] == tar) { v.push_back(a[i]); v.push_back(a[j]); res.push_back(v); v.pop_back(); v.pop_back(); int t = i; while (i < j && a[i] == a[t]) i++; t = j; while (i < j && a[j] == a[t]) j--; } else if (a[i] + a[j] > tar) j--; else i++; } return; } int prev, i = cur; while (i + 3 - v.size() < a.size()) { v.push_back(a[i]); gen(a, res, v, tar - a[i], i+1, total); v.pop_back(); prev = i; while (i < a.size() && a[prev] == a[i]) i++; } } };
相关推荐
Leetcode two sum java 解法
本文档主要介绍了在Python编程语言中如何运用双指针算法解决LeetCode上的2Sum、3Sum及4Sum求和问题,并提供了相应的代码实现。LeetCode是一个非常受欢迎的在线编程平台,用于练习算法题目,尤其适合准备技术面试的...
本文将深入探讨如何使用Python实现双指针算法来解决LeetCode中的2sum、3sum和4sum问题,并提供相关代码示例。 首先,我们来看2sum问题。给定一个整数数组`nums`和一个目标值`target`,我们需要找到数组中两个数的...
oj.leetcode题解, 2sum, 运用hashtable解决这到问题,时间复杂度O(N)
leetcode 2sum leetCode解决方案 我对 leetCode 问题的解决方案 已解决的练习列表: 简单的: 2sum - 带有未排序的数组; O(n) 复杂度; 花了~3ms 2sum - 使用排序数组; O(n) 复杂度 罗马转整数; O(n) 复杂度 合并...
LC4: Longest Palindromic Substring [Medium] LC5: Median Of Two Sorted Arrays [Hard] LC6: Zigzag Conversion [Medium] LC7: Reverse Integer [Easy] LC8: String To Integer Atoi [Medium] LC9: Palindrome ...
leetcode 2SUM 使用以前的地图最快的 2Sum O(N) 使用 unordered_map 比 map 快 以前的地图 là gì ? 上一张地图 đơn giản là 地图 nhưng thay vì ta cần một vòng for để khởi tạo 地图 thì ta khởi...
3sum 力码 力扣算法 (注:“ :locked: " 表示你需要来自 Leetcode) # 标题 解决方案 困难 001 简单的 002 中等的 003 中等的 004 难的 005 中等的 006 简单的 007 简单的 008 简单的 009 简单的 010 难的 011 中等...
3sum leetcode-curation-topical 精选 Leetcode 问题,按主题/概念分类。 我的策展标准是问题必须是有价值的,而不仅仅是为了难而难。 有价值的问题通常可以以不同的时间/空间效率(通过使用各种数据结构)以多种...
js js_leetcode题解之18-4sum.js
"2Sum"是LeetCode中的一个经典问题,编号为Q1,属于基础级别的算法题。本文将深入探讨这个问题,理解其背后的逻辑,并从中学习到如何有效地解决此类问题。 2Sum问题的核心在于,给定一个整数数组`nums`和一个目标值...
java java_leetcode题解之Combination Sum IV.java
java java_leetcode题解之Combination Sum.java
java java_leetcode题解之Combination Sum III.java
java java_leetcode题解之Combination Sum II.java
java java_leetcode题解之Largest Sum of Averages.java
* 4Sum(4Sum):找到数组中四个元素的和等于目标值的元素。 这些知识点涵盖了算法设计、数据结构、数学运算、字符串操作、链表操作、栈和队列操作、字符串匹配和排序搜索等多方面的内容,为LeetCode刷题提供了一...
leetcode 轮廓 1_count_and_say.cpp - super_ugly_number.cpp - Detect_Pattern.cpp - degree_of_array.cpp - 键盘.cpp - 2Sum_Data_Structure_Design.cpp - shuffle_array.cpp - permutations.cpp - kth_missing_...
c c语言_leetcode 0001_two_sum
leetcode 3sum nlogn 让我们研究算法 微电脑网 : 2018.09.06。 用 BFS 搜索,用 DP 解决。 我过去没能做到,但感觉很好。 : 2018.09.06。 起初,它以这样的方式重复,如果有什么变化,它会再次旋转。 -> 超时 接下来...