LeetCode-中等-18. 四数之和

LeetCode-中等-18. 四数之和 LeetCode-中等-18. 四数之和

题目
引用自：LeetCode-中等-18. 四数之和（如有侵权联系删除）

给你一个由 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 = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

提示：

• 1 <= nums.length <= 200
• -109 <= nums[i] <= 109
• -109 <= target <= 109

解题：
没什么好说的(老一句)，
方法一：
暴力破解，4层循环，挨个判断，注意从前到后的顺序，4个元素别抽取重复就好。抽取出来的4个元素如果满足target条件，则检查是不是跟以前的答案有重复，有的话就丢掉，没重复的话就添加到数组(列表)存起来，(其中判断重复的那一部分，可以先把这4个数排序，方便检查，然后跟以前存储下来的答案检查，无重复的话直接把这个排好序的4个元素数组(列表)存起来，这样每次判断的时候，从存起来的答案里面抽出来的4位数组，就不需要重新排序了，因为放进去的时候就是排好序的。同时，每次判断重复时，可以判断前3个数就行，因为前三个数字如果都相同，那么第四个数肯定也一样，因为num1 + num2 + num3 + num4 == target，target和三个数确定之后，第四个数自然也确定了）。O(n^4)
方法二
双指针，先将整个数组排序，然后跟方法一 一样，挨个检查，只是不用4层循环，用两层循环，加一个双指针。外边两层也是和方法一的外两层一样，但是每次迭代里面，用一个双指针，一个从左往右(这里并不是从整个数组的最左开始，看代码)，一个从右往左(这个右就从数组末尾开始了)，每次判断外层循环的两个数和指针滑动的两个数，这四个数之和是等于target，还是大于或者小于target，如果小于target，说明我们应该适当把这4个数里的某些数调大，由于数组又是已经排序过的，所以就把左指针往右滑动一下，这样，左指针指向的数有可能就会变大，再进行和判断，同理，如果大于target，那就把右指针向左移。如果刚好等于target，那就去判断有没有跟以前存下来的答案重复（因为整个数组提前排好序了，所以直接检查，不需要重新把这4个数排序），检查完，继续把左指针向右移动一下(或者右指针向左移动一下，这两个都可以)，直到左右指针相遇。
O（nlogn + n^3），排序是O(nlogn)，迭代是两层加双指针，相当于3层迭代。

代码：

方法一:

#方法一：leetcode提交的时候超时了，因为时间复杂度高
# 四层循环解法
class Solution:
    def fourSum(self, nums, target):
        self.result = []
        length = len(nums)
        if length < 4:
            return []
        i = 0
        while i < length - 3:
            j = i + 1
            while j < length - 2:
                k = j + 1
                while k < length - 1:
                    l = k + 1
                    while l < length:
                        if nums[i] + nums[j] + nums[k] + nums[l] == target:
                            self.deal_same([nums[i], nums[j], nums[k], nums[l]])
                        l += 1
                    k += 1
                j += 1
            i += 1
        return self.result
    def deal_same(self, list_four):
        if len(self.result) < 1:
            list_four = sorted(list_four)
            self.result.append(list_four)
        list_four = sorted(list_four)
        for res in self.result:
            if list_four[0] == res[0] and list_four[1] == res[1] and list_four[2] == res[2]:
                return
        self.result.append(list_four)

#方法二：leetcode提交通过, （记得Solution1换成Solution）
#双指针解法
class Solution1:
    def fourSum(self, nums, target):
        nums = sorted(nums)
        self.result = []
        length = len(nums)
        if length < 4:
            return []
        i = 0
        while i < length - 3:
            j = i + 1
            while j < length - 2:
                k = j + 1
                l = length - 1
                while l > k:
                    sum = nums[i] + nums[j] + nums[k] + nums[l]
                    if sum > target:
                        l -= 1
                    elif sum < target:
                        k += 1
                    else:
                        self.deal_same([nums[i], nums[j], nums[k], nums[l]])
                        k += 1
                j += 1
            i += 1
        return self.result
    def deal_same(self, list_four):
        if len(self.result) < 1:
            self.result.append(list_four)
        for res in self.result:
            if list_four[0] == res[0] and list_four[1] == res[1] and list_four[2] == res[2]:
                return
        self.result.append(list_four)

测试：

# 四层循环解法
class Solution:
    def fourSum(self, nums, target):
        self.result = []
        length = len(nums)
        if length < 4:
            return []
        i = 0
        while i < length - 3:
            j = i + 1
            while j < length - 2:
                k = j + 1
                while k < length - 1:
                    l = k + 1
                    while l < length:
                        if nums[i] + nums[j] + nums[k] + nums[l] == target:
                            self.deal_same([nums[i], nums[j], nums[k], nums[l]])
                        l += 1
                    k += 1
                j += 1
            i += 1
        return self.result
    def deal_same(self, list_four):
        if len(self.result) < 1:
            list_four = sorted(list_four)
            self.result.append(list_four)
        list_four = sorted(list_four)
        for res in self.result:
            if list_four[0] == res[0] and list_four[1] == res[1] and list_four[2] == res[2]:
                return
        self.result.append(list_four)

#双指针解法
class Solution1:
    def fourSum(self, nums, target):
        nums = sorted(nums)
        self.result = []
        length = len(nums)
        if length < 4:
            return []
        i = 0
        while i < length - 3:
            j = i + 1
            while j < length - 2:
                k = j + 1
                l = length - 1
                while l > k:
                    sum = nums[i] + nums[j] + nums[k] + nums[l]
                    if sum > target:
                        l -= 1
                    elif sum < target:
                        k += 1
                    else:
                        self.deal_same([nums[i], nums[j], nums[k], nums[l]])
                        k += 1
                j += 1
            i += 1
        return self.result
    def deal_same(self, list_four):
        if len(self.result) < 1:
            self.result.append(list_four)
        for res in self.result:
            if list_four[0] == res[0] and list_four[1] == res[1] and list_four[2] == res[2]:
                return
        self.result.append(list_four)

if __name__=="__main__":
    so = Solution()
    so1 = Solution1()
    print('测试1: nums=[3,2,2,3,2], target=9')
    print('4层循环t',so.fourSum(nums=[3,2,2,3,2], target=9))
    print('双指针t',so1.fourSum(nums=[3,2,2,3,2], target=9))
    print()
    print('测试2: nums=[1,0,-1,0,-2,2], target=0')
    print('4层循环t', so.fourSum(nums=[1,0,-1,0,-2,2], target=0))
    print('双指针t', so1.fourSum(nums=[1,0,-1,0,-2,2], target=0))