找到所有和为零的唯一三元组

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

-2 -2 4

-1 0 1

online

Python解决方案: 时间复杂度:O(n^2)

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(N) ²

代码:

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]]

其主要思想是,主循环遍历每个唯一的数字,然后试图找到另外两个数字,它们加起来等于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]

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: {}
}

2. 遍历对象>如果不在object的object中,则将其值添加为null | 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;
    }
 }
}

}
}