LeetCode 四数之和

四数之和

题目来源：https://leetcode-cn.com/problems/4sum

前言：本题的主要思路，与 LeetCode | 15. 三数之和此题的思路相似，可以借鉴思考。下面的链接内容是往期关于 LeetCode | 15. 三数之和 的解法。

LeetCode 三数之和

题目

给定一个包含 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]
]

解题思路

思路：数组排序和双指针；
先对特殊情况进行判断，若是 nums 为空(或None) 或者 nums 数组的长度 nl 小于 4，返回空列表；
先对数组进行排序；
返回的结果列表中不会有重复的四元组。在这个前提下，对数组进行遍历（从 0 开始，取 nl -3 个数，最终需取 4 个元素，且不重复，取到第 nl - 3 个数时，即可确定最后 4 个元素），取其中一个固定值 nums[i]（注意去重）；
在确定第一个固定值时，再次遍历数组（从 i + 1 开始，取 nl - 2 个数，理由同上面），取第二个固定值 nums[j]（注意去重）；
定义双指针 L、R，分别指向 j + 1 的位置与末尾的位置。先考虑边界的问题，取第一跟第二个固定值，与后续两个数值的和，即是： nums[i] + nums[j] + nums[L] + nums[L+1]，此值为当前最小值。若这个值比目标值大，那显然后面的组合都会比目标值大，所以可以直接跳出循环；
取第一跟第二个固定值，与最后末尾两位数的和，即是：nums[i] + nums[j] + nums[R-1] + nums[R]，这个是当前最大值，若是这个值比目标值小，那么可以跳过，移动第二个固定值，寻找更大的值，再看 4 个元素之和是否等于目标值；
不存在边界问题的情况下，则考虑在确定两个固定值的前提下，在双指针区间进行搜索，找出符合条件的元素；
当找到符合条件的 4 个元素时，若左边指针对应的索引值小于右指针对应的索引值时，两个指针往中间靠拢，继续寻找符合条件的元素；
若是 4 个元素之和小于目标值，左指针往右移动，往大值的方向移动；若是大于目标值，则往小值的方向移动。（注意去重）
时间复杂度： $O(n^3)$

代码实现

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        res = []
        nl = len(nums)
        # 特殊情况判断
        if not nums or nl < 4:
            return res
        
        # 排序
        nums.sort()
        
        # 遍历数组，先固定一个值
        for i in range(nl-3):
            # 去重
            if i > 0 and nums[i] == nums[i-1]:
                continue

            # 从 i + 1，开始遍历，固定第二个值
            for j in range(i+1 ,nl-2):
                # 去重
                if j > i + 1 and nums[j] == nums[j-1]:
                    continue
                # 定义双指针
                # 左指针指向第二个固定值下一位，
                # 右指针指向末尾
                L, R = j + 1, nl - 1
                
                # 边界问题判断
                # 取第一跟第二个固定值，与后续两个数值的和
                # 数组已排序，这里的和为当前最小值
                this_min = nums[i] + nums[j] + nums[L] + nums[L+1]
                # 若当前最小值比目标值大，那可以直接跳出循环，后续的值无论组合都不能匹配
                if this_min > target:
                    break
                # 取第一跟第二个固定值，与最后末尾两位数的和，
                # 这里的和为当前的大值
                this_max = nums[i] + nums[j] + nums[R-1] + nums[R]
                # 若这里比目标值小，则可以跳过，也就是移动 j，再取较大值
                if this_max < target:
                    continue

                # 在双指针之间进行搜索
                while L < R:
                    # 取第一跟第二个固定值，与左右指针对应的值之和
                    four_sum = nums[i] + nums[j] + nums[L] + nums[R]
                    # 如果等于目标值，将四元组放入返回列表 res 中
                    if four_sum == target:
                        res.append([nums[i], nums[j], nums[L], nums[R]])
                        # 注意去重
                        while L < R and nums[L] == nums[L+1]:
                            L += 1
                        while L < R and nums[R] == nums[R-1]:
                            R -= 1
                        L += 1
                        R -= 1
                    # 当数值小于目标值时，左指针往右移动，
                    elif four_sum < target:
                        L += 1
                        # 去重
                        while L < R and nums[L] == nums[L-1]:
                            L += 1
                    # 当数值大于目标值时，右指针往左移动
                    else:
                        R -= 1
                        while L < R and nums[R] == nums[R+1]:
                            R -= 1
        return res

实现结果

以上就是关于 LeetCode | 18. 四数之和问题的解题内容。解题思想与《三数之和》相似，这里需取两个固定值，先考虑完边界问题，不满足边界条件则在双指针之间进行搜索。

欢迎关注微信公众号《书所集录》