当前位置:网站首页>[leetcode] 18. Sum of four numbers
[leetcode] 18. Sum of four numbers
2022-07-06 05:09:00 【Xiaoqu classmate】
subject :
Here you are n An array of integers nums
, And a target value target
. Please find and return the quads that meet all the following conditions and are not repeated [nums[a], nums[b], nums[c], nums[d]]
( If two Quad elements correspond to each other , It is considered that two quads repeat ):
0 <= a, b, c, d < n
a、b、c and d Different from each other
nums[a] + nums[b] + nums[c] + nums[d] == target
You can press In any order Return to the answer .
Example 1:
Input :nums = [1,0,-1,0,-2,2], target = 0
Output :[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Example 2:
Input :nums = [2,2,2,2,2], target = 8
Output :[[2,2,2,2]]
Tips :
1 <= nums.length <= 200
-10^9 <= nums[i] <= 10 ^9
-10^9 <= target <= 10 ^9
Their thinking :
I believe you have done the sum of three numbers before , So the idea of this topic , You can refer to the sum of three numbers , Use double pointer .
You can refer to it Sum of three numbers Make a comparison , What are the similarities and differences .
Because we need to use double pointers , So sorting is a must .
There is also the sum of three numbers , Sum of four numbers ...n Sum of numbers and so on , It's the same thing , This time I'll write you a n Sum of the numbers , You can recite it directly , I'll never be afraid again n The sum of the numbers .
Specific code :
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);
}
// Recursive parameters :nums, Current target value target, Number of current values n, The starting index of the current value start
// return n A list of numbers and , namely n Tuples
List<List<Integer>> nSum(int[] nums, long target, int n, int start) {
// Every layer of recursion should be created res To pass the list
List<List<Integer>> res = new ArrayList<>();
// The termination layer of recursion :2 Sum of the numbers
if (n == 2) {
int left = start, right = nums.length - 1;
while (left < right) {
// prune : Select the closed interval according to the rest [left, right] Prune the minimum and maximum values in
// If from the current left,left+1 The minimum value ratio of composition target Big words , The rest left and right It's even bigger
// So jump out , Traverse i+1
int nMin = nums[left] + nums[left + 1];
if (nMin > target) {
break;
}
// And nMin Empathy
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);
// duplicate removal 2: Remove the repetition of the last two values
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]) ;
}
}
}
// Normal recursion layer :
else {
for (int i = start; i <= nums.length - n; i++) {
// duplicate removal 1: Remove the repetition of the current value . Comparison between current value and historical value ,i-1 Executed
// Be careful , If de duplication is placed in front of the code block , Just use if continue as well as i-1 and i In the form of ,
// If put in the back , Namely while i++ as well as i and i+1 In the form of
if (i > start && nums[i - 1] == nums[i]) {
continue;
}
// sub Catch the result of recursion
List<List<Integer>> sub = nSum(nums, target - nums[i], n - 1, i + 1);
// // After the sequence returns, the operation on the current layer :res add to sub And the current value
for (List<Integer> row : sub) {
row.add(nums[i]);
res.add(row);
}
// Comparison between current value and historical value , Put it after the code block , use i and i+1, because i Executed
// while (i <= len - n - 1 && nums[i] == nums[i + 1]) {
// i++;
// }
}
}
return res;
}
}
边栏推荐
- 趋势前沿 | 达摩院语音 AI 最新技术大全
- Acwing week 58
- Yyds dry inventory SSH Remote Connection introduction
- What should the project manager do if there is something wrong with team collaboration?
- acwing周赛58
- The kernel determines whether peripherals are attached to the I2C address
- RT thread analysis log system RT_ Kprintf analysis
- The underlying structure of five data types in redis
- On the solution of es8316's audio burst
- MySQL time processing
猜你喜欢
ISP学习(2)
行业专网对比公网,优势在哪儿?能满足什么特定要求?
JS quick start (II)
Bill Gates posted his 18-year-old resume and expected an annual salary of $12000 48 years ago
【LGR-109】洛谷 5 月月赛 II & Windy Round 6
Postman管理测试用例
Cve-2019-11043 (PHP Remote Code Execution Vulnerability)
Codeforces Round #804 (Div. 2)
Application of Flody
F12 solve the problem that web pages cannot be copied
随机推荐
Hometown 20 years later (primary school exercises)
February 12 relativelayout
EditorUtility. The role and application of setdirty in untiy
Flody的应用
Talking about the type and function of lens filter
麦斯克电子IPO被终止:曾拟募资8亿 河南资产是股东
【OSPF 和 ISIS 在多路访问网络中对掩码的要求】
acwing周赛58
Implementing fuzzy query with dataframe
MySQL time processing
集合详解之 Map + 面试题
Fuzzy -- basic application method of AFL
驱动开发——第一个HelloDDK
Bill Gates posted his 18-year-old resume and expected an annual salary of $12000 48 years ago
比尔·盖茨晒18岁个人简历,48年前期望年薪1.2万美元
Building intelligent gray-scale data system from 0 to 1: Taking vivo game center as an example
Nestjs配置文件上传, 配置中间件以及管道的使用
[lgr-109] Luogu may race II & windy round 6
flutter 实现一个有加载动画的按钮(loadingButton)
Postman断言