Leetcode - 3Sum. Не пойму, чего хотят - Алгоритмы

Здравствуйте, Marty, Вы писали:

M>https://leetcode.com/problems/3sum/

M>

M>Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

M>Notice that the solution set must not contain duplicate triplets.

Дошло. Я исходил из того, что дубликаты — это по индексам элементов, а на самом деле — по значениям элементов. Меня сбило с толку условие "i != j, i != k, and j != k", которое вообще-то говорит только о том, что это должны быть разные элементы, и не более того

Здравствуйте!

https://leetcode.com/problems/3sum/

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Моё решение

class Solution {
public:
    
    // Constraints:
    // 0 <= nums.length <= 3000


    struct Index3
    {
        size_t  idx[3];

        static void minmax( size_t &i1, size_t &i2 )
        {
            size_t tmp = max(i1,i2);
            i1 = min(i1,i2);
            i2 = tmp;
        }

        static Index3 makeOrdered( size_t i1, size_t i2, size_t i3 )
        {
            // Если закоментить, то вариантов появляется гораздо больше
            minmax(i2,i3);
            minmax(i1,i2); // минимум провалился в i1
            minmax(i2,i3); // максимум всплыл в i3

            Index3 res;
            res.idx[0] = i1;
            res.idx[1] = i2;
            res.idx[2] = i3;

            return res;
        }

        bool operator==(const Index3& rhs) const
        {
            return idx[0] == rhs.idx[0] && idx[1] == rhs.idx[1] && idx[2] == rhs.idx[2];
        }


    };

    struct Index3Hash
    {
        std::size_t operator()(const Index3 &i) const noexcept
        {
            size_t h0 = std::hash<size_t>{}(i.idx[0]);
            size_t h1 = std::hash<size_t>{}(i.idx[1]);
            size_t h2 = std::hash<size_t>{}(i.idx[2]);

            return h0 ^ (h1 << 1) ^ (h2 << 2); // or use boost::hash_combine
        }
    };

    
    bool findUnusedIdx( const unordered_set<size_t> &s, size_t &foundIdx, const unordered_set<size_t> &used)
    {
        for(auto v:s)
        {
            if (used.find(v)==used.end())
            {
                foundIdx = v;
                return true;
            }
        }
        
        return false;
    }
    
    bool findUnusedIdx( const unordered_set<size_t> &s, size_t &foundIdx )
    {
        return findUnusedIdx( s, foundIdx, unordered_set<size_t>());
    }

    bool findUnusedIdx( const unordered_set<size_t> &s, size_t &foundIdx, size_t i1 )
    {
        return findUnusedIdx( s, foundIdx, unordered_set<size_t>{ i1 } );
    }

    bool findUnusedIdx( const unordered_set<size_t> &s, size_t &foundIdx, size_t i1, size_t i2 )
    {
        return findUnusedIdx( s, foundIdx, unordered_set<size_t>{ i1, i2 } );
    }
    
    vector<vector<int>> threeSum(vector<int>& nums) {
        
        unordered_map<int, unordered_set<size_t> > indices;
        
        for(size_t i=0; i!=nums.size(); ++i)
        {
            indices[nums[i]].insert(i);
        }
        
        vector< vector<int> > res;

        unordered_set< Index3, Index3Hash > usedTriplets;

        for(size_t idxFirst=0; idxFirst!=nums.size(); ++idxFirst )
        {
            for(size_t idxSecond=0; idxSecond!=nums.size(); ++idxSecond ) // от 0, если не упорядочивать индексы, и от idxFirst+1, если упорядочивать
            {
                if (idxFirst==idxSecond)
                    continue;

                int sum2 = nums[idxFirst] + nums[idxSecond];
                
                // sum2 + _3 = 0
                // _3 = 0 - sum2
                int thirdCandidate = 0 - sum2;

                unordered_map<int, unordered_set<size_t> >::iterator itThird = indices.find(thirdCandidate);
                if (itThird==indices.end())
                {
                    continue; // продолжаем перебирать
                }
                
                size_t idxThird = 0;
                if (!findUnusedIdx( itThird->second, idxThird, idxFirst, idxSecond))
                {    
                    continue; // продолжаем перебирать
                }

                auto idxTriplet = Index3::makeOrdered(idxFirst, idxSecond, idxThird);
                if (usedTriplets.find(idxTriplet)!=usedTriplets.end())
                    continue;

                usedTriplets.insert(idxTriplet);

                res.emplace_back(vector<int>{nums[idxFirst], nums[idxSecond], nums[idxThird]});
            
            }
        
        }

        
        return res;
    }
};

