https://leetcode-cn.com/problems/two-sum/
給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target膀跌，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那 兩個(gè) 整數(shù)，并返回他們的數(shù)組下標(biāo)佳窑。
你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案届腐。但是抄谐，數(shù)組中同一個(gè)元素不能使用兩遍导狡。
示例：
給定 nums = [2, 7, 11, 15], target = 9
因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解題：
- 題目未規(guī)定時(shí)間和空間復(fù)雜度纹坐，因此最容易的實(shí)現(xiàn)就是暴力遍歷法。時(shí)間復(fù)雜度O(n2)痊夭，空間復(fù)雜度O(1)血柳。
public class Solution {
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return new int[] {i, j};
}
}
}
return null;
}
}
- 使用Map結(jié)構(gòu)，以空間換時(shí)間生兆，降低時(shí)間復(fù)雜度。時(shí)間復(fù)雜度O(n)膝宁，空間復(fù)雜度O(n)鸦难。
public class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int temp = target - nums[i];
if (map.containsKey(temp)) {
return new int[] {map.get(temp), i};
}
map.put(nums[i], i);
}
return null;
}
}
