【演算法思路】從入題至解題的詳細思路講解——LeetCode（1）——兩數之和
- 前言
- 題目
- 思路
- 解題
前言
演算法思路是程式員必備的一項能力，某認為刷演算法題不僅僅在于給出答案，更在于理解做題的思路流程
本文將從入題至解題，進行詳細的思路描述，希望能夠對你有所幫助
以下是本篇文章正文內容，內容僅為某個人見解，歡迎交流
題目
給定一個整數陣列 nums 和一個整數目標值 target，請你在該陣列中找出 和為目標值 的那 兩個 整數，并回傳它們的陣列下標，
你可以假設每種輸入只會對應一個答案，但是，陣列中同一個元素在答案里不能重復出現，
你可以按任意順序回傳答案，
（原題）兩數之和
示例 1：
輸入：nums = [2,7,11,15], target = 9 輸出：[0,1] 解釋：因為 nums[0] + nums[1] ==
9 ，回傳 [0, 1] ，
思路
- 在拿到這道題的初期，可以看到最終輸出的是陣列下標，那么我們可以定義一個陣列來接收要輸出的陣列下標，在主函式中以增強for回圈的方式遍歷接收陣列，輸出答案
- 本題在解題的程序中明確要求，依照一個已知的數，在容器中尋找另一個對應的值是否存在，那么這便是一個典型的K-V鍵值對的模型，所以我們可以考慮利用HashMap來解題
- 當然，我們可以采用雙層for回圈進行暴力求解，在此某不對這種方法做過多闡述
- 為什么要用哈希表呢？
- 本題在運行時需要遍歷源陣列，在遍歷的同時，記錄一些資訊，以省去一層回圈，相對于雙層for回圈的暴力解法，這是一種“以空間換時間”的方法
- 需要記錄已經遍歷過的數值和它所對應的下標，可以借助查找表來實作，查找表有兩個常用的實作 ：
- 哈希表：如果經常需要根據鍵值對存取值，而且不要求順序，那么HashMap就是理想的選擇
- 平衡二叉樹
- 在確定使用HashMap之后，一起來看下一步操作
- 我們已經建立了一個空的哈希表，如何把陣列中的資料轉入集合中呢？可以這樣操作
- 首先我們利用for回圈遍歷陣列，同時將目標值在HashMap中查找
- 如果不存在該資料，則將該數與對應的陣列下標以鍵值對的形式存入集合中
- 如果存在則回傳該數對應的鍵值，這里的鍵值就是上一步存入的陣列下標
- 至此本題大致的解題思路便已經明了了
- 需要注意的是，在做本題之前需要對HashMap所包含的方法有一定的了解，以下是本題中用到的三個HashMap中的方法
| 回傳值型別 | 方法 | 描述 |
|---|---|---|
| boolean | containsKey(Object key) | 如果此映射包含指定鍵的映射，則回傳 true |
| void | get(Object key) | 回傳到指定鍵所映射的值，或 null如果此映射包含該鍵的映射 |
| void | put(K key, V value) | 將指定的值與此映射中的指定鍵相關聯 |
解題
public class TwoSum1 {
public static void main(String[] args) {
int[] nums = {2, 7, 11, 15};
int[] result = twoSum(nums, 9);
for (int i : result) {
System.out.println(i);
}
}
public static int[] twoSum(int[] nums, int target) {
if (nums != null) {
HashMap<Integer, Integer> hashMap = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int temp = target - nums[i];
if (hashMap.containsKey(temp))
return new int[]{hashMap.get(temp), i};
else
hashMap.put(nums[i], i);
}
}
return null;
}
//以下為用for回圈的暴力解法
/*public static int[] twoSum(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return new int[0];
}
for (int i = 0; i < nums.length; i++) {
int x = nums[i];
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] == target - x) {
return new int[]{i, j};
}
}
}
return new int[0];
}*/
}
運行結果
同時也推薦看看這些文章
普歌-允異團隊-【Java知識點】這些Java學習路上你必須知道的底層原理（2）為什么介面中沒有構造方法而抽象類中有構造方法？
- 作者：CEMER216
- 本文著作權歸作者和CSDN共有，歡迎轉載，且在文章頁面明顯位置給出原文鏈接，未經作者同意必須保留此段宣告，否則保留追究法律責任的權利，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/272875.html
標籤：java