前言：本人第一次刷LeetCode，我是按照題目順序開始刷的，第一題為“兩數之和”、即使難度為“簡單”，但仍然花費了很長時間才勉強做出來，為什么說是勉強做出來？因為我僅僅是實作了功能，但是在做法以及時間、空間復雜度上卻比較笨重且消耗了大量的資源，但仍然想借此記錄一下， 畢竟是耗費了腦細胞的勞動結晶，哈哈哈，
題目：
給定一個整數陣列 nums 和一個目標值 target，請你在該陣列中找出和為目標值的那 兩個 整數，并回傳他們的陣列下標，
你可以假設每種輸入只會對應一個答案，但是，陣列中同一個元素不能使用兩遍，
示例:
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
所以回傳 [0, 1]
以下是解題代碼：
public class Solution {
public int[] twoSum(int[] nums, int target) {
// 定義一個陣列接識訓傳的兩個陣列下標
int[] indexes = new int[2];
// 外層回圈：所有數相加需要回圈陣列length-1次
// (例如：4個數需要經過第一次回圈：1和2、3、4相加；第二次回圈：2和3、4相加；第三次回圈：3和4相加，共三次)
for (int i = 0; i < nums.length - 1; i++) {
// 定義內層回圈依次相加的陣列的下標（例如：第一次回圈的2、3、4；第二次回圈的3、4；第三次回圈的4）
int k = i + 1;
// 內層回圈：每次回圈需要陣列length-1-i次
// (例如：1和2、3、4相加回圈3次；2和3、4相加回圈2次；3和4相加回圈1次)
for (int j = 0; j < nums.length - 1 - i; j++) {
// 依次通過相加檢驗是否與目標值相等，如果相等，分別將兩數對應的當前變數存入事先定義好的陣列中，確定為下標
if (nums[j] + nums[k] == target) {
indexes[0] = j;
indexes[1] = k;
}
k++;
}
}
return indexes;
}
}
這是我剛剛又重新提交了一次的執行結果反饋：
于是我帶著挫敗又虛心的心態去查看學習了別人提交的代碼以及官方答案，不得不說：簡潔易于理解、思路清晰的解題方法與思路真是讓我無比佩服，證明了我要學的還有太多了
官方方法一：暴力法
暴力法很簡單，遍歷每個元素 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(n^2)
對于每個元素，我們試圖通過遍歷陣列的其余部分來尋找它所對應的目標元素，這將耗費 O(n)的時間，因此時間復雜度為 O(n^2)
- 空間復雜度：O(1)
當然這只是其中一種解決方法，官方還給出了：
方法二：兩遍哈希表（包含有 n 個元素的串列遍歷兩次，由于哈希表將查找時間縮短到 O(1) ，所以時間復雜度為 O(n)）
方法三：一遍哈希表（只遍歷了包含有 n 個元素的串列一次，在表中進行的每次查找只花費 O(1) 的時間）
以上兩種方法皆降低了時間復雜度，提高了演算法的效率，在這里就不詳細列舉了，大家可以在兩數之和-題解中仔細研究，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/21337.html
標籤：其他