給定一個(gè)整數(shù)數(shù)組nuns和一個(gè)目標(biāo)值target串绩，請(qǐng)?jiān)跀?shù)組中找出和為目標(biāo)值的兩個(gè)整數(shù)聚凹，并返回他們的下標(biāo)构资，假設(shè)每種輸入只存在一個(gè)答案抽诉，數(shù)組中同一元素不能使用兩遍。
示例：
給定 nums = [2,7,11,15]吐绵，target = 9
nums[0] + nums[1] = 2 + 7 = 9
返回 [0,1]
方法一：暴力算法
使用遍歷法找出數(shù)組中的nums[i] + nums[j] = target的值
public int[] findNum(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 new int[0];
}
這種方式時(shí)間復(fù)雜度為O(N*N)迹淌，因?yàn)槭褂玫氖莾蓪忧短妆闅v；空間復(fù)雜度為O(1)己单，沒有占用額外空間
方法二：使用HashMap
通過HashMap的特性唉窃，在不考慮哈希沖突的情況下找到特定值的時(shí)間復(fù)雜度為O(1)來實(shí)現(xiàn)；即我們用HashMap存儲(chǔ)key為nums[i]纹笼，value為i纹份，遍歷nums數(shù)組，查找HashMap中是否有target - nums[i]的key
public int[] findNum2(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
return new int[]{map.get(target - nums[i]), i};
}
map.put(nums[i], i);
}
return new int[0];
}
這種方式時(shí)間復(fù)雜度為O(N)允乐，只需要遍歷一次矮嫉；空間復(fù)雜度為O(N)，需要?jiǎng)?chuàng)建HashMap申請(qǐng)額外空間
