Leetcode配列easy|1.両数の和

りょうすうの和
整数配列とターゲット値を指定し、配列とターゲット値の2つの数を見つけます.入力ごとに1つの答えしか対応せず、同じ要素が再利用できないと仮定できます.例:

   nums = [2, 7, 11, 15], target = 9
   nums[0] + nums[1] = 2 + 7 = 9
     [0, 1]

Python版
解法一:二輪遍歴.時間複雑度:O(N^2)空間複雑度:O(1)

class Solution(object):
    def twoSum(self, nums, target):
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

解法二:時間複雑度:O(N)空間複雑度:O(N)

辞書lookupを確立して最初の数字を格納し、その数字を格納するindex

lookup種が存在するか否かを判断する:target-現在の数字、表面現在値とlookup中の値をtargetに加算する.

が存在する場合、target-現在の数値のindexと現在の値のindex

が返されます.

class Solution(object):
    def twoSum(self, nums, target):
        lookup = {}
        for i, num in enumerate(nums):   
            if target - num in lookup:
                return [lookup[target-num], i]
            else:
                lookup[num] = i

Enumerate()関数は、リスト、メタグループ、文字列などの遍歴可能なデータオブジェクトをインデックスシーケンスに結合し、forループで一般的に使用されるデータとデータの下付き文字をリストするために使用されます.

seasons = ['Spring', 'Summer', 'Fall', 'Winter']

list(enumerate(seasons))

[(0, 'Spring'), (1, 'Summer'), (2, 'Fall'), (3, 'Winter')]

C++版
方案一:時間複雑度:O(NlgN)空間複雑度:O(N)
二指針法を用いて,まず配列を並べ替えて秩序ある区間を形成し,ポインタi,jはそれぞれ頭尾を指す

nums 1[i]+nums[j]>tragetの場合、j--、

nums[i]+nums[j]

nums[i]+nums[j]==target

まで

class Solution 
{
public:    #     public            
    vector twoSum(vector& nums, int target)   #       vector        vector   int
    {
        vector > nums1;   #        
        for(int i = 0;i < nums.size();++i)   # size          
            nums1.push_back(make_pair(nums[i],i));   #            
        sort(nums1.begin(),nums1.end());  # sort        
        int i = 0,j = nums1.size() - 1;   #    i      j 
        vector ret;  #      
        while(i < j)   #         
        {
            if(nums1[i].first + nums1[j].first == target)   #         nums1       
            {
                ret.push_back(nums1[i].second);   #              ret
                ret.push_back(nums1[j].second);
                return ret;   #     
            }
            nums1[i].first +nums1[j].first < target ? ++i : --j;   #      (   1)？(   2):(   3)       1        2，       3
        }
    }
};

シナリオ2:時間複雑度:O(N)空間複雑度:O(N)
c++でunordered_を提供mapの容器、unordered_mapの要素は、キー値またはマッピング値の任意の順序でソートされず、それらのハッシュ値に基づいてバケツに組織され、キー値によって単一の要素(定数平均時間複雑度を有する)に迅速にアクセスし、先に現れた要素をunorder_に格納することができる.mapでは、target-nums[i]が存在するかどうかを検索するたびに配列を巡回すればよい.

class Solution 
{
public:
   vector twoSum(vector& nums, int target)
   {
       unordered_map m;  #      m，   python       
       vector res;   #      res
       for (int i = 0; i < nums.size(); ++i) {
           m[nums[i]] = i;   #     nums     m，    ，     
       }

       for (int i = 0; i < nums.size(); ++i) {   #     
           int t = target - nums[i];    
           if (m.count(t) && m[t] != i) {      # count()   m    t  ，  1。   t， t     i
               res.push_back(i);     #         res
               res.push_back(m[t]);  #              res
               break;
           }
       }
       return res;  #         
   }
};

参考:awesome-algorithm awesome-algorithm