Выдаёт:

Your input                   
[-1,0,1,2,-1,-4]             
Output                       
[[-1,0,1],[-1,2,-1],[0,1,-1]]
Expected                     
[[-1,-1,2],[-1,0,1]]

Окай, у меня было другое решение, которое в данном случае выдавало тоже самое. Но ломалось на этом:

[-1,0,1,2,-1,-4,-2,-3,3,0,4]                                                         
Output                                                                               
[[4,-4,0],[3,-4,1],[-2,3,-1],[1,-3,2],[-3,4,-1],[0,3,-3],[2,-2,0],[-1,1,0]]          
Expected                                                                             
[[-4,0,4],[-4,1,3],[-3,-1,4],[-3,0,3],[-3,1,2],[-2,-1,3],[-2,0,2],[-1,-1,2],[-1,0,1]]

Что я не так понял?

ЗЫ Я индексы упорядочиваю в обоих своих варантах, если не упорядочивать, то в первом кейсе вариантов становится еще больше, во втором тоже больше, но не на один, а на много

Здравствуйте, Marty, Вы писали:

M>https://leetcode.com/problems/3sum/

M>

M>Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

M>Notice that the solution set must not contain duplicate triplets.

M>Выдаёт:
M>

M>Your input                   
M>[-1,0,1,2,-1,-4]             
M>Output                       
M>[[-1,0,1],[-1,2,-1],[0,1,-1]]
M>Expected                     
M>[[-1,-1,2],[-1,0,1]]         
M>

M>Окай, у меня было другое решение, которое в данном случае выдавало тоже самое. Но ломалось на этом:
M>

M>[-1,0,1,2,-1,-4,-2,-3,3,0,4]                                                         
M>Output                                                                               
M>[[4,-4,0],[3,-4,1],[-2,3,-1],[1,-3,2],[-3,4,-1],[0,3,-3],[2,-2,0],[-1,1,0]]          
M>Expected                                                                             
M>[[-4,0,4],[-4,1,3],[-3,-1,4],[-3,0,3],[-3,1,2],[-2,-1,3],[-2,0,2],[-1,-1,2],[-1,0,1]]
M>

M>Что я не так понял?

M>ЗЫ Я индексы упорядочиваю в обоих своих варантах, если не упорядочивать, то в первом кейсе вариантов становится еще больше, во втором тоже больше, но не на один, а на много

А входные данные сортировать можно?
Я бы сделал так:
1. Упорядочить входные данные по возрастанию.
2. Три индекса — один указывает на левый элемент, третий — на правый, а второй — бегает между первым и третим (выполняет кастрированный двоичный поиск).

Псевдокод примерно такой:

// Входные данные после сортировки:
 0  1  2  3  4  5  6  7  8  9  10
+--+--+--+--+--+--+--+--+--+--+--+
|-4|-3|-2|-1|-1| 0| 0| 1| 2| 3| 4|
+--+--+--+--+--+--+--+--+--+--+--+

int idx1 = 0,
    idx2 = 5,
    idx3 = 10;

