題目描述
給定一個整數陣列 nums 和一個目標值 target，請你在該陣列中找出和為目標值的那 兩個 整數，并回傳他們的陣列下標，
你可以假設每種輸入只會對應一個答案，但是，你不能重復利用這個陣列中同樣的元素，
示例:
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
所以回傳 [0, 1]
方法一：暴力法
思路
暴力法很簡單，遍歷每個元素 x，并查找是否存在一個值與 target ? x 相等的目標元素，
代碼
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[j] == target - nums[i]) {
return new int[]{i, j};
}
}
}
throw new IllegalArgumentException("No two sum solution");
}
}
復雜度分析
- 時間復雜度：O（n2），對于每個元素，我們試圖通過遍歷陣列的其余部分來尋找它所對應的目標元素，這將耗費O（n）的時間，因此時間復雜度為O（n2），·
- 空間復雜度：O（1），
方法二：一遍哈希表（優質解法）
思路
利用HashMap 減少查詢時間
- 在暴力法中，內層回圈查找差值很浪費時間，那么如何減少查詢時間呢？利用HashMap就可以減少查詢時間，
- 使用一層回圈，每遍歷到一個元素就計算該元素與target之間的差值，然后到HashMap中尋找該差值，如果找到，則回傳兩個元素在陣列nums的下標，如果沒有找到，則將當前元素存入HashMap中（Key:nums [i] ，Value : i ），
代碼
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer,Integer> map = new HashMap<>();
int[] res = new int[2];
for (int i = 0; i < nums.length; i++) {
int dif = target - nums[i];
if (map.get(dif) != null) {
res[0] = map.get(dif);
res[1] = i;
return res;
}
map.put(nums[i],i);
}
return res;
}
}
復雜度分析
- 時間復雜度：O（n），我們只遍歷了包含有n個元素的串列一次，在表中進行的每次查找只花費O（1）的時間，
- 空間復雜度：O（n），所需的額外空間取決于哈希表中存盤的元素數量，該表最多需要存盤n個元素，
代碼優化
public class Solution {
public int[] twoSum(int[] nums, int target) {
Map<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 int[]{-1, -1};
}
}
思考
看到這個題，第一個想到的就是暴力法，確實做出來了，發現時間復雜度和空間復雜度都挺高的，hashMap的時間復雜度遠遠低于暴力法，算是用空間換時間的一種方法了，
代碼優化以后盡可能的去做，話說討論區好多大佬啊，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/117874.html
標籤：其他
上一篇：ID3演算法
下一篇：排序演算法學習（一）：冒泡排序