leetcodeの2数の和c++解法

leetcodeの2数の和c++解法

方法一:暴力法

メソッド2:2パスハッシュテーブル

方法3:一次ハッシュテーブル

整数配列numsとターゲット値targetを指定します.この配列でターゲット値の2つの整数を見つけて、その配列の下付きを返します.
入力ごとに1つの答えしか対応しないと仮定できます.しかし、この配列の同じ要素を繰り返し利用することはできません.
例:

   nums = [2, 7, 11, 15], target = 9

   nums[0] + nums[1] = 2 + 7 = 9
     [0, 1]

方法1:暴力法
各要素xを巡り、target-xに等しい値のターゲット要素が存在するかどうかを検索します.時間複雑度:各要素に対して配列の残りの部分を遍歴して対応するターゲット要素を探そうとすると、O(n)の時間がかかり、n要素なので時間複雑度はO(n 2)である.空間複雑度:O(1).

class Solution {
public:
    vector twoSum(vector& nums, int target) {
        for(int i=0;i{i,j};
            }
        }
        return vector{};
    }
};

方法2:2パスハッシュテーブル
最初の反復:各要素の値とインデックスをテーブルに追加します.2回目の反復:各要素に対応するターゲット要素(target-nums[i])がテーブルに存在するかどうかを確認します.時間複雑度:n個の要素を含むリストを2回遍歴し,ハッシュテーブルの検索時間はO(1)であるため,時間複雑度はO(n)である.空間複雑度:必要な余分な空間は、ハッシュ・テーブルに格納されている要素の数に依存し、このテーブルにはn要素が格納されているため、空間複雑度はO(n)である.

class Solution{
public:
	vector twoSum(vector& nums, int target){
		map hash;
		for(int i=0;i{i,hash.find(t)->second};//first  map      key，second       value
  		}
		return vector();
	}
};

方法3:一次ハッシュテーブル
最初に要素を表に挿入する前に、表に現在の要素に対応するターゲット要素がすでに存在するかどうかを確認し、すでに存在する場合は、対応する解が見つかり、それを返し、存在しない場合は、次の要素を表に挿入して操作を続行します.時間複雑度:n個の要素を含むリストを1回遍歴し,ハッシュテーブルは検索するたびにO(1)の時間を費やすため,時間複雑度はO(n)である.空間複雑度:必要な余分な空間は、ハッシュ・テーブルに格納されている要素の数に依存し、このテーブルは最大n要素を格納する必要があるため、空間複雑度はO(n)である.

class Solution{
public:
	vector twoSum(vector& nums, int target){
			map hash;
			for(int i=0;i{hash.find(t)->second,i}; //                  ，             ，        
					hash[nums[i]]=i;
		}
		return vector {};
	}
};