做網(wǎng)站站主需要什么條件天津提升專業(yè)關(guān)鍵詞排名
文章收錄于LeetCode專欄
LeetCode地址
兩數(shù)之和
??給定一個(gè)整數(shù)數(shù)組nums和一個(gè)整數(shù)目標(biāo)值target,請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那兩個(gè)整數(shù),并返回它們的數(shù)組下標(biāo)。
??你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案。但是數(shù)組中同一個(gè)元素在答案里不能重復(fù)出現(xiàn)。你可以按任意順序返回答案。
??示例 1:
輸入:nums = [2, 7, 11, 15], target = 9
輸出:[0, 1]
解釋:因?yàn)?nums[0] + nums[1] == 9 ,返回 [0, 1]
??示例 2:
輸入:nums = [3, 2, 4], target = 6
輸出:[1, 2]
??示例 3:
輸入:nums = [3, 3], target = 6
輸出:[0, 1]
題解
第一步審題
??給定一個(gè)數(shù)組求得其中任意兩數(shù)之和為目標(biāo)值,題目很簡(jiǎn)單就是從數(shù)組中得得等于目標(biāo)值的元素的下標(biāo)。
第二步列出所有解
??求解該題目可以采用暴力求解和hash表兩種方式。
解法一(暴力枚舉)
??所謂暴力枚舉就是采用兩層循環(huán),每層循環(huán)取出數(shù)組中一個(gè)元素,判斷兩層循環(huán)取出的兩個(gè)元素相加是否等于目標(biāo)值。
class Solution{public int[] twoSum(int[] nums, int target){for(int i=0; i<nums.length-1; i++){for(int j=i+1; j<nums.length; j++){if(nums[i] + nums[j] == target){return new int[]{i, j};}}}return null;}
}
解法二(hash表)
??暴力枚舉法采用了兩層循環(huán)時(shí)間復(fù)雜度較高,所以可以采用采用的空間換時(shí)間的方式,定義一個(gè)hash表來(lái)記錄遍歷過程中用過的元素及其下標(biāo),這樣再下一輪判斷的時(shí)候可以直接通過map.get(y)= target-x來(lái)判斷是否等于目標(biāo)值。
class Solution{public int[] twoSum(int[] nums, int target){Map<Integer, Integer> map = new HashMap<>();for(int i=0; i<nums.length; i++){int sub = target - nums[i];if(map.containsKey(sub)){return new int[]{map.get(sub), i};}map.put(nums[i], i);}return null;}
}
第三步復(fù)雜度分析
??暴力枚舉法使用了兩層循環(huán)且沒有使用額外的內(nèi)存空間,所以時(shí)間復(fù)雜度為O(n2),空間復(fù)雜度為O(1);hash表使用空間換時(shí)間的方法,所以時(shí)間復(fù)雜度為O(n),空間復(fù)雜度為O(n)。