題目描述
給定一個整數陣列 nums 和一個目標值 target，請你在該陣列中找出和為目標值的那 兩個 整數，并回傳他們的陣列下標，
你可以假設每種輸入只會對應一個答案，但是，陣列中同一個元素不能使用兩遍，
示例:
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
所以回傳 [0, 1]
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/two-sum
解題思路
把陣列中的值，存盤到hashmap中，key為值，value放置index，當遍歷時發現組隊相加為目標值時，退出回圈，回傳數值對應的index，
解題代碼
下邊的代碼，執行用時：8 ms 記憶體消耗：39 MB，經過思考后發現還可以再優化，
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, String> numMap = new HashMap<Integer, String>();
//設定值和對應的index
for(int i=0;i<nums.length;i++) {
if(numMap.containsKey(nums[i])) {
numMap.put(nums[i], numMap.get(nums[i])+"_"+i);
} else {
numMap.put(nums[i], i+"");
}
}
int[] result = new int[2];
for(int i=0;i<nums.length;i++) {
//判斷兩個數值相加是否為目標值
if(numMap.containsKey(target-nums[i])) {
if((target-nums[i]) == nums[i] && !numMap.get(nums[i]).contains("_")) {
//兩個數值是相等的，但是陣列中該值只有一個
continue;
} else if((target-nums[i]) == nums[i] && numMap.get(nums[i]).contains("_")) {
//滿足要求，記錄index，回傳結果結束
String[] is = numMap.get(target-nums[i]).split("_");
result[0] = Integer.parseInt(is[0]);
result[1] = Integer.parseInt(is[1]);
break;
}
result[0] = i;
result[1] = Integer.parseInt(numMap.get(target-nums[i]));
break;
}
}
return result;
}
}
優化后的代碼，執行用時：3 ms 記憶體消耗：37.8 MB，
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
//存盤數值和下標的hashmap
Map<Integer, Integer> numMap = new HashMap<Integer, Integer>();
for(int i=0;i<nums.length;i++) {
//判斷與當前值相加等于目標數值的數是否在hashmap中
//如果存在則取當前下標，和hashmap中的下標，回傳
//如果不存在把數值作為key，index作為value，存盤到hashmap中
if(numMap.containsKey(target-nums[i])) {
result[1] = i;
result[0] = numMap.get(target-nums[i]);
break;
} else {
numMap.put(nums[i], i);
}
}
return result;
}
}
代碼倉庫
gitee：https://gitee.com/Tong_Cheng_Yu/leetcode/tree/master
github：https://github.com/t-c-y/leetcode
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/5286.html
標籤：其他