while(idx1 < idx3) // Пока интервал не схлопнулся
{
   idx3 = 10;      // правую границу на исходную
   idx2 = (idx1 + idx3)/2; // "бегунок" поставить куда-то в середину интервала

   while(true)     // Начинаем двигать правую границу интервала навстречу левой
   {
      // Найти положение idx2, при котором nums[idx1] + nums[idx2] + nums[idx3] == 0
      ...
      assert(idx1 < idx2 && idx2 < idx3); // idx2 не выходит за границы
      // Если нашел подходящий idx2, то добавить найденный набор в копилку.

      --idx3;    // Сдвинуть правую границу интервала

      if (((nums[idx1] + nums[idx3]) > -nums[idx1]) || ((nums[idx1] + nums[idx3]) < -nums[idx3]))
          break; // в интервале нет подходящего слагаемого, можно закончить перебор
   }

   ++idx1; // Сдвинуть левую границу интервала
}

В триплетах элементы будут всегда упорядочены, как в тестовых наборах.
Если меня чюйка не подводит, то тут даже хеш не потребуется — достаточно перед добавлением в копилку проверить последний элемент (но это неточно!).

При отладке на бумажке получаются все триплеты, как в Expected.
Прикольная задачка.

Здравствуйте, Stanislav V. Zudin, Вы писали:

M>>Выдаёт:
M>>

M>>Your input                   
M>>[-1,0,1,2,-1,-4]             
M>>Output                       
M>>[[-1,0,1],[-1,2,-1],[0,1,-1]]
M>>Expected                     
M>>[[-1,-1,2],[-1,0,1]]         
M>>

M>>Что я не так понял?

M>>ЗЫ Я индексы упорядочиваю в обоих своих варантах, если не упорядочивать, то в первом кейсе вариантов становится еще больше, во втором тоже больше, но не на один, а на много

SVZ>А входные данные сортировать можно?
SVZ>Я бы сделал так:
SVZ>1. Упорядочить входные данные по возрастанию.
SVZ>2. Три индекса — один указывает на левый элемент, третий — на правый, а второй — бегает между первым и третим (выполняет кастрированный двоичный поиск).

Да, идея интересная.

Но получается, что тестовые данные подогнаны под решение, а не под условие. Вот в моем выводе, который я оставил — что с ним не так?

Здравствуйте, Marty, Вы писали:

M>Но получается, что тестовые данные подогнаны под решение, а не под условие.

Не совсем, это просто побочный эффект.
Если я правильно понял условие, то триплеты [-1,0,1], [0,-1,1] и [1,-1,0] эквивалентны.
На упорядоченных данных проще искать и сравнивать, видимо поэтому в тестовых результатах выходят упорядоченные триплеты.

Здравствуйте, Marty, Вы писали:

M>https://leetcode.com/problems/3sum/

Решил глянуть что вообще такое leetcode на этом примере

Мой вариант на расте. PS: Возможно что-то неправильно понял в задании + не проверял

use std::collections::*;
use itertools::*;

pub fn three_sum(nums: Vec<i32>) -> Vec<Vec<i32>> {
    let mut lookup = HashMap::new(); // value -> index

    let mut lookup_minus_sum = |sum| -> Option<(i32, usize, i32, usize)> {
        lookup.clear();
        for (idx, value) in nums.iter().enumerate() {
            let sum_minus = sum - value;
            if let Some(i) = lookup.get(&sum_minus) {
                return Some((*value, idx, sum_minus, *i));
            } else {
                lookup.insert(*value, idx);
            }
        }
        None
    };

    nums.iter().enumerate()
        .filter_map(|(i, v)| lookup_minus_sum(-v).and_then(  // находим пару в nums, такую что их сумма равна -v:
            |(v2, j, v3, k)| 
                Some((i, *v, j, v2, k, v3))
        ))
        .filter(|(i, _, j, _, k, _)|                         // отсеиваем по индексам i != k && j!= k && k != i
            i != k && j != k && k != i
        )  
        .map(|(_, v1, _, v2, _, v3)|                         // формируем тройки
            (v1, v2, v3)
        )               
        .unique()                                            // оставляем только уникальные тройки
        .map(|(v1, v2, v3)|                                  // как требует задание, тройка должна быть вектором
            vec![v1, v2, v3]
        )                    
        .collect()                                           // получаем конечный вектор векторов
}

PPS: поправил форматирование, чтобы было красивее )

Здравствуйте, ArtDenis, Вы писали:

