我正在研究 3 Sum 来自己实现它,并遇到了以下规则的实现:
给定一个由 n 个整数组成的数组 S,S 中是否存在满足 a + b + c = 0 的元素 a、b、c?查找数组中所有总和为零的唯一三元组。
注意:三元组 (a,b,c) 中的元素必须按非降序排列。 (即,a ≤ b ≤ c)
解决方案集不得包含重复的三元组。
For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)
和实现(对数组进行排序,遍历列表,并使用另外两个指针来接近目标):
import java.util.*;
public class ThreeSum {
List<List<Integer>> threeSum(int[] num) {
Arrays.sort(num);
List<List<Integer>> res = new LinkedList<>();
for (int i=0; i<num.length-2; i++) {
if (i==0 || (i>0 && num[i] != num[i-1])) { //HERE
int lo = i+1;
int hi = num.length-1;
int sum = 0 - num[i];
while (lo < hi) {
if (num[lo] + num[hi] == sum) {
res.add(Arrays.asList(num[i], num[lo], num[hi]));
while (lo < hi && num[lo] == num[lo+1]) lo++; //HERE
while (lo < hi && num[hi] == num[hi-1]) hi--; //HERE
lo++; hi--;
} else if (num[lo] + num[hi] < sum) lo++;
else hi--;
}
}
}
return res;
}
//Driver
public static void main(String args[]) {
ThreeSum ts = new ThreeSum();
int[] sum = {-1, 0, 1, 2, -1, -4};
System.out.println(ts.threeSum(sum));
}
}
我的问题是(位于评论位置://此处),检查的原因是什么num[i] != num[i-1]
, num[lo] == num[lo+1]
, and num[hi] == num[hi-1]
?据说他们应该跳过相同的结果,但这意味着什么?例子确实会有帮助。
预先感谢您,并将接受回答/赞成票。