【LeetCode刷题笔记（7-2）】【Python】【四数之和】【双指针】【中等】

四数之和

引言

编写通过所有测试案例的代码并不简单，通常需要深思熟虑和理性分析。虽然这些代码能够通过所有的测试案例，但如果不了解代码背后的思考过程，那么这些代码可能并不容易被理解和接受。我编写刷题笔记的初衷，是希望能够与读者们分享一个完整的代码是如何在逐步的理性思考下形成的。我非常欢迎读者的批评和指正，因为我知道我的观点可能并不完全正确，您的反馈将帮助我不断进步。如果我的笔记能给您带来哪怕是一点点的启示，我也会感到非常荣幸。同时，我也希望我的分享能够激发您的灵感和思考，让我们一起在编程的道路上不断前行~

四数之和

题目描述

给你一个由 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⁹ <= nums[i] <= 10⁹
• -10⁹ <= target <= 10⁹

解决方案3：【排序】+【双指针】

在探讨【四数之和】这一算法题之前，我相信许多读者已经对【三数之和】有所涉猎。在【【LeetCode刷题笔记（6-2）】【Python】【三数之和】【双指针】【中等】】中，我详细介绍了如何设计基于【双指针】的算法解决【三数之和】问题。

现在，摆在我们面前的是【四数之和】问题，它与【三数之和】在本质上是一样的。因此，我们很自然地会把解决【三数之和】的算法搬过来，在此基础上修改，从而解决【四数之和】问题。

完整代码如下：

class Solution:  
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:  
        # 初始情况下，如果nums为空或者长度小于4，直接返回空列表  
        if not nums or len(nums) < 4:  
            return []  
          
        # 对nums进行排序，方便后续的去重和剪枝操作  
        nums.sort()  
        n = len(nums)  
        result_list = []  
  
        # 外层循环，遍历第一个数字，范围到n-3即可  
        for i in range(n - 3):  
            # 如果当前数字和前一个数字相同，则跳过，避免得到重复的四元组 
            if i > 0 and nums[i] == nums[i - 1]:  
                continue  
            # 如果当前数字加上紧跟在后面的三个数字的和都大于target，则直接返回结果列表，因为排序后不可能有更小的组合了  
            if nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target:  
                return result_list  
            # 如果当前数字加上数组末尾的三个数字的和都小于target，说明当前数字太小了，则跳过本次循环，继续遍历nums[i+1], 寻找下一个可能的组合  
            if nums[i] + nums[-1] + nums[-2] + nums[-3] < target:  
                continue  
              
            # 第二层循环，遍历第二个数字，范围从i+1到n-2  
            for j in range(i + 1, n - 2):  
                # 如果当前数字和前一个数字相同，则跳过，避免得到重复的四元组 
                if j > i + 1 and nums[j] == nums[j - 1]:  
                    continue  
                # 如果当前【固定的】两个数字加上紧跟着的两个数字的和都大于target，则跳出内层循环，继续遍历nums[i+1], 寻找下一个可能的组合    
                if nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target:  
                    break  
                # 如果当前两个数字加上数组末尾的两个数字的和都小于target，则跳过本次循环，继续遍历nums[j+1]，寻找下一个可能的组合  
                if nums[i] + nums[j] + nums[-1] + nums[-2] < target:  
                    continue  
                  
                # 使用双指针法寻找剩余的两个数字，初始时left指向j+1，right指向n-1  
                left = j + 1  
                right = n - 1  
                  
                # 当left小于right时执行循环，寻找符合要求的四个数字的组合  
                while left < right:  
                    # 如果找到了符合要求的四个数字的组合，则将其添加到结果列表中，并移动指针去重  
                    if nums[i] + nums[j] + nums[left] + nums[right] == target:  
                        result_list.append([nums[i], nums[j], nums[left], nums[right]])  
                        # 移动left指针去重  
                        while left < right and nums[left] == nums[left + 1]:  
                            left += 1  
                        # 移动right指针去重  
                        while left < right and nums[right] == nums[right - 1]:  
                            right -= 1  
                        # 继续寻找下一个可能的组合  
                        left += 1  
                        right -= 1  
                    # 如果当前四个数字的和大于target，则移动right指针，减小和的值  
                    elif nums[i] + nums[j] + nums[left] + nums[right] > target:  
                        right -= 1  
                    # 如果当前四个数字的和小于target，则移动left指针，增大和的值  
                    else:  
                        left += 1  
        # 返回结果列表  
        return result_list

如果对上面代码的执行逻辑不太熟悉，建议参考一下【LeetCode刷题笔记（6-2）】【Python】【三数之和】【双指针】【中等】中的完整代码，上面的代码和解决【三数之和】的代码绝大部分是一致的，注释和算法逻辑也在【LeetCode刷题笔记（6-2）】【Python】【三数之和】【双指针】【中等】叙述的非常清楚。

因此，在这篇博客中，我主要叙述一下修改细节。

1. 与解决【三数之和】问题的完整代码相比，【四数之和】的代码主要加了两段功能基本一致的代码段，即：

 # 如果当前数字加上紧跟在后面的三个数字的和都大于target，则直接返回结果列表，因为排序后不可能有更小的组合了  
 if nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target:  
     return result_list  
 # 如果当前数字加上数组末尾的三个数字的和都小于target，说明当前数字太小了，则跳过本次循环，继续遍历nums[i+1], 寻找下一个可能的组合  
 if nums[i] + nums[-1] + nums[-2] + nums[-3] < target:  
     continue  

由于数组是从小到大排好序的 ==> 给定数组切片nums[i:]，如果我们固定第一个元素nums[i], 那么和nums[i]相邻的三个元素构成的四元组[nums[i], nums[i + 1], nums[i + 2], nums[i + 3]] 就是所有可能的四元组中和最小的。如果和最小的的四元组都比目标值target大，那往后任意一个四元组的和都会比目标值大 ==> 直接返回结果列表即可。
同理，将nums[i]和数组切片nums[i:]末尾的三个元素构成的四元组[nums[i], nums[ -1], nums[-2], nums[-3]] 就是所有可能的四元组中和最大的；如果和最大的的四元组都比目标值target小，那说明当前固定的nums[i]可能太小 ==> 遍历下一固定值nums[i+1]。

2. 由于是【四数之和】，因此需要从一层遍历改用两层遍历；

运行结果：

复杂度分析

• 时间复杂度：O(N³)，其中 N 是数组nums元素的数量。
• 空间复杂度：O(N)
  • 需要存放排序后的新数组 ===> O(N)

结束语

• 亲爱的读者，感谢您花时间阅读我们的博客。我们非常重视您的反馈和意见，因此在这里鼓励您对我们的博客进行评论。
• 您的建议和看法对我们来说非常重要，这有助于我们更好地了解您的需求，并提供更高质量的内容和服务。
• 无论您是喜欢我们的博客还是对其有任何疑问或建议，我们都非常期待您的留言。让我们一起互动，共同进步！谢谢您的支持和参与！
• 我会坚持不懈地创作，并持续优化博文质量，为您提供更好的阅读体验。
• 谢谢您的阅读！