p****n
发帖数: 148 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: person (幸福的黄马甲), 信区: JobHunting
标 题: 一FG家常见题
发信站: BBS 未名空间站 (Thu Apr 26 11:10:11 2012, 美东)
3Sum，原题附在下面
有什么好办法( O(n^2 ) ?)能处理输入中重复的元素，又不产生重复解吗？
如 S = {0, 0, 0, 0, -1, -1, -1, -1, 2},
A solution set is:
(0, 0, 0)
(-1,-1,2)
========
Given an array S of n integers, are there elements a, b, c in S such that a
+ b + c = 0? Find all unique triplets in the array which gives the sum of
zero.
Note:
* Elements in a triplet (a,b,c) must be in non-descending order. (ie, a
≤ b ≤ c)
* The solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2) | b*****e
发帖数: 474 | 2 Suppose s_i <= s_j for all i<=j, i.e. sorted (sorting takes no more
than O(n^2) anyway.
for i=0 to n-3
// find j, k such that i
// i.e. (s_j - s_i/2 ) = - (s_k - s_i/2 )
// if so, output ( i, j, k)
let series t_m = s_m - s_i/2 for all m > i.
// this step is not really necessary but would clarify
// the process. You may simply substitute t_m with s_m-s_i/2
// below
// find all pairs of (j, k), such that t_j = - t_k
// since t_m is sorted, this is trivial in O(n) time
let j=i+1, k=n-1
while ( j < k )
if t_j == t_k == 0
output ( i, j, k), break
else if t_j , t_k same sign break;
else if t_j + t_k < 0 then j++
else if t_j + t_k > 0 then k--
else
output ( i, j ,k)
k--, j++ until no duplicates of t_j or t_k are there
【在 p****n 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: person (幸福的黄马甲), 信区: JobHunting
: 标 题: 一FG家常见题
: 发信站: BBS 未名空间站 (Thu Apr 26 11:10:11 2012, 美东)
: 3Sum，原题附在下面
: 有什么好办法( O(n^2 ) ?)能处理输入中重复的元素，又不产生重复解吗？
: 如 S = {0, 0, 0, 0, -1, -1, -1, -1, 2},
: A solution set is:
: (0, 0, 0)
: (-1,-1,2)
|
|
