原题及翻译

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.

给一个有 n 个 整形数的数组 S, S 中是否存在 a, b, c 和 d 四个数之和为 target? 寻找所有独特且和为 target 的四胞胎.

Note: The solution set must not contain duplicate quadruplets.

注意: 解集内的四胞胎不得重复.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

比如说给出一个数组 S = [1, 0, -1, 0, -2, 2], target = 0.

A solution set is:
该结果集为:

思路

cpp算法, 18 ms. 基本采用的是暴力法,但是稍微优化了一下. 先给数组 S 排序, 然后两层顺序循环, 从左到右分别得到 a, b 两个数, c, d 两数通过左右逼近, 获取符合条件的解.

中间两句优化是 cx1992 的思路, good idea!
转载注明 原文连接

Hello world!
文章已创建 218

发表评论

邮箱地址不会被公开。 必填项已用*标注

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部