文章目录
18. 四数之和：
定制开发给你一个由 n 定制开发个整成的数组 nums ，定制开发和一个目标值 target 。定制开发请你找出并返回满足下述全部条件且不重复的四 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < na、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]]- 1
- 2
- 3
- 4
- 5
样例 2：
输入： nums = [2,2,2,2,2], target = 8 输出： [[2,2,2,2]]- 1
- 2
- 3
- 4
- 5
提示：
- 1 <= nums.length <= 200
- -109 <= nums[i] <= 109
- -109 <= target <= 109
原题传送门：
分析
- 面对这道算法题目，二当家的陷入了沉思。
- 第一反应就是暴力四层循环，但是据说会超时。
- 如果是两数之和，在知道第一个数的情况下，第二个数也就固定了；
- 四数之和在第一个数固定后，并不能固定第二个数，第三个数和第四个数，所以才需要四层循环。
- 然而如果我们把数组先排序一下，在确定了前两个数之后，后两个数就有了关系，一个数越大，另一个数就需要越小，可以合并成一次循环。
题解
impl Solution { pub fn four_sum(mut nums: Vec<i32>, target: i32) -> Vec<Vec<i32>> { let mut ans = Vec::new(); let n = nums.len(); if n < 4 { return ans; } nums.sort(); for first in 0..n - 3 { if first > 0 && nums[first] == nums[first - 1] { continue; } if nums[first] as i64 + nums[first + 1] as i64 + nums[first + 2] as i64 + nums[first + 3] as i64 > target as i64 { break; } if target as i64 > nums[first] as i64 + nums[n - 3] as i64 + nums[n - 2] as i64 + nums[n - 1] as i64 { continue; } for second in first + 1..n - 2 { if second > first + 1 && nums[second] == nums[second - 1] { continue; } if nums[first] as i64 + nums[second] as i64 + nums[second + 1] as i64 + nums[second + 2] as i64 > target as i64 { break; } if target as i64 > nums[first] as i64 + nums[second] as i64 + nums[n - 2] as i64 + nums[n - 1] as i64 { continue; } let mut fourth = n - 1; let t = target as i64 - nums[first] as i64 - nums[second] as i64; for third in second + 1..n - 1 { if third > second + 1 && nums[third] == nums[third - 1] { continue; } while third < fourth && nums[third] as i64 + nums[fourth] as i64 > t { fourth -= 1; } if third == fourth { break; } if nums[third] as i64 + nums[fourth] as i64 == t { ans.push(vec![nums[first], nums[second], nums[third], nums[fourth]]); } } } } return ans; }}- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
go
func fourSum(nums []int, target int) [][]int { n := len(nums) if n < 4 { return nil } sort.Ints(nums) var ans [][]int for first := 0; first < n-3; first++ { if first > 0 && nums[first] == nums[first-1] { continue } if nums[first]+nums[first+1]+nums[first+2]+nums[first+3] > target { break } if nums[first]+nums[n-3]+nums[n-2]+nums[n-1] < target { continue } for second := first + 1; second < n-2; second++ { if second > first+1 && nums[second] == nums[second-1] { continue } if nums[first]+nums[second]+nums[second+1]+nums[second+2] > target { break } if nums[first]+nums[second]+nums[n-2]+nums[n-1] < target { continue } fourth := n - 1 t := target - nums[first] - nums[second] for third := second + 1; third < n-1; third++ { if third > second+1 && nums[third] == nums[third-1] { continue } for third < fourth && nums[third]+nums[fourth] > t { fourth -= 1 } if third == fourth { break } if nums[third]+nums[fourth] == t { ans = append(ans, []int{nums[first], nums[second], nums[third], nums[fourth]}) } } } } return ans}- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
c++
class Solution {public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> ans; int n = nums.size(); if (n < 4) { return ans; } sort(nums.begin(), nums.end()); for (int first = 0; first < n - 3; ++first) { if (first > 0 && nums[first] == nums[first - 1]) { continue; } if ((long) nums[first] + nums[first + 1] + nums[first + 2] + nums[first + 3] > target) { break; } if ((long) nums[first] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) { continue; } for (int second = first + 1; second < n - 2; ++second) { if (second > first + 1 && nums[second] == nums[second - 1]) { continue; } if ((long) nums[first] + nums[second] + nums[second + 1] + nums[second + 2] > target) { break; } if ((long) nums[first] + nums[second] + nums[n - 2] + nums[n - 1] < target) { continue; } int fourth = n - 1; int t = target - nums[first] - nums[second]; for (int third = second + 1; third < n - 1; ++third) { if (third > second + 1 && nums[third] == nums[third - 1]) { continue; } while (third < fourth && nums[third] + nums[fourth] > t) { fourth -= 1; } if (third == fourth) { break; } if (nums[third] + nums[fourth] == t) { ans.push_back({nums[first], nums[second], nums[third], nums[fourth]}); } } } } return ans; }};- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
java
class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> ans = new ArrayList<>(); int n = nums.length; if (n < 4) { return ans; } Arrays.sort(nums); for (int first = 0; first < n - 3; ++first) { if (first > 0 && nums[first] == nums[first - 1]) { continue; } if ((long) nums[first] + nums[first + 1] + nums[first + 2] + nums[first + 3] > target) { break; } if ((long) nums[first] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) { continue; } for (int second = first + 1; second < n - 2; ++second) { if (second > first + 1 && nums[second] == nums[second - 1]) { continue; } if ((long) nums[first] + nums[second] + nums[second + 1] + nums[second + 2] > target) { break; } if ((long) nums[first] + nums[second] + nums[n - 2] + nums[n - 1] < target) { continue; } int fourth = n - 1; int t = target - nums[first] - nums[second]; for (int third = second + 1; third < n - 1; ++third) { if (third > second + 1 && nums[third] == nums[third - 1]) { continue; } while (third < fourth && nums[third] + nums[fourth] > t) { fourth -= 1; } if (third == fourth) { break; } if (nums[third] + nums[fourth] == t) { ans.add(Arrays.asList(nums[first], nums[second], nums[third], nums[fourth])); } } } } return ans; }}- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
python
class Solution: def fourSum(self, nums: List[int], target: int) -> List[List[int]]: ans = list() n = len(nums) if n < 4: return ans nums.sort() for first in range(n - 3): if first > 0 and nums[first] == nums[first - 1]: continue if nums[first] + nums[first + 1] + nums[first + 2] + nums[first + 3] > target: break if nums[first] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target: continue for second in range(first + 1, n - 2): if second > first + 1 and nums[second] == nums[second - 1]: continue if nums[first] + nums[second] + nums[second + 1] + nums[second + 2] > target: break if nums[first] + nums[second] + nums[n - 2] + nums[n - 1] < target: continue fourth = n - 1 t = target - nums[first] - nums[second] for third in range(second + 1, n - 1): if third > second + 1 and nums[third] == nums[third - 1]: continue while third < fourth and nums[third] + nums[fourth] > t: fourth -= 1 if third == fourth: break if nums[third] + nums[fourth] == t: ans.append([nums[first], nums[second], nums[third], nums[fourth]]) return ans- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 博客原创~