在一次采访中得到了这个。这个问题与非常著名的问题"找到一个三元组"非常相似，该三元组的总和为给定值，但略有不同。在这里，我们要打印所有三元组，而不仅仅是一个。
数组可以包含重复项。
例如，考虑以下数组：[1, -1, 2, 0, -2, 4, -2, -2, 4]
输出应为：
[1, -1, 0]
[4, -2, -2]
[2, -2, 0]
三元组中的顺序或数字的顺序并不重要。
使用排序或使用集合有 n^2 个解决方案(如上面链接中的解决方案(。但是如何确保我们只打印独特的三胞胎呢？我能想到的一个解决方案是使用一组来跟踪我们到目前为止看到的三胞胎。但不确定这是否是最好的方法，或者是否有其他解决方案使用排序等来生成独特的三胞胎。
没有太大区别。只有当我们有重复项时，我们才需要在各个级别上跳过它们，因此std::set不一定。
#include <vector>
#include <algorithm>
#include <iostream>
#include <array>
int main()
{
const int kDesired = 0;
std::vector<int> a = { 1, -1, 2, 0, -2, 4, -2, -2, 4 };
std::sort(a.begin(), a.end());
std::vector<std::array<int, 3>> triples;
for (int i = 0; i < (int)a.size(); ++i) {
const int others = kDesired - a[i];
for (int j = i + 1; j < (int)a.size(); ++j) {
for (int k = (int)a.size() - 1; k > j; --k) {
if (a[j] + a[k] == others) {
triples.push_back({ { a[i], a[j], a[k] } });
}
else if (a[j] + a[k] < others) {
break;
}
// we don't want a[k] to be the same next time
while (j + 1 < k && k < (int)a.size() && a[k] == a[k - 1]) --k;
}
// we don't want a[j] to be the same next time
while (i + 1 <= j && j < (int)a.size() - 1 && a[j] == a[j + 1]) ++j;
}
// we don't want a[i] to be the same next time
while (0 <= i && i < (int)a.size() - 1 && a[i] == a[i + 1]) ++i; }
for (const auto& t : triples) {
std::cout << t[0] << " " << t[1] << " " << t[2] << std::endl;
}
return 0;
}
4-2
0 2-1
0 1
在线
Python 解决方案： 时间复杂度 ： O(n^2( 空间复杂度 ： O(1(
class Solution:
def findSum(self , nums , rest_sum , start_from , soln ):
i = start_from +1
j = len(nums)-1
while(i < j ):
if(nums[i] + nums[j] < rest_sum):
i += 1
elif(nums[i] + nums[j] > rest_sum):
j -= 1
else:
soln.append( [ nums[start_from] , nums[i] , nums[j] ])
i += 1
j -= 1
while(i < j and nums[i] == nums[i-1]):#Loop to avoid duplicate
i+=1
continue
while(j > i and nums[j] == nums[j+1] ):#Loop to avoid duplicate
j-=1
continue
return
def threeSum(self, nums: List[int]) -> List[List[int]]:
if(len(nums) < 3 ):
return []
soln = []
nums.sort()
for i in range(0 , len(nums)):
if(i > 0 and nums[i-1] == nums[i]):#Loop to avoid duplicate
continue
self.findSum(nums , (0 - nums[i]) ,i , soln ) #Use Two Sum Algo to find solution
return soln
- 对数组进行排序后，您可以跳过以前访问过的相同整数。
- 时间复杂度为 O(N2log (N((。下面是一个相同的示例(我更喜欢Java(。
法典：
import java.util.*;
public class Solution{
public static void main(String[] args) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
int[] arr = {1,-1,2,0,-2,4,-2,-2, 4,-2,-2,-2,4,4,4};
int target = 0;
Arrays.sort(arr);
int low = 0,mid = 0,high = 0,seek = 0;
for(int i=0;i<arr.length;++i){
if(i > 0 && arr[i] == arr[i-1]) continue;// skip it to avoid getting same triplets
for(int j=i+1;j<arr.length;++j){
if(j > i+1 && arr[j] == arr[j-1]) continue; // skip it to avoid getting same triplets
seek = target - arr[i] - arr[j];
if(seek < arr[j]) break; // we break because seek cannot be found ahead if arr[j] is greater than it after sorting.
low = j+1;
high = arr.length-1;
while(low <= high){
mid = low + (high - low) / 2;
if(arr[mid] == seek){
// add this triplet to results.
List<Integer> triplet = new ArrayList<>();
triplet.add(arr[i]);
triplet.add(arr[j]);
triplet.add(seek);
res.add(triplet);
break;
}else if(arr[mid] > seek){
high = mid - 1;
}else{
low = mid + 1;
}
}
}
}
System.out.println(res.toString());
}
}
输出：
[[-2, -2, 4], [-2, 0, 2], [-1, 0, 1]]
多亏了Yola的回答，我才能够真正理解如何避免重复，所以这里是O(n^2(解决方案。
主要思想是主循环遍历每个唯一数字，然后尝试找到另外两个总和为 0 的数字。
主要的技巧是，对数组进行排序，然后对 i、j、k 中的每个数组进行排序，不要访问其轮中的任何重复数字，并且保证不会产生任何重复的三元组。
import java.util.Arrays;
public class Find3TripletSum0 {
public static void find(int a[]) {
Arrays.sort(a);
for (int i = 0; i < a.length; i++) {
if (i > 0 && a[i] == a[i - 1]) // pass duplicates for i
continue;
int j = i + 1;
int k = a.length - 1;
int target = -a[i];
while (j < k) {
if (j > i + 1 && a[j] == a[j - 1]) { // pass duplicates for j
j++;
continue;
}
if (k < a.length - 1 && a[k] == a[k+1]) { // pass duplicates for k
k--;
continue;
}
if (a[i] + a[j] + a[k] == 0)
System.out.printf("[%d, %d, %d]n", a[i], a[j], a[k]);
if (a[j] + a[k] < target)
j++;
else
k--;
}
}
}
public static void main(String[] args) {
int a[] = {1, -1, 2, 0, -2, 4, -2, -2, 4};
find(a);
}
}
输出：
[-2, -2, 4]
[-2, 0, 2]
[-1, 0, 1]
查看此复杂度为 O(n^2( 的解决方案 我不知道它的复杂性是否可以最小化为线性。
public static List<List<Integer>> findTriplets(int nums[]) {
boolean found = false;
List<Integer> triples = null;
HashSet<Integer> set = null;
HashSet<List<Integer>> tripleSet = new HashSet<List<Integer>>();
for (int i = 0; i < nums.length - 1; i++) {
set = new HashSet<Integer>();
for (int j = i + 1; j < nums.length; j++) {
found = false;
int x = -(nums[i] + nums[j]);
if (set.contains(x)) {
Integer [] temp = {x,nums[i],nums[j]};
Arrays.sort(temp);
triples = new ArrayList<Integer>();
triples.add(temp[0]);
triples.add(temp[1]);
triples.add(temp[2]);
found = true;
} else {
set.add(nums[j]);
}
if(found==true){
tripleSet.add(triples);
}
}
}
return new ArrayList<List<Integer>>(tripleSet);
}
如果你正在寻找javascript的解决方案，这里有一个用简单的英语解释逻辑：
const threeSum = (nums, target) => {
const hash = {};
const ans = [];
for (let i = 0; i < nums.length; i++) {
for (key in hash) {
if(hash[key][target - (nums[i] + +key)] === undefined) {
hash[key][nums[i]] = null;
} else {
hash[key][target - (nums[i] + +key)] = nums[i];
ans.push([+key, target - (nums[i] + +key), nums[i]]);
}
}
if (hash[nums[i]] === undefined) {
hash[nums[i]] = {}
}
}
return ans;
}
例
console.log(threeSum([-1, 0, 1, 2, -1, -4], 0));
输出
[ [ -1, 0, 1 ], [ 0, 1, -1 ], [ -1, 2, -1 ] ]
解释
{
-1: {0:1, 1:null, 2:-1, -1:null, -4:null},
0: {1:-1, 2: null, -1:null, -4:null},
1: {2: null, -1:null, -4: null},
2: {-1:null, -4:null},
-4: {}
}
- 遍历数组>如果不在对象中，则添加到对象
- 遍历对象> 如果不在对象的对象中，则将其添加为空 | else log
import java.util.*;
class zero
{
public static void main(String abc[])
{
int arr[]=new int[6];
int i,j,x;
Scanner c=new Scanner(System.in);
System.out.println("Enter an array to be sorted ");
for(i=0;i<6;i++)
{
arr[i]=c.nextInt();
}
Arrays.sort(arr);
for(i=0;i<6;i++)
{
System.out.println(arr[i]);
}
for(i=0;i<4;i++)
{
x=arr[i]*-1;
j=5;
while(i<j)
{
if(arr[i+1]+arr[j]>x)
{
j--;
}else if(arr[i+1]+arr[j]<x){
i++;
}else{
System.out.println("Found ");
break;
}
}
}
}
}
只有当当前数字与您已经看到的数字相同时，才会发生重复。HashSets可以用于此目的。
但是，由于您要对数组进行排序，因此只需跟踪前一个数字，因为排序可确保所有重复项都位于同一位置。
下面是 C# 中的一个解决方案。
public class Solution
{
public IList<IList<int>> ThreeSum(int[] nums)
{
var result = new List<IList<int>>();
if(nums.Length<3)
return result;
Array.Sort(nums);
int curr=nums[0]-1;
for(int i=0; i<nums.Length;i++)
{
if(nums[i]!=curr)
{
var tsum= Get2Sum(-nums[i],nums, i+1);
if(tsum.Count>0)
{
for(int j=0; j<tsum.Count;j++)
{
tsum[j].Add(nums[i]);
}
result.AddRange(tsum);
}
curr=nums[i];
}
}
return result;
}
public IList<IList<int>> Get2Sum(int target, int[] nums, int start)
{
var result = new List<IList<int>>();
int end = nums.Length-1;
if(start>=end)
{
return result;
}
//current value for starting pointer
int scurr=nums[start]-1;
//current value for ending pointer
int ecurr= nums[end]+1;
while(start< end)
{
if(nums[start]==scurr)
{
start++;
continue;
}
if(nums[end] == ecurr)
{
end--;
continue;
}
int sum = nums[start]+nums[end];
if(sum > target)
{
ecurr= nums[end];
end--;
}
else if(sum < target)
{
scurr=nums[start];
start++;
}
else
{
scurr=nums[start];
ecurr=nums[end];
result.Add(new List<int>(){nums[start], nums[end]});
start++;
end--;
}
}
return result;
}
}