力扣第18题. 四数之和

题目：

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例：给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

Python3解答代码：

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        # 排序nums数组
        nums.sort()
        # 初始化变量,初始化一个空列表result用于存储结果
        n = len(nums)
        result = []

        # 循环每个可能作为四元组的第一个数字nums[i]
        for i in range(n):
            # 如果 nums[i] 大于 target 并且都为正数，后续元素只会更大，就可以提前结束当前循环，
            # 因为不可能存在四个数的和等于 target
            if nums[i] > target and nums[i] > 0 and target > 0:
                break
            # 第一层循环中的元素 nums[i]，如果当前元素与前一个元素相同，则直接跳过，避免重复计算
            if i > 0 and nums[i] == nums[i-1]:
                continue
            # 内层循环遍历每个可能作为四元组第二个数字的 nums[j]
            for j in range(i+1, n):
                if nums[i] + nums[j] > target and target > 0:
                    break
                # 跳过相同的 nums[j] 值以避免重复的四元组。
                if j > i+1 and nums[j] == nums[j-1]:
                    continue
                
                # 确定两个数之后，使用双指针来查找后两个数，使得四数之和等于target、
                left,right = j+1, n-1
                while left < right:
                    # 计算选中的四个数之和s
                    s = nums[i] + nums[j] + nums[left] + nums[right]
                    if s == target:
                        result.append([nums[i], nums[j], nums[left], nums[right]])
                        # 为了避免重复的四元组，需要移动left和right来跳过重复的元素
                        # 只要 left 指向的元素与其右边相邻的元素相同，就继续向右移动 left 指针
                        while left < right and nums[left] == nums[left+1]:
                            left += 1
                        # 只要 right 指向的元素与其左边相邻的元素相同，就继续向左移动 right 指针
                        while left < right and nums[right] == nums[right-1]:
                            right -= 1
                        # 完成上述循环后，需要将 left 和 right 分别再向中间移动一位，
                        # 以避免重复计算当前的组合
                        left += 1
                        right -= 1
                    #  四数之和小于目标值，需要将left指针向右移动
                    elif s < target:
                        left += 1
                    # 四数之和大于目标值,为了减少和的大小
                    # 需要将 right 指针向左移动，即向更小的数移动
                    else:
                         right -= 1

        return result

上述代码实现过程解析：

上述代码实现了在给定整数数组 nums 中找出所有四个元素的组合，使得它们的和等于目标值 target。下面是代码的详细解释：

排序数组：首先，对输入的整数数组 nums 进行排序。这样做的目的是为了在后续的处理中能更方便地进行去重和剪枝操作。
初始化变量：获取数组的长度 n，并初始化一个空列表 result 用于存储结果。
遍历数组：使用两层循环遍历数组，首先固定两个数 nums[i] 和 nums[j]，其中 i 和 j 分别表示第一层循环和第二层循环的索引。这两个数将作为四个元素中的前两个。
剪枝操作：在第一层循环中，有两处剪枝操作：
- 如果当前的 nums[i] 大于 target 并且都为正数，就可以提前结束当前循环，因为后续元素只会更大，不可能满足条件。
- 在第二层循环中，如果当前的 nums[i] + nums[j] 大于 target 并且 target 为正数，同样可以提前结束当前循环。
去重操作：**在每一层循环中，都需要进行去重操作，以避免重复的组合被计算。具体做法是：
- 对于第一层循环中的元素 nums[i]，如果当前元素与前一个元素相同，则直接跳过，避免重复计算。
- 对于第二层循环中的元素 nums[j]，如果当前元素与前一个元素相同，则直接跳过，避免重复计算。
双指针法找到剩余两个数：**在固定了前两个数后，剩余的两个数采用双指针法。定义两个指针 left 和 right 分别指向当前范围内的最左和最右的元素。然后循环移动这两个指针，不断调整它们指向的元素，直到找到符合条件的组合或者两个指针相遇。
判断条件和更新指针：
- 如果四个数的和等于目标值 target，则将这个组合添加到结果列表 result 中，并同时更新指针 left 和 right，以避免重复计算相同的组合。
- 如果四个数的和小于目标值 target，则将左指针 left 右移一位。
- 如果四个数的和大于目标值 target，则将右指针 right 左移一位。
返回结果：最终返回结果列表 result，其中存储了所有满足条件的四个元素的组合。

重难点解释：

1.剪枝操作：

"剪枝"指的是在搜索过程中通过一些条件判断提前结束不必要的搜索分支，从而减少搜索空间，提高算法效率。具体来说，这段代码中的剪枝操作有两个地方：

