Posts

LeetCode [Easy] 1.Two Sum (by C/C++)

題目: Two Sum Given an array of integers, return  indices  of the two numbers such that they add up to a specific target. You may assume that each input would have  exactly  one solution, and you may not use the  same  element twice. 範例: Given nums = [2, 7, 11, 15], target = 9, Because nums[ 0 ] + nums[ 1 ] = 2 + 7 = 9, return [ 0 , 1 ]. 解法: 直觀解法:兩層迴圈比對所有組合,時間複雜度O(n^n)。  簡易的Hash:取一段len長度的hash表,通過hash function : target-nums[i]-min尋找解,時間複雜度降低到O(n)。注意:若有極端資料則不適合使用,len會過大,導致使用過多記憶體空間,造成效率過低。 註: c資料型態表達範圍 Hash Table(C++ STL : map): 註: C++ STL(map)介紹