Три суммы, используя двоичный поиск


Дан массив и значение, найти все тройки в массиве, сумма которых равна заданному значению. Например, если данный массив {12, 3, 4, 1, 6, 9} и данная сумма 24тогда это одна тройня (12, 3 and 9) что способствует общую сумму 24.

Решение для данного примера:

6, 9, 9

6, 6, 12

3, 9, 12

Условия:

  • На заказ номера в растворе не имеет значения.

  • Дубликат триплет не допускается.

  • Ряд не может быть использована несколько раз.

Подобный вопрос был задан здесь, хотя это было HashMapоснове.

На GitHub

public class ThreeSumUsingBinarySearch {

     static class Triplet {
        final List<Integer> triplets;

        public Triplet(int x, int y, int z) {
            triplets = Arrays.asList(x, y, z);
            Collections.sort(triplets);
        }

        @Override
        public String toString() {
            return String.format("(%d,%d,%d)", triplets.get(0), triplets.get(1), triplets.get(2));
        }

        @Override
        public int hashCode() {
            return triplets.hashCode();
        }

        @Override
        public boolean equals(Object o) {
            if (o instanceof Triplet) {

                Triplet other = (Triplet) o;
                return other.triplets.equals(this.triplets);
            }

            return false;
        }
    }

    public static Set<Triplet> findTriplets(int array[], int targetSum) {

        int[] numbers = Arrays.copyOf(array, array.length);
        Set<Triplet> triplets = new HashSet<>();

        Arrays.sort(numbers);

        for (int i = 0; i < array.length; i++) {
            int complement = targetSum - numbers[i];

            for (int low = i + 1, high = numbers.length - 1; low < high; ) {
                int total = numbers[low] + numbers[high];

                if (total < complement) {
                    low++;
                } else if (total > complement) {
                    high--;
                } else {
                    // found the match
                    triplets.add(new Triplet(numbers[i], numbers[low], numbers[high]));
                    low++;
                    high--;
                }
            }
        }

        return triplets;
    }
}


Комментарии