3SUM, но возможны дубликаты - PullRequest
Новая
       21

3SUM, но возможны дубликаты

0 голосов
/ 20 января 2020

Я пытаюсь решить проблему 3SUM , но разрешены дубликаты триплетов. Например, предположим, что у нас есть массив [2 0 -1 1 -2 3 3]. Здесь решениями являются (2, 0, -2), (0, -1, 1), (-1, -2, 3) и (-1, -2, 3). Решения также можно рассматривать как (A [0], A [1], A [4]), (A [1], A [2], A [3]), (A [2], A [4]. ], A [5]) и (A [2], A [4], A [6]). Индексы должны представлять собой уникальную комбинацию, но если они являются одинаковыми значениями, это нормально.

После прочтения о проблеме я нашел много решений по ИЗБЕЖАНИЮ дубликатов, но ни одно по их сохранению. Как бы я реализовал проблему, не избегая дубликатов?

Я ищу решение O (N ^ 2) или решение O (N ^ 2logN) (не грубая сила!)

1 Ответ

1 голос
/ 20 января 2020
  • Сначала отсортируйте массив.
  • Создайте вложенный l oop.
  • Наружный l oop идет от 0 до n-2
  • Внутренний l oop идет от i+1 до n-1 (здесь i - переменная итерации external l oop).
  • Теперь мы получаем значение двух сумм, добавляя значения индексов i и j.
  • Мы go для проверки -two_sum в получить триплет с суммой как 0.
  • Мы выполняем некоторую предварительную обработку и собираем все значения и их индексы в хэш-карту.

  • Теперь мы можем просто выполнить проверку для это существование и добавьте все триплеты, просматривая индексы, хранящиеся в карте.

  • Сложность времени: O (n ^ 2) (исключая добавление триплетов l oop).

Фрагмент: 

import java.util.*;
class Main {
    public static List<List<Integer>> threeSum(int[] nums) {      
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        Map<Integer,LinkedList<Integer>> map = new HashMap<Integer,LinkedList<Integer>>();

        for(int i=0;i<nums.length;++i){
            if(!map.containsKey(nums[i])) map.put(nums[i],new LinkedList<Integer>());
            map.get(nums[i]).add(i);
        }

        for(int i=0;i<nums.length-2;++i){
           map.get(nums[i]).poll();
            for(int j=i+1;j<nums.length-1;++j){
               map.get(nums[j]).poll();
               int search_value = -(nums[i] + nums[j]);
               if(map.containsKey(search_value) && map.get(search_value).size() > 0){
                   int start_index = map.get(search_value).peek();
                   int end_index = map.get(search_value).peekLast();
                   for(int k = start_index;k <= end_index;++k) res.add(Arrays.asList(nums[i],nums[j],nums[k])); // add all triplets
               }
            }

            // restore all popped items
            for(int j=nums.length-2;j>i;--j){
                map.get(nums[j]).addFirst(j);
            }

            if(map.get(nums[i]).size() == 0) map.remove(nums[i]);
        }        

        return res;
    }

    public static void main(String... args){
        List<List<Integer>> triplets = threeSum(new int[]{2,0,-1,1,-2,3,3});
        for(int i=0;i<triplets.size();++i) System.out.println(triplets.get(i).toString());
    }

}

Демонстрация: https://onlinegdb.com/SJ4ALZ7bL

...