Найти треугольники в списке случайных чисел

Question

Я принимаю каждый элемент как «сумма», «первая» и «сек». Если (first + sec < sum), я сделаю hashset (tmp) из этих 3 и помещу это hashset в более крупный hashset (треугольник), содержащий все thhsets tmp. Это устраняет дубликаты комбинаций из 3 чисел. Вот мой код. Он работает, но есть ли лучшее решение?

public void findTriangle(int[] a){ 

    HashSet<HashSet<Integer>> triangle = new HashSet<HashSet<Integer>>(); 
    HashSet<Integer> tmp; 
    for(int i=0;i<a.length;i++){ 
     int sum=a[i]; 
     for(int j=0;j<a.length;j++){ 
      int first = a[j]; 
      if(first!=sum){ 
       for(int k=0;k<a.length;k++){ 
        int sec = a[k]; 
        if(sec!=first && sec!=sum && (first + sec < sum)){ 
         tmp = new HashSet<Integer>(); 
         tmp.add(first); 
         tmp.add(sec); 
         tmp.add(sum); 
         triangle.add(tmp); 
        } 
       }  
      } 
     } 

    } 

    for(HashSet<Integer> hs : triangle) 
     System.out.println(hs); 
} 

Answer 1

Сортировка массива и добавить триплеты в список -

public static ArrayList<ArrayList<Integer>> get(int[] input) { 
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); 
    if (input.length < 3) { 
     return result; 
    } 
    Arrays.sort(input); 
    for (int i = 0; i < input.length - 2; i++) { 
     int k = i + 2; 
     for (int j = i + 1; j < input.length; j++) { 
     while (k < input.length && input[i] + input[j] > input[k]) { 
      ArrayList<Integer> inner = new ArrayList<Integer>(); 
      inner.add(input[i]); 
      inner.add(input[j]); 
      inner.add(input[k]); 
      result.add(inner); 
      k++; 
     } 
     } 
    } 
    return result; 
    } 

Answer 2

Не так оптимальные работы еще. Я пробовал тестировать два вышеупомянутых решения, и они, похоже, не работали. Может быть, я чего-то не видел. Поэтому я решил разместить здесь свое протестированное решение. Он не проверяет наличие дубликатов. Условия найти треугольник: http://www.wikihow.com/Determine-if-Three-Side-Lengths-Are-a-Triangle

import java.util.ArrayList; 
import java.util.HashSet; 
import java.util.List; 
import java.util.Arrays; 

class Triangle { 
    int a; 
    int b; 
    int c; 

    public Triangle(int a, int b, int c) { 
     this.a = a; 
     this.b = b; 
     this.c = c; 
    } 

    @Override 
    public String toString() { 
     return this.a + " " + this.b + " " + this.c; 
    } 
} 

public class FindTriangle { 

    public List<Triangle> findTriangle(List<Integer> points) { 
     List<Triangle> result = new ArrayList<Triangle>(); 
     System.out.println("Entered"); 

     for (int i = 0; i < points.size(); i++) { 
      int pt0 = points.get(i); 
      System.out.println("Entered i:" + i); 

      for (int j = i + 1; j < points.size() - 2; j++) { 
       int pt1 = points.get(j); 
       int pt2 = points.get(j + 1); 
       Boolean isTri = isTriangle(pt0, pt1, pt2); 
       if (isTri.equals(Boolean.TRUE)) { 
        Triangle t = new Triangle(pt0, pt1, pt2); 
        result.add(t); 
       } 
      } 
      for (int j = 0; j < (i - 1) && j > 0; j++) { 
       int pt1 = points.get(j); 
       int pt2 = points.get(j + 1); 
       Boolean isTri = isTriangle(pt0, pt1, pt2); 
       if (isTri.equals(Boolean.TRUE)) { 
        Triangle t = new Triangle(pt0, pt1, pt2); 
        result.add(t); 
       } 
      } 

      // final 
      int pt1, pt2; 
      if (i == 0) { 
       pt1 = points.get(i + 1); 
       pt2 = points.get(points.size() - 1); 
      } else if (i == points.size() - 1) { 
       pt1 = points.get(0); 
       pt2 = points.get(i - 1); 
      } else { 
       pt1 = points.get(i + 1); 
       pt2 = points.get(i - 1); 
      } 

      Boolean isTri = isTriangle(pt0, pt1, pt2); 
      if (isTri.equals(Boolean.TRUE)) { 
       Triangle t = new Triangle(pt0, pt1, pt2); 
       result.add(t); 
      } 
     } 
     return result; 
    } 

    public Boolean isTriangle(Integer pt1, Integer pt2, Integer pt3) { 
     System.out.println("Pt1, Pt2, Pt3: " + pt1 + ":" + pt2 + ":" + pt3); 

     if ((pt1 + pt2) > pt3 && (pt1 + pt3) > pt2 && (pt2 + pt3) > pt1) { 
      System.out.println("This is triangle"); 
      return Boolean.TRUE; 
     } 
     return Boolean.FALSE; 
    } 

    public ArrayList<ArrayList<Integer>> getTri(int[] input) { 
     ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); 
     if (input.length < 3) { 
      return result; 
     } 
     Arrays.sort(input); 
     for (int i = 0; i < input.length - 2; i++) { 
      int k = i + 2; 
      for (int j = i + 1; j < input.length; j++) { 
       while (k < input.length && input[i] + input[j] > input[k]) { 
        ArrayList<Integer> inner = new ArrayList<Integer>(); 
        inner.add(input[i]); 
        inner.add(input[j]); 
        inner.add(input[k]); 
        result.add(inner); 
        k++; 
       } 
      } 
     } 
     return result; 
    } 

    public void findTriangleW(int[] a) { 

     HashSet<HashSet<Integer>> triangle = new HashSet<HashSet<Integer>>(); 
     HashSet<Integer> tmp; 
     for (int i = 0; i < a.length; i++) { 
      int sum = a[i]; 
      for (int j = 0; j < a.length; j++) { 
       int first = a[j]; 
       if (first != sum) { 
        for (int k = 0; k < a.length; k++) { 
         int sec = a[k]; 
         if (sec != first && sec != sum && (first + sec < sum)) { 
          tmp = new HashSet<Integer>(); 
          tmp.add(first); 
          tmp.add(sec); 
          tmp.add(sum); 
          triangle.add(tmp); 
         } 
        } 
       } 
      } 

     } 

     for (HashSet<Integer> hs : triangle) 
      System.out.println(hs); 
    } 

    public static void main(String[] args) { 
     FindTriangle f = new FindTriangle(); 
     List<Integer> points = new ArrayList<Integer>(); 
     points.add(1); 
     points.add(5); 
     points.add(10); 
     points.add(7); 

     System.out.println("Printing final results"); 
     List<Triangle> result = f.findTriangle(points); 
     for (int i = 0; i < result.size(); i++) { 
      System.out.println(result.get(i).toString()); 
     } 
    } 
}