LeetCode 1 two num

転載は出典を明記してください.http://leonchen1024.com/2017/02/17/1-Two-Sum/Record[Chinese%20 ver]/
[Chinese ver]1.両方の合計を求めます.整数の配列を指定して、2つの数字のインデックスを返します.この2つの数字を合わせて指定された目標値になります.各入力に少なくとも一つの解決策があると仮定してもいいです.同じ要素を二回使うことはできません.
Example:

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

まずは間違った試みです.

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] testNums = new int[nums.length];
        int j = 0;
        for (int i=0;i

問題の意味がよく分かりませんでした.この解決方法で最終的に得られたのは私達が指定した配列の番号で、問題の要求の番号ではなく、卒倒しました.その後、より深刻な問題が発見されました.彼は負数があってはいけないと言ったことがありません.つまり、配列内の値が和より大きいかどうかを判断する必要はありません.
それから改めて考えてみます.まず基本的な解法をします.

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i=0;i

結果としては、一番簡単な自然も効率的ではないです.
この方法の原理を解析するのは簡単で、各値を他の値と循環して、条件に合う状況があるかどうかを確認します.ちょっと注意したいのは、for(int k=i＋1;k時間複雑度:O(n^2)です.n個の要素は、配列内の残りの要素を巡回するので、n^2です.空間複雑度:O(1).http://leonchen1024.com/2017/02/17/1-Two-Sum/Record[Chinese ver]/33166;菗菗方法二:二次循環のhash table

public class Solution {
   public int[] twoSum(int[] numbers, int target) {
    Map map = new HashMap();
    for (int i = 0; i < numbers.length; i++) {
        map.put(numbers[i],i);
    } 
   for (int i = 0; i < numbers.length; i++) {
       int requestNum = target - numbers[i];
        if (map.containsKey(requestNum)&&map.get(requestNum)!=i) {
            return new int[]{i,map.get(requestNum)};
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}
}

効率が大幅に向上したことが見られます.
この方法の原理を分析すると、hash tableを使って時間のコストを空間のコストに変えて、複雑度をO(n)に近いサイクルをO(1)に近いルックアップに変えます.なぜ近いですか?hash tableに大量の衝突が発生すると、複雑度がO(n)に向かうからです.近くにあります.配列内の各要素の値をkeyとしてhash tableに預け入れます.そのシリアル番号を対応するvalueとしてhash tableに預け入れます.そして、対応する値がhash tableのkeyにあるかどうかを遍歴して調べます.keyに対応するvalueを取り出します.時間複雑度:O(n)空間複雑度:O(n)
璣璖33751;方法三:一回の循環のhash table

public class Solution {
   public int[] twoSum(int[] numbers, int target) {
    Map map = new HashMap();
    for (int i = 0; i < numbers.length; i++) {
       int requestNum = target - numbers[i];
        if (map.containsKey(requestNum)) {
            return new int[]{map.get(requestNum),i};
        }
        map.put(numbers[i],i);
    }
    throw new IllegalArgumentException("No two sum solution");
}
}

効率はちょっと高めました.でも、ちょっと納得できません.まだ中間の位置です..何回か試してみましたが、40%から50%ぐらいはうろうろしています.前の方は何を使っていますか?なぜそんなに早いですか?理論的には少なくとも一回のサイクルが必要です.つまり、O(n)の複雑さが必要です.
この方法の原理を分析すると、方法2の改善の一つです.すべての配列をhash tableに入れる必要はないので、私達の最終的な目的は2つの加算が目標数に等しい値の番号を取ればいいです.だから、配列の値をhash tableに入れる時に比べて、必要な値を得たらすぐに循環を終了します.複雑度:O(n)空間複雑度:O(n)
もっといい方法があったら、あるいはこちらの説明に対して他の見方があったら、連絡してください.ありがとうございます.
http://leonchen1024.com/2017/02/17/1-Two-Sum/Record[Chinese ver]/[English ver]見Git
私のGithttps://github.com/chenlinfeng 私のブログhttp://leonchen1024.com/