# 引言
题目链接：https://leetcode.com/problems/4sum/description/
# 题目大意
给出一个包含 n 个整数的数组 nums 以及一个目标值 target, 这个数组是否存在有元素 a,b,c,d 使得 a + b + c + d = target , 找出所有满足条件的 a,b,c,d 的组合
- Example
Given array nums = [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]
]
# 题解
这题其实是第 15 题的变种，相信看了这篇题解举一反三很容易能拿下这题，LeetCode:15.3Sum 题解，Click Here!
这道题由于是求 4 个数的目标值，所以需要滚动查询的数字由 15 题的两个变成了 3 个，很暴力的一个方法，在原来的循环上再加一层循环，内部继续再剩余数组上枚举两个数求和即可
Hint:
如何优雅的避免重复也是一个坑，外层两个循环都需要判断下当前选取的数字和上一次是不是相同的，相同的直接跳过，内层俩数字枚举时 2 也注意判断即可 (千万别忘了某一层少写了这个条件，不然美滋滋～)
# 复杂度
时间复杂度 O(n^3)
空间复杂度 O(1)
# AC 代码
c++ 版本
class Solution | |
{ | |
public: | |
vector<vector<int>> fourSum(vector<int> &nums, int target) | |
{ | |
vector<vector<int>> ans; | |
std::sort(nums.begin(), nums.end()); | |
const int len = nums.size(); | |
for (int i = 0; i < len - 3; ++i) | |
{ | |
if (target > 0 && nums[i] > target) | |
{ | |
break; | |
} | |
if (i > 0 && nums[i] == nums[i - 1]) | |
{ | |
continue; | |
} | |
for (int j = i + 1; j < len - 2; ++j) | |
{ | |
if (target > 0 && nums[i] + nums[j] > target) | |
{ | |
break; | |
} | |
if (j > i + 1 && nums[j] == nums[j - 1]) | |
{ | |
continue; | |
} | |
int midIndex = j + 1; | |
int lastIndex = len - 1; | |
while (midIndex < lastIndex) | |
{ | |
int curSum = nums[i] + nums[j] + nums[midIndex] + nums[lastIndex]; | |
if (curSum == target) | |
{ | |
ans.push_back({nums[i], nums[j], nums[midIndex++], nums[lastIndex--]}); | |
while (midIndex < lastIndex && nums[midIndex] == nums[midIndex - 1]) | |
{ | |
++midIndex; | |
} | |
while (midIndex < lastIndex && nums[lastIndex] == nums[lastIndex + 1]) | |
{ | |
--lastIndex; | |
} | |
} | |
else if (curSum > target) | |
{ | |
--lastIndex; | |
} | |
else | |
{ | |
++midIndex; | |
} | |
} | |
} | |
} | |
return ans; | |
} | |
}; |
go 版本
func fourSum(nums []int, target int) [][]int { | |
var ans [][]int | |
lens := len(nums) | |
sort.Sort(sort.IntSlice(nums)) | |
for i := 0; i < lens-3; i++ { | |
if i > 0 && nums[i] == nums[i-1] { | |
continue | |
} | |
for j := i + 1; j < lens-2; j++ { | |
if j > i+1 && nums[j] == nums[j-1] { | |
continue | |
} | |
midIndex, lastIndex := j+1, lens-1 | |
for midIndex < lastIndex { | |
curSum := nums[i] + nums[j] + nums[midIndex] + nums[lastIndex] | |
if curSum == target { | |
ans = append(ans, []int{nums[i], nums[j], nums[midIndex], nums[lastIndex]}) | |
midIndex++ | |
for midIndex < lastIndex && nums[midIndex] == nums[midIndex-1] { | |
midIndex++ | |
} | |
lastIndex-- | |
for midIndex < lastIndex && nums[lastIndex] == nums[lastIndex+1] { | |
lastIndex-- | |
} | |
} else if curSum > target { | |
lastIndex-- | |
} else { | |
midIndex++ | |
} | |
} | |
} | |
} | |
return ans | |
} |
