| 2024-04-19 |

# 四数之和

随笔：四数之和相比三数之和多了很多细节比如要多套一层循环去重复的时候要 while 遍历防止没有去除干净此外还要考虑如 target 是任意值。比如：数组是 [-4, -3, -2, -1] ， target 是 -10 ，不能因为 -4 > -10 而跳过

# 题目

给你一个由 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：
1
2
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
1
2
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]
提示：

1 <= nums.length <= 200

-109 <= nums[i] <= 109

-109 <= target <= 109

# 题解

public class Solution 
{
    public IList<IList<int>> FourSum(int[] nums, int target) 
    {
        IList<IList<int>> result = new List<IList<int>>();
        //先对nums进行排序
        Array.Sort(nums);

        for(int i=0;i<nums.Length;i++)
        {
            //剪枝处理   target是任意值。比如：数组是[-4, -3, -2, -1]，target是-10，不能因为-4 > -10而跳过
            if (nums[i] > target && nums[i] >= 0) {
            	break; // 这里使用break，统一通过最后的return返回
            }
            
            if(i > 0 && nums[i] == nums[i-1])
            {
                continue;
            }
            //这里从i+1开始 因为是二重遍历 i在上面已经走完了
            for(int j= i+1;j<nums.Length;j++)
            {

                if(nums[j] + nums[i] > target && nums[j] + nums[i] >= 0)
                {
                    break;
                }

                //去除重复
                if(j>i+1 && nums[j] == nums[j-1])
                {
                    continue;
                }
                int left = j+1;
                int right = nums.Length -1;
                while(left < right)
                {
                    //判定
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if(sum < target)
                    {
                        left++;
                    }
                    else if(sum > target){
                        right--;
                    }
                    else{

                        result.Add(new List<int>{nums[i],nums[j],nums[left],nums[right]});
                        //去除重复 这里去重要重复遍历 因为多套了一层循环
                        while(left < right && nums[left] == nums[left+1])
                            left++;
                        while(left < right && nums[right] == nums[right-1])
                            right--;

                        left++;
                        right--;
                    }
                }
            }
        }
        return result;
    }
}

这类题目对于双指针法的锻炼还是挺有效果的，在实际项目中，可以理解如何将复杂度 n^2 的算法降低一层

tags: #算法