初心者がLeetCode解いてみたSeason1(1.TwoSum)

LeetCode(1. TwoSum)

整数numsと整数targetの配列が与えられたとき、それらが足し合わされてtargetになるような2つの数値の添字を返す。 各入力は正確に1つの解を持つと仮定してよく、同じ要素を2度使ってはならない。 答えはどのような順番でも返すことができる。

public class Solutions {
    public int[] TwoSums(int[] nums, int target) {

    }
}

まずtargetにならないといけないため、配列をforループで回す。

using System;

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        var result = new int[2];

        for(var i = 0; i < nums.Length; i++) {
            for(var j = 0; j < nums.Length; j++) {
                if(i == j) continue;

                if((nums[i] + nums[j]) == target) {
                    result = [i, j];
                }
            }
        }

        return result;
    }
}public class Solutions {
    public int[]
}

この場合の結果はRuntime:164ms/Memory:47.64MBでした。

いろいろ考えてみたんですがダメでした。

解法を見てみました。

ハッシュテーブル

// nums = [3, 5, 12];
public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        var map = new Dictionary<int, int>();

        for(int i = 0; i < nums.Length; i++) {
            // map[3] = 0;
            // map[5] = 1;
            // map[12] = 2;
            map[nums[i]] = i;
        }

        for(int i = 0; i < nums.Length; i++) {
            // targetが8なら8 - 3で5がキーのmapが存在すればよい。
            int complete = target - nums[i];

            // map[complete] != iは同一の値を使わないように
            if(map.ContainsKey(complete) && map[complete] != i) {
                return new int[] {i, map[complete]};
            }
        }

        return null;
    }
}

ワンタイムハッシュ

上記の場合だと二回ループを回さなければいけないですが、下記だと、違った場合次の要素を単一のループの最後で入れることで、可能になります。

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        var map = new Dictionary<int, int>();

        for(var i = 0; i < nums.Length; i++) {
            int complete = target - nums[i];

            if(map.ContainsKey(complete) && map[complete] != i) {
                return new int[] {i, map[complete]};
            }

            map[nums[i]] = i;
        }

        return null;
    }
}