18. 4Sum 四数之和

本文关键词：four sum, 4sum, 四数之和，题解，leetcode, 力扣，Python, C++, Java

题目地址：https://leetcode.com/problems/4sum/description/

题目描述

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

Thesolution set must not contain duplicate quadruplets.

Example:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

Asolution set is:

[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

题目大意

找出一个数组中所有的和为target的四个数字，要求返回的结果里面不准有重复的四元组。

解题方法

遍历

总结一下 K-sum 题目。

1、 首先先排序；
2、 然后用K−2个指针做O(N^(K-2))的遍历；
3、 剩下2个指针从第2步的剩余区间里面找，找的方式是使用两个指针p,q分别指向剩余区间的首尾，判断两个指针的和与target-第2步的和的关系，对应的移动指针即如果两个数的和大了，那么,q--；如果两个数的和小了，那么，p++；等于的话，输出结果要时刻注意p<q.；
4、 用p,q查找剩余区间结束之后，需要移动前面的K-2个值，这里需要在移动的过程中做个去重，找到和前面不同的值继续查找剩余区间；

时间复杂度是O(N^3)，空间复杂度是O(1).

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        N = len(nums)
        nums.sort()
        res = []
        i = 0
        while i < N - 3:
            j = i + 1
            while j < N - 2:
                k = j + 1
                l = N - 1
                remain = target - nums[i] - nums[j]
                while k < l:
                    if nums[k] + nums[l] > remain:
                        l -= 1
                    elif nums[k] + nums[l] < remain:
                        k += 1
                    else:
                        res.append([nums[i], nums[j], nums[k], nums[l]])
                        while k < l and nums[k] == nums[k + 1]:
                            k += 1
                        while k < l and nums[l] == nums[l - 1]:
                            l -= 1
                        k += 1
                        l -= 1
                while j < N - 2 and nums[j] == nums[j + 1]:
                    j += 1
                j += 1 重要
            while i < N - 3 and nums[i] == nums[i + 1]:
                i += 1
            i += 1 重要
        return res

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

相似题目

Two Sumopen in new windowTwo Sum II - Input array is sortedopen in new window15. 3Sumopen in new window16. 3Sum Closestopen in new window923. 3Sum With Multiplicityopen in new window454. 4Sum IIopen in new window

参考资料

https://blog.csdn.net/MebiuW/article/details/50938326

DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发