LeetCode : 4Sum #18
最近班班在工作场景中遇到了一个类似4Sum问题的需求问题,找我看看有没有什么好的解决方法,于是我就开始研究2Sum,3Sum,4Sum,NSum问题。
Question
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target?
Find all unique quadruplets in the array which gives the sum of target.Note:
- Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
The solution set must not contain duplicate quadruplets.
For example, given array S = {1 0 -1 0 -2 2}, and target = 0.
A solution set is:
(-1, 0, 0, 1)
(-2, -1, 1, 2)
(-2, 0, 0, 2)
简单来说,给一个非有序的数字数组,然后给定一个target
,计算有多少组不重复的集合,加起来的和为给定的target
。
Analysis
面对NSum问题,最简单最快捷的方法就是暴力枚举,但时间复杂度是O(N^3)。
基本思路就是先排序,然后外面套两层循环,target减去得出来的和,然后开始2Sum的方法,左右两边向中间移动。
每次左边和右边加起来的和等于target,这就是命中的一组。其中需要进行去重处理,其他的都是中规中矩的做法。
1 | class Solution(object): |