M>>https://leetcode.com/problems/3sum/

AD>Решил глянуть что вообще такое leetcode на этом примере

AD>Мой вариант на расте. PS: Возможно что-то неправильно понял в задании + не проверял

Не очень понял, а какая сложность в итоге?
Чтобы проверить, надо засабмитить на литкоде

AD>

AD>

AD>PPS: поправил форматирование, чтобы было красивее )

Блин, это какой-то птичий язык — одни крючки да закорючки. И потом кто-то ругает C++ и говорит, что Rust — это понятно и удобно

Здравствуйте, Stanislav V. Zudin, Вы писали:

SVZ>А входные данные сортировать можно?

Кстати, не факт. С другой стороны, хэш-мап с индексами займёт столько же места, так что, думаю, можно сделать копию.

SVZ>Я бы сделал так:
SVZ>1. Упорядочить входные данные по возрастанию.
SVZ>2. Три индекса — один указывает на левый элемент, третий — на правый, а второй — бегает между первым и третим (выполняет кастрированный двоичный поиск).

Но вот какая сложность твоего решения? Сортировка — это N*log(N), плюс log(N) — итого N*log(N)**2, так вроде. Ну, вроде побыстрее, чем N**2

вот на питончике простой вариант за n^2

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        memo = {}
        result = set()
        n = len(nums)
        for i in range(0, n):
            memo[-nums[i]] = i
        for i in range(0, n):
            for j in range(i + 1, n):
                d = nums[i] + nums[j]
                if d in memo and memo[d] != i and memo[d] != j:
                    t = tuple(sorted((nums[i], nums[j],-d)))
                    result.add(t)
        return result

Здравствуйте, Marty, Вы писали:

SVZ>>1. Упорядочить входные данные по возрастанию.
SVZ>>2. Три индекса — один указывает на левый элемент, третий — на правый, а второй — бегает между первым и третим (выполняет кастрированный двоичный поиск).

M>Но вот какая сложность твоего решения? Сортировка — это N*log(N), плюс log(N) — итого N*log(N)**2, так вроде. Ну, вроде побыстрее, чем N**2

С сортировкой всё ясно.

А в последующем переборе всё зависит от характера данных.

Если взять равномерный ряд (ИМХО худший случай), например, -3, -2, -1, 0, 1, 2, 3:

Левый индекс перебирает элементы от самого отрицательного до 0.
Средний и правый индексы перебирают примерно половину интервала.
Это получается (N/2) * (N/2) -> N^2.

В запущенных случаях будет чуть больше, чем O(N), т.к. итерации будут прерываться очень быстро.

Здравствуйте, Marty, Вы писали:

M>Не очень понял, а какая сложность в итоге?
O(n^2) в худшем случае. Но это не точно )

M>Чтобы проверить, надо засабмитить на литкоде
У меня там нету аккаунта. Я просто решил глянуть что там народ решает.

M>Блин, это какой-то птичий язык — одни крючки да закорючки. И потом кто-то ругает C++ и говорит, что Rust — это понятно и удобно

Раст — это боль, страдание и битьё по рукам. Те, кто так говорят — латентные мазохисты )

Здравствуйте, iriska2, Вы писали:

I>вот на питончике простой вариант за n^2

Я такое же решение предполагал, но вместо set можно использовать массив, если сначала в исходном массиве оставить только не более 2х дубликатов, а для 0 — вообще оставлять только в одном экземпляре. (если "0" — 3 и более, то добавлять в множество [0,0,0], как специальный случай)

От:	Marty	https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата:	05.05.22 17:59
Оценка:	+1

От:	Marty	https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата:	05.05.22 16:02
Оценка:

	От:	Stanislav V. Zudin
	Дата:	05.05.22 17:06
	Оценка:

От:	Marty	https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата:	05.05.22 17:31
Оценка:

	От:	Stanislav V. Zudin
	Дата:	06.05.22 06:36
	Оценка:

	От:	Plague
	Дата:	12.05.22 08:31
	Оценка: