【leetcode刷题笔记】4Sum
2024-08-27 04:37:15
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,把4Sum问题转换成3Sum,再转换成2Sum,如下图所示:
代码如下:
public class Solution {
public List<List<Integer>> fourSum(int[] num, int target) {
List<List<Integer>> answer = new ArrayList<List<Integer>>();
if(num == null || num.length == 0)
return answer; Arrays.sort(num);
int length = num.length;
for(int i = 0;i < length;i++){
if(i!=0 && num[i]== num[i-1] )
continue;
for(int j = i+1;j < length;j++ ){
if(j != i+1 && num[j] == num[j-1] )
continue;
int start = j + 1;
int last = length - 1;
while(start < last){
int sum = num[i]+num[j]+num[start]+num[last];
if(sum == target){
ArrayList<Integer> result = new ArrayList<Integer>();
result.add(num[i]);
result.add(num[j]);
result.add(num[start]);
result.add(num[last]);
answer.add(result);
start++;
last--;
while(start < last && num[start-1] == num[start])
start++;
}
else if(sum < target){
start++;
}
else {
last--;
}
}
}
}
return answer;
}
}
最新文章
- mac下生成ssh keys 并上传github仓储
- ASP.NET MVC5 网站开发实践(二) Member区域 - 咨询管理的架构
- php面向对象基础
- Java 第十周学习总结
- 暑假前的flag
- 9.20 noip模拟试题
- Vulkan Tutorial 12 Fixed functions
- 【NOIP2015提高组】跳石头
- Struts2学习---拦截器+struts的工作流程+struts声明式异常处理
- 使用Coding Pages托管网站
- java之equals 与 == 的区别
- LeetCode算法题-Kth Largest Element in a Stream(Java实现)
- C# 向程序新建的窗体中添加控件,控件需要先实例化,然后用controls.add添加到新的窗体中去
- Python 每日随笔
- 将txt文本转换为excel格式
- Clion pycharm激活码(可使用到2019年2月)
- Hibernate3.0配置
- 014 再次整理关于hadoop中yarn的原理及运行
- ios成长之每日一遍(day 6)
- UNIX环境编程学习笔记(20)——进程管理之exec 函数族