力扣01 求兩數之和
題目：
給定一個整數陣列，回傳兩個數字的索引，使它們加起來為一個特定的目標，
您可以假設每個輸入只有一個解決方案，并且您可能不會兩次使用同一個元素，
示例：
Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1]
注：題目大意就是在給定的一個陣列中找到兩個陣列元素之和為給定的target并且回傳這兩個陣列元素在陣列中的下標，
解法一：暴力求解
解題思路：
依次固定陣列的第一個元素，并開始遍歷陣列（從固定元素的下一個元素開始）看其他元素與固定元素加起來是否等于target若等于則回傳這兩個陣列的下標若不等于則重復此操作，
代碼：
/**
* 暴力解決：每次固定一個數再遍歷剩余陣列中的元素看這兩個數之和是否等于target
* 如果等于就回傳這兩個數在陣列中所對應的下標值
*/
public class TowSum01 {
/**
* 定義一個方法回傳型別為一個陣列，引數為指定的一個陣列以及目標值
* 回傳的陣列元素為對應兩個目標數在原來陣列中的下標值
* @param nums
* @param target
* @return
*/
public int[] towSum ( int[] nums, int target){
//1.定義一個長度為2的陣列用以存盤目標數在原來陣列中的下標值
int[] result = new int[2];
//2.第一層回圈是固定原來陣列的元素因為每一個都要固定一次
for (int i = 0; i < nums.length; i++) {
//2.1第二層回圈是尋找剩下元素是否有元素與固定的元素加起來值為target
for (int j = i + 1; j < nums.length; j++) {
//2.2將固定元素與剩下的元素加起來看值是否等于target
int sum = nums[i] + nums[j];
if (sum == target) {
//2.3如果sum等于target則將這兩個元素的下標放在result陣列中并回傳result
result[0] = i;
result[1] = j;
return result;
}
}
}
return result;
}
}
解法二：哈希表求解
解題思路：
使用哈希表求解，將原本陣列中的元素作為哈希表中的key將陣列元素對應的陣列下標作為哈希表中的value，并按照此規則將陣列放進哈希表中，遍歷此哈希表用target-key的值作為參照并在哈希表中查找是否有符合此值的key，若存在符合此值的key則回傳此key的value，
代碼：
import java.util.Hashtable;
/**
* 使用哈希表法：將原本陣列中的元素作為哈希表中的key將原本陣列中元素的下標作為哈希表中的value
* 遍歷一次原來的陣列將按照以上規則放進哈希表中
* 使用target-key看差值在哈希表中是否存在若存在則回傳value
*/
public class TowSum02 {
//1.定義一個方法，回傳值型別為長度為2的陣列，引數為一個陣列以及int型別的target
public int[] towSum(int[] nums,int target){
//2.定義一個長度為2的陣列用來存盤回傳的兩個value
int[] result = new int[2];
//3.定義一個哈希表用來存盤元本陣列的元素以及對應元素的下標值
Hashtable<Integer, Integer> map = new Hashtable<>();
//4.遍歷原本的陣列將元素作為key將下標作為value存盤在map中
for (int i = 0; i < nums.length; i++) {
map.put(nums[i],i);
}
//5.遍歷陣列元素并用target與陣列元素做差看其差值是否在map中
for (int j = 0; j < nums.length; j++) {
//5.1 target與陣列元素做差
int diff = target - nums[j];
//5.2 看差值是否在map中且不能是同一個元素
if(map.containsKey(diff) && map.get(diff) != j){
//6.將陣列的下標值以及map中找到對應key的value（也就是另一個下標值）放進result中
result[0] = j;
result[1] = map.get(diff);
return result;
}
}
return result;
}
}
總結： 解法一的時間復雜度為O(N2)，解法二的時間復雜度為O(N)，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/538723.html
標籤：其他
上一篇：KVC原理與資料篩選