Java:如何实现三和? [英] Java: How to implement 3 sum?

问题描述

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

I'm studying the 3 Sum to implement it on my own, and came across the following implementation with the rules:

给定一个由n个整数组成的数组S，S中是否有元素a，b，c使得a + b + c = 0?在数组中找到所有零的三元组，它们的总和为零.

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.

注意:三元组(a，b，c)中的元素必须按降序排列. (即a≤b≤c) 解决方案集不得包含重复的三胞胎.

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)

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

And implementation (sorts the array, iterates through the list, and uses another two pointers to approach the target):

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]的原因是什么?假设他们应该跳过相同的结果，但这意味着什么呢?例子确实有帮助.

And my question is (located where commented: //HERE), what's the reason for checking num[i] != num[i-1], num[lo] == num[lo+1], and num[hi] == num[hi-1]? Supposedly they are supposed to skip the same result, but what does that mean? Examples would really help.

提前谢谢您，我们将接受答案/投票.

Thank you in advance and will accept answer/up vote.

推荐答案

以下程序查找O(N * 2)组成的三对整数

Following program finds pairs of three integer with O(N*2)

1. 排序输入数组
2. 并迭代for循环中的每个元素，并在为两个和开发的程序中检查和.

排序后线性时间中的两个和-> https://stackoverflow.com/a/49650614/4723446

Two sum in linear time after sorting -> https://stackoverflow.com/a/49650614/4723446

公共类ThreeSum {

public class ThreeSum {

private static int countThreeSum(int[] numbers) {
    int count = 0;

    for (int i = 0; i < numbers.length; i++) {
        int front = 0, rear = numbers.length - 1;

        while (front < rear) {
            if (numbers[front] + numbers[rear] + numbers[i] == 0) {
                System.out.printf(String.format("Front : {%d}  Rear : {%d}  I : {%d}  \n", numbers[front],
                        numbers[rear], numbers[i]));
                front++;
                rear--;
                count++;
            } else {
                if (Math.abs(numbers[front]) > Math.abs(numbers[rear])) {
                    front++;
                } else {
                    rear--;
                }
            }
        }
    }

    return count;
}

public static void main(String[] args) {
    int[] numbers = { 1, 3, 5, 7, 12, 16, 19, 15, 11, 8, -1, -3, -7, -8, -11, -17, -15 };
    Arrays.sort(numbers);
    System.out.println(countThreeSum(numbers));
}

}

这篇关于Java:如何实现三和?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！