leetcode 兩數(shù)之和
思路
給定一個整數(shù)數(shù)組
nums和一個目標值target秀菱，請你在該數(shù)組中找出和為目標值的那 兩個 整數(shù)轻腺，并返回他們的數(shù)組下標。
你可以假設每種輸入只會對應一個答案胃夏。但是，你不能重復利用這個數(shù)組中同樣的元素尝哆。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
class Solution {
public int[] twoSum(int[] nums, int target) {
// 這里寫出解
}
}
思路
- 新建一個map，用來存儲數(shù)據的數(shù)據
Map<String, Object> map = new HasMap<>();
- 循環(huán)數(shù)組將數(shù)據中的值作為key甜攀，索引作為value秋泄，存入map中
for (int i = 0 ; i < nums.length ; i ++) {
map.put(nums[i], i);
}
image
- 如上圖所示，在第一次循環(huán)賦值完畢之后规阀， map中的數(shù)據如上圖右邊所示印衔，此時再次循環(huán)數(shù)據，由題目中給出的目標值
target與循環(huán)數(shù)據得到值nums[i]可以計算得出差值target - nums[i],將這個值作為key進入map中使用map集合的方法boolean containesKey(Object key)進行查詢, 看是否存在key 如果存在那么久表示姥敛，有符合題目描述的兩個數(shù)字
for(int i = 0 ; i < nums.length ; i ++) {
int cur = target
if(map.containesKey(cur)){
return new int[]{i, map.get(cur)};
}
}
image
- 注意需要排除題目所說的相同點的情況奸焙， 最后整合的結果為
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
int result = target - nums[i];
if (map.containsKey(result) && map.get(result) != i) {
return new int[]{i, map.get(result)};
}
}
return new int[0];
}
}
