1. Two Sum

💡 に答える

// O(NlogN)
var twoSum = function (nums, target) {
  let sorted = [...nums].sort((a, b) => a - b);

  let end = sorted.length - 1;
  let start = 0;
  let answer = [];

  for (let i = 0; i < sorted.length; i++) {
    if (sorted[start] + sorted[end] > target) {
      end--;
    } else if (sorted[start] + sorted[end] === target) {
      answer = [sorted[start], sorted[end]];
    } else {
      start++;
    }
  }

  answer = [nums.indexOf(answer[0]), nums.lastIndexOf(answer[1])];

  return answer;
};

// O(N)
var twoSum = function (nums, target) {
  let hash = {};

  for (let i = 0; i < nums.length; i++) {
    const n = nums[i];
    if (hash[target - n] !== undefined) {
      return [hash[target - n], i];
    }
    hash[n] = i;
  }
  return [];
};

let nums = [3, 3];
let target = 6;
twoSum(nums, target);

📝 整理する

leetcode問題を初めて解いたときに出会った問題です.当時は2つの繰り返し文を用い,O(N*N)の時間的複雑さ(Brute Force)で問題を解決した.その時は時間の複雑さの概念も詳しく把握していませんでした...単純に問題を解決している事実そのものがいい…!
要するに,この問題の後続において,時間的複雑さをO(N*N)に低減できるかどうかに焦点を当てる.今回はその方法を考えました.
1.まず私が解く方法です.時間的複雑さもO(Nlogn)で解く方法である.ダブルポインタを使用しました.

nums並べ替え先.このときの時間的複雑度はO(Nlogn)である.その後、2つのポインタを用いて並べ替えられるnums並べ替え(以下、sortedという)では、sorted[start] + sorted[end]の総和に基づいて分割処理を行い、その和targetが大きいとendポインタを1マス前に移動し、逆にstartポインタを1マス前に移動する.targetと等しい瞬間が現れると、2つの要素が元numsに並んでいる指数が答えです.

2.時間的複雑度O(N)の方法.Hash mapを使用します.

まず、hashすでにhash[target-n]オブジェクト内に存在する場合、hashという名前のオブジェクトを作成し、重複文を迂回しますか?

これが正解という意味なので、このloopを回すときのindexとhash[target-n]が正解です.

修正、指摘を歓迎します!

質問リンク

https://leetcode.com/problems/two-sum/

LeetCode GitHub

https://github.com/tTab1204/LeetCode