聆聽 沉淀 傳播 … 關注微信公眾號【Java之言】，助你放棄編程之路！
每天一道演算法題，講解自己解題思路與實作；歡迎大家點評或者說出你的解題想法；也可評論想讓我講解哪道題！
文章目錄
- 題目
- 一、思路
- 二、演算法實作
- 三、上下篇
題目
給定一個整數陣列 nums 和一個整數目標值 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]
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/two-sum
一、思路
眾所周知，兩數之和，即
A+B=SUM，在已知SUM的情況下，然后又獲得一個A時，只需要找到一個數等于SUM-A，
對于一個陣列，如果我們采用遍歷兩兩相加的演算法，即對于陣列的每一個數，都要與其他數進行相加，判斷是否等于目標值，這速度是非常慢的，即時間復雜度為O(N2)，
換個角度想，只要遍歷過的數和它對應下標，能通過某種規則或者演算法（此規則和演算法要簡單并且速度要快）存放起來，后續我們再去查找這個數能快速查出來，那演算法速度就大大提高了，這樣只需要遍歷一遍陣列即可，時間復雜度為O(N)，
既要存取速度快，還能存對應的數和下標鍵值對，那就非哈希表HashMap莫屬了，
演算法步驟：
- 遍歷陣列每一個數num，通過 target-num 計算出另一個加數A；
- 在map中查找key是否等于A的值，如果存在，則回傳當前數的下標和A的下標；
- 如果不存在，則將此數num放入map中，key為num，value為num在陣列中的下標；
二、演算法實作
package com.nobody;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
/**
* @Description 給定一個整數陣列 nums 和一個整數目標值 target，請你在該陣列中找出和為目標值的那兩個整數，并回傳它們的陣列下標，
* 你可以假設每種輸入只會對應一個答案，但是，陣列中同一個元素不能使用兩遍， 你可以按任意順序回傳答案，
* 原題鏈接：https://leetcode-cn.com/problems/two-sum/
* @Author Mr.nobody
* @Date 2021/1/21
* @Version 1.0
*/
public class TwoSum {
public static int[] twoSum(int[] nums, int target) {
// 記錄每一個遍歷過的數，利用HashMap插入查找0(1)的高效率時間復雜度
Map<Integer, Integer> indexMap = new HashMap<>(16);
// 遍歷每一個數
for (int index = 0; index < nums.length; index++) {
// target-nums[index]算出另一個加數，然后在map中找有沒有這個加數
if (indexMap.get(target - nums[index]) != null) {
// 找到了，就回傳2個加數的下標
return new int[] {indexMap.get(target - nums[index]), index};
} else {
// 沒找到，就將這個數放入map中，key為這個數，value為這個數的下標
indexMap.put(nums[index], index);
}
}
return null;
}
// 測驗
public static void main(String[] args) {
System.out.println(Arrays.toString(twoSum(new int[] {1, 2, 6, 4, 10, 11, 8, 9}, 16)));
}
}
輸出結果：
[2, 4]
Leetcode執行結果：
三、上下篇
下一篇：思路講解與演算法實作 LeetCode - 兩數相加
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/251746.html
標籤：java