題目資訊
源地址：兩數之和
給定一個整數陣列 nums 和一個整數目標值 target，請你在該陣列中找出和為目標值 target 的那兩個整數，并回傳它們的陣列下標，
你可以假設每種輸入只會對應一個答案，但是，陣列中同一個元素在答案里不能重復出現，
你可以按任意順序回傳答案，
提示資訊
示例 1
輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因為 nums[0] + nums[1] == 9 ，回傳 [0, 1] ，
示例 2
輸入：nums = [3,2,4], target = 6
輸出：[1,2]
示例 3
輸入：nums = [3,3], target = 6
輸出：[0,1]
限制
2 <= nums.length <= 10^3-10^9 <= nums[i] <= 10^9-10^9 <= target <= 10^9- 只會存在一個有效答案
實作邏輯
暴力列舉
最先想到的邏輯肯定是使用雙層回圈暴力查找，
當然，采用這種方式的時間復雜度是 \(O(n^2)\)，空間復雜度是 \(O(1)\)，實際效率是非常地低，
package cn.fatedeity.algorithm.leetcode;
public class TwoSum {
public int[] answer(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];
}
}
哈希匹配
如果采用“空間換時間”的方法，利用哈希表結構查找時間復雜度為 \(O(1)\) 的特性，就可以一次回圈快速得到結果，
最終，時間復雜度降到 \(O(n)\)，空間復雜度則變成 \(O(n)\)，
package cn.fatedeity.algorithm.leetcode;
import java.util.HashMap;
public class TwoSum {
public int[] answer(int[] nums, int target) {
HashMap<Integer, Integer> hashMap = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int diff = target - nums[i];
if (hashMap.containsKey(diff)) {
return new int[]{hashMap.get(diff), i};
}
hashMap.put(nums[i], i);
}
return new int[0];
}
}
首發于翔仔的個人博客，點擊查看更多，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/498738.html
標籤：其他
上一篇：RS-485通信介面編碼器