当前位置:网站首页>【LeetCode】18、四数之和
【LeetCode】18、四数之和
2022-07-06 05:03:00 【小曲同学呀】
题目:
给你一个由 n 个整数组成的数组 nums
,和一个目标值 target
。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]]
(若两个四元组元素一一对应,则认为两个四元组重复):
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
示例 1:
输入:nums = [1,0,-1,0,-2,2], target = 0
输出:[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2:
输入:nums = [2,2,2,2,2], target = 8
输出:[[2,2,2,2]]
提示:
1 <= nums.length <= 200
-10^9 <= nums[i] <= 10 ^9
-10^9 <= target <= 10 ^9
解题思路:
相信大家前面都做过三数之和,那么本题的思路,可以参考三数之和来做,使用双指针。
可以参考一下 三数之和 做个对比,有什么相同点和什么不同点。
因为要用到双指针,所以排序是必须要做的。
还有就是三数之和,四数之和。。。n 数之和等等,本质都是一样的,这次给大家写一个 n数之和,大家可以直接背下,以后再也不怕 n 数之和了。
具体代码:
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
if (nums.length < 4) {
return new LinkedList<>();
}
return nSum(nums, target, 4, 0);
}
// 递归参数:nums,当前目标值target,当前数值的个数n,当前数值的起始索引start
// 返回n数和的列表,即n元组
List<List<Integer>> nSum(int[] nums, long target, int n, int start) {
// 递归的每层都要新建res来传递列表
List<List<Integer>> res = new ArrayList<>();
// 递归的终止层:2数之和
if (n == 2) {
int left = start, right = nums.length - 1;
while (left < right) {
// 剪枝:根据剩下选择闭区间[left, right]里的最小值和最大值剪枝
// 如果由当前left,left+1组成的最小值比target大的话,剩下的left和right就更大了
// 因此直接跳出,遍历i+1
int nMin = nums[left] + nums[left + 1];
if (nMin > target) {
break;
}
// 与nMin同理
int nMax = nums[right] + nums[right - 1];
if (nMax < target) {
break;
}
long sum = nums[left] + nums[right];
if (sum == target) {
List<Integer> row = new LinkedList<>();
row.add(nums[left]);
row.add(nums[right]);
res.add(row);
// 去重2:去除最后两个值的重复
while (left < right && nums[left] == nums[++left]) ;
while (left < right && nums[right] == nums[--right]) ;
} else if (sum < target) {
while (left < right && nums[left] == nums[++left]) ;
} else {
while (left < right && nums[right] == nums[--right]) ;
}
}
}
// 正常递归层:
else {
for (int i = start; i <= nums.length - n; i++) {
// 去重1:去除当前值的重复。当前值和历史值对比,i-1执行过
// 注意,去重若放在代码块前面,就是用if continue 以及i-1和i的形式,
// 若放在后面,就是while i++ 以及 i和i+1的形式
if (i > start && nums[i - 1] == nums[i]) {
continue;
}
// sub接住递归回来的结果
List<List<Integer>> sub = nSum(nums, target - nums[i], n - 1, i + 1);
// // 后序归来后在当前层的操作:res添加sub和当前值
for (List<Integer> row : sub) {
row.add(nums[i]);
res.add(row);
}
// 当前值和历史值对比,放在代码块后面,用i和i+1,因为i执行过
// while (i <= len - n - 1 && nums[i] == nums[i + 1]) {
// i++;
// }
}
}
return res;
}
}
边栏推荐
- 關於Unity Inspector上的一些常用技巧,一般用於編輯器擴展或者其他
- Redis 排查大 key 的4种方法,优化必备
- The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
- Postman pre script - global variables and environment variables
- Bubble sort
- Hyperledger Fabric2. Some basic concepts of X (1)
- win10电脑系统里的视频不显示缩略图
- 比尔·盖茨晒18岁个人简历,48年前期望年薪1.2万美元
- GAMES202-WebGL中shader的編譯和連接(了解向)
- 关于Unity Inspector上的一些常用技巧,一般用于编辑器扩展或者其他
猜你喜欢
Building intelligent gray-scale data system from 0 to 1: Taking vivo game center as an example
Pagoda configuration mongodb
趋势前沿 | 达摩院语音 AI 最新技术大全
Weng Kai C language third week 3.1 punch in
idea一键导包
Golang -- TCP implements concurrency (server and client)
麦斯克电子IPO被终止:曾拟募资8亿 河南资产是股东
比尔·盖茨晒18岁个人简历,48年前期望年薪1.2万美元
[数学建模] 微分方程--捕鱼业的持续发展
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
随机推荐
A little knowledge of CPU, disk and memory
Postman manage test cases
Implementing fuzzy query with dataframe
RT thread analysis - object container implementation and function
Yolov5 tensorrt acceleration
[buuctf.reverse] 159_ [watevrCTF 2019]Watshell
Ad20 is set with through-hole direct connection copper sheet, and the bonding pad is cross connected
idea一键导包
Building intelligent gray-scale data system from 0 to 1: Taking vivo game center as an example
麥斯克電子IPO被終止:曾擬募資8億 河南資產是股東
Class inheritance in yyds dry inventory C
2021 robocom world robot developer competition - undergraduate group (semi-finals)
Leetcode 186 Flip the word II in the string (2022.07.05)
Codeforces Round #804 (Div. 2)
Idea one key guide package
Weng Kai C language third week 3.1 punch in
Lepton 无损压缩原理及性能分析
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
关于es8316的音频爆破音的解决
Drive development - the first helloddk