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
你可以按 任意顺序 返回答案 。
示例一：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例二：
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]
提示：
1 <= nums.length <= 200-109 <= nums[i] <= 109-109 <= target <= 109
【算法设计思想】
解决这类问题的主要思想基本都是排序+双指针。在解决四数之和这个问题时，我们可以仿照三数之和，再在外面加上一层for循环，然后再进行相同的处理即可。
对于三数之和，详见
【算法描述】
C++:
class Solution {
public:
// 定义一个方法 fourSum，接收一个整数向量 nums 和一个整数目标值 target
vector<vector<int>> fourSum(vector<int>& nums, int target) {
// 首先对输入的整数向量进行排序
sort(nums.begin(), nums.end());
// 初始化结果向量，用于存放所有满足条件的四元组
vector<vector<int>> ans;
// 遍历整个数组
for (int i = 0; i < nums.size(); i++) {
// 如果当前元素与前一个元素相同，则跳过此次循环，避免重复计算
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// 内层循环遍历数组中剩余的部分
for (int j = i + 1; j < nums.size(); j++) {
// 同样地，如果当前元素与前一个元素相同，则跳过此次循环
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
// 定义两个指针 l 和 r，分别指向当前内层循环起始位置的下一个元素和数组的最后一个元素
int l = j + 1, r = nums.size() - 1;
// 计算剩余两个元素需要达到的目标和
int sum = target - nums[i] - nums[j];
// 双指针法查找符合条件的另外两个数
while (l < r) {
if (nums[l] + nums[r] == sum) {
// 当找到符合条件的一组解时，将其添加到结果向量中
ans.push_back({nums[i], nums[j], nums[l], nums[r]});
// 移动指针，并跳过重复的元素
while (l < r && nums[l] == nums[l + 1]) {
l++;
}
while (l < r && nums[r] == nums[r - 1]) {
r--;
}
// 更新指针的位置
l++;
r--;
} else if (nums[l] + nums[r] < sum) {
// 如果当前和小于目标和，则移动左指针 l 往右
l++;
} else {
// 如果当前和大于目标和，则移动右指针 r 往左
r--;
}
}
}
}
// 返回所有找到的四元组组合
return ans;
}
};
Java:
public class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
// 对输入的整型数组进行排序
Arrays.sort(nums);
int n = nums.length;
List<List<Integer>> ans = new ArrayList<>();
// 遍历数组中的每一个元素作为第一个数
for (int i = 0; i < n; i++) {
// 如果当前元素与前一个元素相同，跳过以避免重复解
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// 内层循环遍历第二个数
for (int j = i + 1; j < n; j++) {
// 如果当前元素与前一个元素相同，跳过以避免重复解
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
// 初始化两个指针，分别从当前元素的下一个位置和数组末尾开始
int l = j + 1;
int r = n - 1;
// 当左指针小于右指针时执行循环
while (l < r) {
// 计算当前四个数的和
long sum = (long)nums[i] + nums[j] + nums[l] + nums[r];
// 如果和等于目标值，则将这四个数作为一个解决方案加入答案列表
if (sum == target) {
ans.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));
// 移动左右指针并跳过重复元素
while (l < r && nums[l] == nums[l + 1]) {
l++;
}
while (l < r && nums[r] == nums[r - 1]) {
r--;
}
// 更新指针位置
l++;
r--;
} else if (sum < target) {
// 如果总和小于目标值，则移动左指针尝试更大的数
l++;
} else {
// 如果总和大于目标值，则移动右指针尝试更小的数
r--;
}
}
}
}
// 返回所有找到的组合
return ans;
}
}
Python:
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
# 对数组进行排序
nums.sort()
# 初始化结果列表
ans = []
# 获取数组长度
n = len(nums)
# 遍历数组中的每一个元素作为第一个数
for i in range(n):
# 跳过重复元素以避免重复解
if i > 0 and nums[i] == nums[i - 1]:
continue
# 内层循环遍历第二个数
for j in range(i + 1, n):
# 同样跳过重复元素
if j > i + 1 and nums[j] == nums[j - 1]:
continue
# 初始化两个指针
l = j + 1
r = n - 1
# 当左指针小于右指针时执行循环
while l < r:
# 计算当前四个数的和
sum = nums[l] + nums[r]
if sum + nums[i] + nums[j] == target:
# 如果和等于目标值，则添加到结果列表中
ans.append([nums[i], nums[j], nums[l], nums[r]])
# 移动左右指针并跳过重复元素
while l < r and nums[l] == nums[l + 1]:
l += 1
while l < r and nums[r] == nums[r - 1]:
r -= 1
# 更新指针位置
l += 1
r -= 1
elif sum + nums[i] + nums[j] < target:
# 如果总和小于目标值，则移动左指针尝试更大的数
l += 1
else:
# 如果总和大于目标值，则移动右指针尝试更小的数
r -= 1
# 返回所有找到的组合
return ans