新博文地址:[leetcode]4Sum
4Sum
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:
Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
The solution set must not contain duplicate quadruplets.
For example, given array S = {1 0 -1 0 -2 2}, and target = 0.
A solution set is:
(-1, 0, 0, 1)
(-2, -1, 1, 2)
(-2, 0, 0, 2)
Note:
Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
The solution set must not contain duplicate quadruplets.
For example, given array S = {1 0 -1 0 -2 2}, and target = 0.
A solution set is:
(-1, 0, 0, 1)
(-2, -1, 1, 2)
(-2, 0, 0, 2)
这道题可以参考3Sum 和3Sum Closest ,只需要在3Sum的外层再加一层循环即可。不了解的请戳这里。时间复杂度为O(n^3),但是我在网上看到一个算法时间复杂度只有O(n^2),但是空间复杂度太大,而且网上只提供了算法思想,并没有给出实现,本以为O(n^3)过不去,因此把O(n^2)的算法实现了一下。代码太长太丑,阅览请慎重:
List<List<Integer>> result = new ArrayList<List<Integer>>(); Set<String> duplicate = new HashSet<String>(); public List<List<Integer>> fourSum(int[] num, int target) { if (num == null || num.length < 4) { return result; } HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>(); Map<Integer, List<int[]>> twoSum = new HashMap<Integer, List<int[]>>(); Set<Integer> processed = new HashSet<Integer>(); for (int i = 0; i < num.length; i++) { hash.put(num[i], hash.containsKey(num[i]) ? hash.get(num[i]) + 1 : 1); for (int j = i + 1; j < num.length; j++) { int[] node = new int[] { num[i], num[j] }; if (twoSum.containsKey(num[i] + num[j])) { twoSum.get(num[i] + num[j]).add(node); } else { List<int[]> list = new ArrayList<int[]>(); list.add(node); twoSum.put(num[i] + num[j], list); } } } for (int k : twoSum.keySet()) { if (processed.contains(k)) continue; if (twoSum.containsKey(target - k)) { processed.add(k); if (target == k << 1) { for (int[] node1 : twoSum.get(k)) { for (int[] node2 : twoSum.get(k)) { if (node2 != node1) { process(node1, node2, hash); } } } } else { processed.add(target - k); List<int[]> list1 = twoSum.get(k); List<int[]> list2 = twoSum.get(target - k); for (int[] node1 : list1) { for (int[] node2 : list2) { process(node1, node2, hash); } } } } } return result; } private void process(int[] a, int[] b, HashMap<Integer, Integer> map) { int[] sum = new int[] { a[0], a[1], b[0], b[1] }; Arrays.sort(sum); StringBuilder sb = new StringBuilder(); Map<Integer, Integer> cloneMap = (HashMap<Integer, Integer>) map .clone(); for (int i = 0; i < 4; i++) { sb.append(sum[i]); cloneMap.put(sum[i], cloneMap.get(sum[i]) - 1); if (cloneMap.get(sum[i]) < 0) return; } if (!duplicate.contains(sb.toString())) { duplicate.add(sb.toString()); List<Integer> list = new ArrayList<Integer>(); for(int i = 0; i < 4; list.add(sum[i++])); result.add(list); } }
相关推荐
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题解之Path Sum III.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