4Sum

题目链接

题意

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

注意点

1. 如何使得结果不重复？
2. 如何以的复杂度求解？

解答

  假设满足等式的下标分别为1st，2st，3st，4st，且依次递增。我们先用二重循环遍历所有可取的1st和2st，再判断是否存在对应的3st和4st满足：为避免超时，必须在常数时间内完成寻找3st和4st。，以为键，数组为值，建立哈希表。于是，对于给定的 1st 和 2st，若哈希表中存在对应键，从键值中找到符合要求的[a,b]，即为一个解。

  执行以上步骤前，还需先将nums排序，便于避免重复的元素被遍历。

Python代码

class Solution:
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        hash1 = dict()
        nums = sorted(nums)

        add2 = [[-1] * len(nums) for i in range(len(nums))]

        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                add2[i][j] = nums[i] + nums[j]
                hash1[add2[i][j]] = []
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                hash1[add2[i][j]].append([i, j])
        res = []
        pre_f = None

        for first in range(len(nums) - 3):
            if nums[first] == pre_f:
                continue
            pre_f = nums[first]

            pre_s = None
            for second in range(first + 1, len(nums) - 2):
                if nums[second] == pre_s:
                    continue
                pre_s = nums[second]

                t = target - nums[first] - nums[second]
                if t not in hash1:
                    continue
                candidate = hash1[t]
                pre_t = None
                for item in candidate:
                    if item[0] <= second or nums[item[0]] == pre_t:
                        continue
                    pre_t = nums[item[0]]
                    res.append([nums[first], nums[second], nums[item[0]], nums[item[1]]])

        return res