題目：
給定一個整數陣列nums和一個整數目標值target，請你在該陣列中找出和為目標值的那兩個整數，并回傳它們的陣列下標，你可以假設每種輸入只會對應一個答案，但是，陣列中同一個元素在答案里不能重復出現，你可以按任意順序回傳答案，
示例：
輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因為 nums[0] + nums[1] == 9 ，回傳 [0, 1]
輸入：nums = [3,2,4], target = 6
輸出：[1,2]
輸入：nums = [3,3], target = 6
輸出：[0,1]
提示：
-
2 <= nums.length <= 103 -
-109 <= nums[i] <= 109 -
-109 <= target <= 109 -
只會存在一個有效答案
思路一：暴力列舉
最直接也是最容易想到的方法是列舉陣列中的每一個數nums[i]，尋找陣列中是否存在target - nums[i]，
時間復雜度：O(N^2)
空間復雜度：O(1)
// Java代碼 class Solution { public int[] twoSum(int[] nums, int target) { int length = nums.length;// 記錄陣列元素個數 for (int i = 0; i < length; ++i) {// 列舉 for (int j = i + 1; j < length; ++j) { if (nums[i] + nums[j] == target) {// 判斷和是否等于target return new int[]{i, j};// 回傳答案下標陣列 } } } return new int[0];// 未找到答案，回傳空陣列 } }
// C++代碼 class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { int length = nums.size();// 記錄向量元素個數 for (int i = 0; i < length; ++i) {// 列舉 for (int j = i + 1; j < length; ++j) { if (nums[i] + nums[j] == target) {// 判斷和是否等于target return {i, j};// 回傳答案下標向量 } } } return {};// 未找到答案，回傳空向量 } };
思路二：哈希表
題目要求兩元素和為target，一個為nums[ i ]，則另一個為target - nums[ i ]，若創建一個哈希表(key = nums[ i ], value = https://www.cnblogs.com/Acx7/p/i)，遍歷陣列，對于每一個nums[ i ]，判斷target - nums[ i ]是否在表中，若在，則找到滿足要求的兩數，若不在，則將x和對應下標加入表中，
時間復雜度：O(N)
空間復雜度：O(N)
// Java代碼 class Solution { public int[] twoSum(int[] nums, int target) { // 記錄陣列值和對應下標 HashMap<Integer, Integer> hashtable = new HashMap<Integer, Integer>(); int length = nums.length;// 記錄陣列元素個數 for (int i = 0; i < length; ++i) {// 遍歷陣列 if (hashtable.containsKey(target - nums[i])) {// 判斷哈希表中是否存在target - x return new int[]{i, hashtable.get(target - nums[i])};// 存在則回傳陣列下標 } else { hashtable.put(nums[i], i);// 不存在則將其加入表中 } }
return new int[0];// 未找到答案，回傳空陣列 } }
// C++代碼 class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { // 記錄陣列值和對應下標 unordered_map<int, int> hashtable; int length = nums.size();// 記錄陣列元素個數 for (int i = 0; i < length; ++i) {// 遍歷陣列 auto it = hashtable.find(target - nums[i]);// 尋找哈希表中是否存在target - x if (it != hashtable.end()) {// 判斷是否在表中 return {it->second, i};// 若在表中，回傳陣列下標 } else{ hashtable[nums[i]] = i;// 不存在則將其加入表中 } } return {};// 未找到答案，回傳空向量 } };
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/271139.html
標籤：其他
上一篇：排序演算法
下一篇：排序演算法