Java:如何实现三和?

本文介绍了Java:如何实现三和?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在研究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)

排序输入数组

并迭代for循环中的每个元素，并在为两个和开发的程序中检查和.

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

Two sum in linear time after sorting -> stackoverflow/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)); }

}