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)
[分析] 3Sum的扩展,在3Sum外面再加一层循环,注意去重处理。
public class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (nums == null || nums.length < 4)
return result;
Arrays.sort(nums);
int N = nums.length;
for (int i = 0; i < N - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1])
continue;
for (int j = i + 1; j < N - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1])
continue;
int p = j + 1, q = N - 1;
while (p < q) {
int sum4 = nums[i] + nums[j] + nums[p] + nums[q];
if (sum4 == target) {
List<Integer> item = new ArrayList<Integer>();
item.add(nums[i]);
item.add(nums[j]);
item.add(nums[p]);
item.add(nums[q]);
result.add(item);
while (++p < q && nums[p] == nums[p - 1]);
while (p < --q && nums[q] == nums[q + 1]);
} else if (sum4 > target) {
while (p < --q && nums[q] == nums[q + 1]);
} else {
while (++p < q && nums[p] == nums[p - 1]);
}
}
}
}
return result;
}
}
分享到:
相关推荐
主要介绍了LeetCode -- Path Sum III分析及实现方法的相关资料,希望通过本文能帮助到大家,需要的朋友可以参考下
001.two-sum │ ├── information.json │ ├── README.md ├── 002.add-two-numbers │ ├── information.json │ ├── README.md ... 有一些有用的选项: Options: -r, --rule crawling rule, ...
vscode安装leetcode leetcode-js-tdd leetcode 勇士的简单样板 如何使用 克隆这个 repo 在你的 vscode 中安装 配置扩展以使用 repo 中的problems文件夹 使用1.two-sum.js案例导出解决方案 module . exports = { // ...
离线和leetcode leetcode-cli 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的网站!...⦙⦙⦙⦙⦙⦙⦙⦙ ...'[3,2,4]\n7' Submit final solution! $ leetcode submit ./two-sum.cpp
离线和leetcode leetcode-cli 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的网站!...⦙⦙⦙⦙⦙⦙⦙⦙ ...'[3,2,4]\n7' Submit final solution! $ leetcode submit ./two-sum.cpp
leetcode 答案 leetcode-machine-swift :SOS_button: 请帮助在Sources/leetcode-machine-swift/leetcode.swift设置所有 leetcode 问题。 :SOS_button: 在 ...利用自动补全、类型检查......Sum " , inputs : [([ 2 , 7
js代码-1. 两数之和 [简单] https://leetcode-cn.com/problems/two-sum
https://leetcode-cn.com/problems/two-sum/ 难度 : 简单 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。...
leetcode 只专注于解决方案! leetcode-helper是一个单 jar 库,它使您无需为每个问题设置解决方案测试脚手架。 生成解决方案/测试框架,编译,通过一行命令进行测试。 集成了Junit ...two_sum/ │ └──
leetcode 2 leetcode-训练 算法训练。 java $: javac hello.java java $: java hello c $: gcc hello.c 如果没有错误会生成a.out 可执行文件 c $: ./a.out leetcode cli leetcode version leetcode help leetcode ...
leetcode编辑器leetcode-问题 自定义代码演示 leetcode 编辑器配置 代码文件名: $ ! velocityTool . camelCaseName(${question ...com.shuzijun.leetcode.editor.en ...Sum ${question.titleSlug} question t
-4] 示例输出: [ [-1, 0, 1], [-1, -1, 2] ] 首先,我最自然的想法是简单地搜索给定数组中 3 个数字的所有可能组合,并找出满足请求的组合。 这该怎么做? 我们将遍历数组中的每个元素,对于每个元素,我们将搜索其...
leetcode-1-Two-Sum 这是我在 Github 的第一天。 我只是 AC leetcode 中的第一个问题。 从现在开始,我将使用Github在leetcode中记录我的生活。 我擅长 C++,但对 java 和 Python 不是很专业,我将使用最流行的 3 种...
sum: 39, 40, 216 - palindrome partitioning - regex - sudoku solver: 37 排序 - merge sort - quick sort - insertion sort - selection sort - counting sort 位操作 - find the only element which exists once...
leetcode 答案 leetcode-solution (Hot 100) leetcode 1. 两数之和题解 /** * @param {number[]} nums * @param {number} target * @return {number[]} */ // 时间复杂度为O(n^2),空间复杂度为O(1). var twoSum = ...
4sum 中等的 从排序数组中删除重复项 简单的 删除元素 简单的 最大子阵列 简单的 移零 简单的 斐波那契数 简单的 拥有最多糖果的孩子 简单的 回溯 题号 题目 难度 电话号码的字母组合 中等的 组合和 中等的 组合和II...
leetcode 答案力码 API 使用 TypeScript 编写的 Leetcode ..."two-sum" ) ; // Fetch more properties of this problem await problem . detail ( ) ; // Show problem content, test case, code snippet
leetcode java 常用只专注于解决方案! leetcode-helper是一个单 jar 库,它使您无需为每个问题设置解决方案测试脚手架。 生成解决方案/测试框架,编译,通过一行命令进行测试。 集成了Junit ...two_sum/ │
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_...
leetcode双人赛Leetcode-火车 1. class Solution { public int[] twoSum(int[] nums, int target) { Map table = new HashMap<>(); for (int i = 0; i < nums.length; i++){ table.put(nums[i], i); } int [] ...