在第一层循环和第二层循环中，通过比较当前元素与目标值的大小关系，如果可以确定后续元素无法满足条件，就提前结束当前循环。例如，在第一层循环中，如果 nums[i] 大于 target 并且都为正数，后续元素只会更大，就可以提前结束当前循环，因为不可能存在四个数的和等于 target。
在第二层循环中，通过比较当前两个元素的和与目标值的大小关系，同样可以提前结束当前循环。如果 nums[i] + nums[j] 大于 target 并且 target 为正数，后续元素只会更大，也可以提前结束当前循环。

2.if j > i+1 and nums[j] == nums[j-1]: continue 解释为啥是i+1

这段代码的意图是在固定了第一个数字 nums[i] 后，跳过那些可能会导致重复四元组的第二个数字 nums[j]。这里的逻辑是：

j > i+1：这个条件用于确保 j 不仅仅是在 i+1 的位置上，也就是说，j 应该至少是从 i+2 的位置开始考虑。这是因为：
- 当 j == i+1 时，nums[j] 是在 nums[i] 后面的第一个元素，此时没有前一个元素 nums[j-1] 与之相比较，因此不需要进行去重判断。
- 当 j > i+1 时，表示 j 至少是第三个考虑的元素，此时 nums[j-1] 存在，并且位于 nums[j] 之前，因此可以进行重复检查。
nums[j] == nums[j-1]：这个条件检查当前的元素 nums[j] 是否与它前一个元素 nums[j-1] 相等。如果相等，说明使用当前的 nums[j] 可能会生成与前一个循环相同的四元组，因此应该跳过当前的 nums[j]。

目的和重要性

防止重复结果：如果不进行这样的去重，相同的 nums[j] 值将在内层循环中多次使用，与同一个 nums[i] 结合，可能会导致生成重复的四元组。
提高效率：通过跳过重复元素，可以减少不必要的计算和迭代，这对于处理大数据集时尤为重要。

3.核心代码解释：

if nums[i] + nums[j] > target and target > 0:
    break

限制 target > 0 的原因主要是为了确保当目标值 target 是正数时，这个剪枝逻辑才会生效。这样的条件设定对于整体算法的正确性和效率都有影响，以下是几个关键点：

1. 保证剪枝的适用性

当 target 是正数时，如果两个数的和已经超过了 target，继续在正数范围内添加更多的数会使得总和进一步增加，从而不可能等于 target。这个逻辑在 target 是正数时显然有效。

2. 处理负数情况

如果 target 是负数或零，上述剪枝条件可能不适用，因为：

当 target 是零或负数时，可能需要包括负数在内的组合来达到 target。即使当前的两数之和已经超过了 target，通过选择负数作为其他组成部分，仍然有可能将总和调整至 target。
对于负 target，若当前两数之和大于 target，但它们之间存在足够大的负数，这些负数仍然可以使得最终的四数之和等于 target。

3. 避免不必要的逻辑应用

如果不加 target > 0 这个条件，那么对于负数 target 或 target 为零的情况，剪枝可能导致漏掉有效的解。例如，假设 target = -10，如果仅仅因为两个正数的和大于 -10 就停止搜索，可能会错过一些包含负数且其和为 -10 的有效组合。

解释一下这个几句代码的实现：

 while left < right and nums[left] == nums[left+1]:
                            left += 1
                        while left < right and nums[right] == nums[right-1]:
                            right -= 1
                        left += 1
                        right -= 1
                    elif s < target:
                        left += 1
                    else:
                        right -= 1
        return result

代码位于双指针搜索的环节，用于在已经固定了两个数字之后，在数组的剩余部分中寻找两个数，使得这四个数的和等于给定的目标 target。这一部分是通过移动左指针 left 和右指针 right 来实现的。下面是详细的逻辑解释：

判断当前四数之和 `s`

s = nums[i] + nums[j] + nums[left] + nums[right]

首先计算当前选定的四个数的和 s，并将其与目标 target 进行比较。

判断三种情况

四数之和等于目标值 (s == target)：
- 将符合条件的四元组 [nums[i], nums[j], nums[left], nums[right]] 添加到结果列表 result 中。
- 接下来，为了避免重复的四元组，需要移动 left 和 right 指针来跳过所有相同的元素。
- ```
while left < right and nums[left] == nums[left+1]:
    left += 1
while left < right and nums[right] == nums[right-1]:
    right -= 1
left += 1
right -= 1
```
- - 这两个 while 循环分别用于：
  - 完成上述循环后，需要将 left 和 right 分别再向中间移动一位，以避免重复计算当前的组合。
  - 跳过右边重复的元素：只要 right 指向的元素与其左边相邻的元素相同，就继续向左移动 right 指针。
  - 跳过左边重复的元素：只要 left 指向的元素与其右边相邻的元素相同，就继续向右移动 left 指针。
四数之和小于目标值 (s < target)：
- 为了增加和的大小，需要将 left 指针向右移动，即向更大的数移动。
  - ```
  left += 1
```
四数之和大于目标值 (s > target)：
- 为了减少和的大小，需要将 right 指针向左移动，即向更小的数移动。