Java:如何实现3和？

Question

我正在研究 3 Sum 来自己实现它，并遇到了以下规则的实现:

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)

以及实现(对数组进行排序，遍历列表，并使用另外两个指针来接近目标):

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));
    }
}

我的问题是(位于注释处://HERE)，检查 num[i] != num[i-1], num[lo] = 的原因是什么= num[lo+1] 和 num[hi] == num[hi-1]？据说他们应该跳过相同的结果，但这意味着什么？例子确实会有帮助。

提前感谢您，并将接受回答/赞成票。

Answer 1

假设您有 {-1,-1,0,1,2,4} 并考虑三元组 num[0], num[2], num[3] (-1,0 ,1).

lo=0 此处。要排除具有相同值的三元组 num[1]、num[2]、num[3]，我们应该增加 lo 并传递重复项