Проблема двух сумм с дубликатами - более идиоматическое решение Javascript - PullRequest
1 голос
/ 12 октября 2019

Учитывая массив целых чисел с дубликатами, вернуть массив со всеми парами индексов, сумма которых равна нулю.

[1, 2, 3, -1, 5, -5, 7, 9, -7, 2, -2] -> [ [ 3, 0 ], [ 5, 4 ], [ 8, 6 ], [ 10, 1 ], [ 10, 9 ] ]

Мое решение JS:

function pairs(values, i) {
  if (values) {
    values.push(i);
    return values;
  }
  return [i];
}

function twoSum(arr) {
  const results = [];
  const map = new Map();
  arr.forEach((ele, i) => {
    if (map.get(-ele)) {
      map.get(-ele).forEach((e) => results.push([i, e]));
    }
    map.set(ele, pairs(map.get(ele), i));
  });
  return results;
}

Исходя из Rubyэто мое решение Ruby:

def two_sum(arr)
  hash = Hash.new { |h, k| h[k] = [] }
  arr.each.with_index.each_with_object([]) do |(ele, i), results|
    if hash.key?(-ele)
      hash[-ele].each { |e| results << [i, e] }
    end
    hash[ele] << i
  end
end

Идея состоит в том, что каждый ключ hashmap имеет массив, и для каждого элемента в массиве мы проверяем, есть ли у hashmap ключ -element, если таквставьте пары текущего индекса и каждого значения в массив результатов.

Как сделать решение JS более идиоматичным? В библиотеке по умолчанию JS не удалось найти следующее (по сравнению с Ruby):

  1. Уменьшить перечисляемый объект до другого перечисляемого объекта (each_with_object).
  2. Инициализировать карту таким образом, чтобы каждыйНовый ключ соответствует объекту (Hash.new ([]), Hash.new (0) и т. д.).

Немного переформулировал выбранное решение и в итоге получил следующее:

function twoSum(arr) {
  const hash = new Map();
  return arr.reduce((results, ele, i) => {
    if (hash.has(-ele)) hash.get(-ele).forEach((e) => results.push([i, e]));
    hash.get(ele) ? hash.get(ele).push(i) : hash.set(ele, [i]);
    return results;
  }, []);
}

Ответы [ 2 ]

2 голосов
/ 12 октября 2019
function two_sum(arr) {
    let hash = new Map();

    return arr.reduce((results, ele, i) => {
        if (hash.has(-ele)) {
            results = results.concat(hash.get(-ele).map(e => [i, e]))
        }

        hash.set(ele, hash.get(ele) || []);
        hash.get(ele).push(i);

        return results;

    }, []);
}
0 голосов
/ 12 октября 2019

Примерно так, может быть:

const sumZeroIndexPairs = arr => {
  const hashMap = arr.reduce(
    (result, value, index, list) => {
      list.forEach((n, i) => {
        const key = [ index, i ].sort().join('_')
        const sum = value + n
        result[key] = sum
      })
      return result
    },
    {}
  );
  
  return Object.entries(hashMap)
    .filter( ([key, value]) => value === 0 )
    .map(([key]) => key.split('_'));
}

console.log(sumZeroIndexPairs([1, 2, 3, -1, 5, -5, 7, 9, -7, 2, -2]))
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...