四数之和：解决数组中的四元组问题

一、排序数组

在对数组进行操作之前，我们需要先对其进行排序：

Array.Sort(nums);

排序数组有助于简化双指针技术的实施，并且可以轻松跳过重复元素。

二、四数之和算法实现

以下是 FourSum 方法的实现，该方法用于找到数组中所有和为目标值的唯一四元组：

public IList<IList<int>> FourSum(int[] nums, int target)
{
    var res = 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 low = j + 1; // 初始化低位指针
            int high = nums.Length - 1; // 初始化高位指针

            // 使用双指针技术寻找剩下的两个元素
            while (low < high)
            {
                // 计算当前四元组的和
                long sum = (long)nums[i] + (long)nums[j] + (long)nums[low] + (long)nums[high];

                // 如果和等于目标值，则将四元组添加到结果列表中
                if (sum == target)
                {
                    res.Add(new List<int> { nums[i], nums[j], nums[low], nums[high] });

                    // 跳过重复的元素
                    while (low < high && nums[low] == nums[low + 1]) low++;
                    while (low < high && nums[high] == nums[high - 1]) high--;

                    // 移动指针继续寻找其他四元组
                    low++;
                    high--;
                }
                // 如果和小于目标值，则移动低位指针以增加和
                else if (sum < target)
                {
                    low++;
                }
                // 如果和大于目标值，则移动高位指针以减少和
                else
                {
                    high--;
                }
            }
        }
    }

    return res; // 返回结果列表
}

三、时间复杂度分析

算法的时间复杂度主要由以下几个部分组成：

（一）排序数组

排序数组的时间复杂度为 (O(n \log n))。

（二）嵌套循环

外层和中层循环的复杂度分别为 (O(n)) 和 (O(n^2))，因此两层循环的总复杂度为 (O(n^3))。

（三）双指针技术

对于每一对由外层和中层循环确定的元素，双指针技术在 (O(n)) 时间内完成搜索。

综合以上分析，整个算法的时间复杂度为 (O(n^3))。这意味着算法在元素数量适中的数组上表现良好，但对于非常大的数组可能会变得较慢。

通过上述方法，我们可以有效地找到数组中所有和为目标值的唯一四元组。