AlgoPressAppearance
0018-四数之和
https://leetcode.cn/problems/4sum
给你一个由 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
思路
仿照三数之和，多一层循环，4重指针
https://leetcode.cn/problems/4sum/solution/si-shu-zhi-he-by-leetcode-solution/
注意去重的时候，最后两个指针，只有sum满足条件的时候才能去重，不能遍历到一个相同的数就去重
参考代码
csharp
public class Solution {
public IList<IList<int>> FourSum(int[] nums, int target) {
List<IList<int>> result = new List<IList<int>>();
Array.Sort(nums);
//四个指针，最后两个往中间夹
for(int i=0; i<nums.Length - 3; i++){
if(i>0 && nums[i] == nums[i-1]){
//跳过相同的数
continue;
}
for(int j=i+1; j<nums.Length - 2; j++){
if(j>i+1 && nums[j] == nums[j-1]){
//跳过第二个相同的数
continue;
}
//设置左右指针
int left = j+1;
int right = nums.Length - 1;
//Console.WriteLine("calc {0} {1} {2} {3}",i,j,left,right);
while(left < right){
//使用long防止溢出
long sum = (long)nums[i] + (long)nums[j] + (long)nums[left] + (long)nums[right];
if(sum > target){ //如果和大于0，说明需要减少,right左移
right--;
}
else if(sum < target){
left++;
}
else{
//说明相等：加入结果集 并且同时移动两边指针
//同时移动两边指针是因为，移动一边之后，如果是同样的数字应该是跳过的，不同的数字后，sum肯定不会为0，所以要移动另外一边，才有可能sum为0
List<int> list = new List<int>();
list.Add(nums[i]);
list.Add(nums[j]);
list.Add(nums[left]);
list.Add(nums[right]);
result.Add(list);
//去除右边重复数字
while(left < right && nums[right-1] == nums[right]){
right--;
}
//去除左边重复的数字
while(left < right && nums[left+1] == nums[left]){
left++;
}
left++;
right--;
}
}
}
}
return result;
}
}