Интересные задачи для программистов

ахахахах

простите

Сначала в не ту степь с array_combine. Работает, но не обязательно первое достает c например [1,2,3,3,3,3,3, 6].

Потом дошло. Смысл в значениях в качестве индекса.

https://pastebin.com/NcuYkQbe

Вариант в "лоб" по памяти чуть лучше, но медленней

class Solution {

    private $n, $t, $l;    

    public function twoSum(array $nums, int $target) {

      $this->n = $nums;

      $this->t = $target;

      $this->l = count($nums);

      $c = $this->l-1;

      for($i=0;$i<$c;$i++){

        $r = $this->calc($this->n[$i], $i+1);

        if(false!==$r) return [$i,$r];

      }

      return [];

    }



    private function calc($val, $k){

      for($i=$k;$i<$this->l;$i++){        

        if( $this->t == $val + $this->n[$i]) return $i;

      }

      return false;

    }

}

такой линейный вариант https://pastebin.com/QJvnxc1A , но пока далековато от лучших решений на пхп..

Gerga, очень странно что способ грубого перебора обогнал 49% всех вариантов)) интересно, что там другие понаписывали тогда) наверное count в цикле.

На пыхе у меня вот так вышло, но один раз поняв алгоритм, дальше становится не интересно

Я заставил свой алгоритм проходить тесты, но пока удручающе все плохо. Но это все еще перебор, хоть и по хэштаб, Пока не могу врубиться в алгоритм(

Runtime: 5964 ms, faster than 8.52% of Python3 online submissions for Two Sum.

Memory Usage: 16 MB, less than 5.77% of Python3 online submissions for Two Sum.

Это как это за 0 сек? 🤪

Очень похожий результат

timo-71, у меня такое же решение итоговое. не думал как соточку выжать?

спойлер:

я сначала подумал что нужно преаллоцировать массив (в Go и Rust я так и делал), но в пыхе этого сделать нельзя (SplFixedArray это таки массив, а не мапа или хеш таблица).

https://pastebin.com/HgtXG8d2

На питоне с тем же алгоритмом:(

---------- Добавлено 18.06.2020 в 19:06 ----------

Что то идей больше нет. :(

Вот на С# https://dotnetfiddle.net/rX0UbZ

Вроде правильно работает :)

Compile: 0.014s

Execute: 0.05s

Memory: 0b

CPU: 0.064s