曉之以理動(dòng)之以碼.png
一浅辙，題目
給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那 兩個(gè) 整數(shù)鸽捻，并返回他們的數(shù)組下標(biāo)泊愧。
你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案盛正。但是，你不能重復(fù)利用這個(gè)數(shù)組中同樣的元素痰滋。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/two-sum
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有敲街。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處逻恐。
二峻黍，題解
1姆涩，方案分析
-
方案1：兩次遍歷暴力破解
- ①遍歷array找到num1
- ②再次遍歷array,根據(jù)條件num1+num2=target 找到num2
- ③返回兩數(shù)的下標(biāo)
- 復(fù)雜度分析：Time:O(n^2) Space:O(1)
-
方案2：兩遍哈希表
- ①遍歷array，將每個(gè)元素以<num,index>形式存儲(chǔ)到HashMap中
- ②再次遍歷array亏栈，根據(jù)條件num1+num2=target 從map中找到num2
- ③返回兩數(shù)的下標(biāo)
- 復(fù)雜度分析：Time:O(n) Space:O(n)
-
方案3：一遍哈希表
- ①遍歷array绒北，根據(jù)條件num1+num2=target 從map中尋找num2
- ②返回兩數(shù)的下標(biāo)
- ③將每個(gè)元素以<num,index>形式存儲(chǔ)到HashMap中
- 復(fù)雜度分析：Time:O(n) Space:O(n)
-
方案4：指針?lè)ǎㄒ雅判騛rray）
- ①聲明兩個(gè)指針 left right 分別指向數(shù)組開(kāi)始和末尾
- ②如果左右指針在數(shù)組下標(biāo)取值范圍內(nèi)就進(jìn)入循環(huán)
- ③根據(jù)num1+num2=target移動(dòng)指針察署，直到找到
- ④返回 left right的值
- 復(fù)雜度分析：Time:O(n) Space:O(1)
2箕母，代碼實(shí)現(xiàn)
完整代碼：Github
方案1：暴力法
測(cè)試代碼：
/**
* Solution1: 暴力法
* 暴力法很簡(jiǎn)單嘶是，遍歷每個(gè)元素 x蛛碌，并查找是否存在一個(gè)值與 target - x 相等的目標(biāo)元素。
*
* <p>
* 復(fù)雜度分析：
* 時(shí)間復(fù)雜度：O(n^2)
* 對(duì)于每個(gè)元素希太，都需要通過(guò)遍歷數(shù)組的其余元素進(jìn)行計(jì)算來(lái)尋找目標(biāo)元素誊辉，這將耗費(fèi) O(n) 的時(shí)間亡脑。
* 因此總的時(shí)間復(fù)雜度為 O(n^2)。
*
* 空間復(fù)雜度：O(1)
* 未使用其它額外的變量存儲(chǔ)
*
* 實(shí)際測(cè)試值：
* 本環(huán)境測(cè)試：數(shù)組長(zhǎng)度5：1000 蛙紫，數(shù)組長(zhǎng)度5萬(wàn)：5 079 573
* LeetCode：時(shí)間 22 ms 內(nèi)存 36.5 MB
*/
private static void solution1() {
System.out.println("-----Solution1-----\n");
//測(cè)試數(shù)據(jù)
//隨機(jī)數(shù)組
int[] numArray = getNumArray();
//獲取隨機(jī)下標(biāo)
int[] targetIndex = getTargetIndexFromArray(numArray);
//生成target
int target = numArray[targetIndex[0]] + numArray[targetIndex[1]];
System.out.println("target:\n" + target);
//暴力法測(cè)試
//開(kāi)始時(shí)間納秒
long sTime = System.nanoTime();
//暴力法題解算法
int[] resultIndex = new Solution().twoSum1(numArray, target);
//結(jié)束時(shí)間納秒
long eTime = System.nanoTime();
System.out.println("nanoTime:\n" + (eTime - sTime));
printArray("resultIndex:", resultIndex);
}
/**
* @param numArray 給定一個(gè)整數(shù)數(shù)組
* @param target 給定一個(gè)目標(biāo)值
* @return 和為目標(biāo)值的那兩個(gè)整數(shù)的下標(biāo)
*/
public int[] twoSum1(int[] numArray, int target) {
//條件檢查
if (numArray == null || numArray.length < 2) {
return new int[2];
}
//數(shù)組中的每個(gè)元素和其它所有元素都計(jì)算一遍
for (int i = 0; i < numArray.length; i++) {
//j 從i+1開(kāi)始可以減少不必要的時(shí)間復(fù)雜度僵驰，也避免重復(fù)
for (int j = i + 1; j < numArray.length; j++) {
//如果找到了和為目標(biāo)值的那兩個(gè)整數(shù)
if (numArray[i] + numArray[j] == target) {
return new int[]{i, j};
}
}
}
//其它情況
throw new IllegalArgumentException("No two sum solution");
}
運(yùn)行結(jié)果：
-----Solution1-----
numArray:
39, 74, 13, 57, 60
target:
70
nanoTime:
11725
resultIndex:
2, 3
-----Solution1-----
numArray:
5萬(wàn)條數(shù)據(jù)（請(qǐng)自行測(cè)試）
target:
1158586
nanoTime:
4 292 020
resultIndex:
20, 6461
方案2：兩遍哈希表
測(cè)試代碼：
/**
* Solution2: 兩遍哈希表
* <p>
* 為了對(duì)運(yùn)行時(shí)間復(fù)雜度進(jìn)行優(yōu)化蒜茴，我們需要一種更有效的方法來(lái)檢查數(shù)組中是否存在目標(biāo)元素枉证。如果存在室谚，我們需要找出它的索引。
* 保持?jǐn)?shù)組中的每個(gè)元素與其索引相互對(duì)應(yīng)的最好方法是什么猪瞬？哈希表入篮。
*
* <p>通過(guò)以空間換取速度的方式潮售，我們可以將查找時(shí)間從 O(n) 降低到 O(1)。哈希表正是為此目的而構(gòu)建的鞍泉，
* 它支持以 近似恒定的時(shí)間進(jìn)行快速查找肮帐。我用“近似”來(lái)描述训枢，是因?yàn)橐坏┏霈F(xiàn)沖突，查找用時(shí)可能會(huì)退化到 O(n)睦刃。
* 但只要你仔細(xì)地挑選哈希函數(shù)十酣，在哈希表中進(jìn)行查找的用時(shí)應(yīng)當(dāng)被攤銷(xiāo)為 O(1)。
*
* <p>一個(gè)簡(jiǎn)單的實(shí)現(xiàn)使用了兩次迭代吃环。
* 在第一次迭代中郁轻，我們將每個(gè)元素的值和它的索引添加到表中。
* 在第二次迭代中竭沫，我們將檢查每個(gè)元素所對(duì)應(yīng)的目標(biāo)元素（target -nums[i]）是否存在于表中骑篙。
* 注意靶端，該目標(biāo)元素不能是 nums[i]本身！
*
* 復(fù)雜度分析：
* 時(shí)間復(fù)雜度：O(n)
* 我們把包含有 n 個(gè)元素的列表遍歷兩次脏榆。由于哈希表將查找時(shí)間縮短到 O(1) 须喂，所以時(shí)間復(fù)雜度為O(n)趁蕊。
* 空間復(fù)雜度：O(n)
* 所需的額外空間取決于哈希表中存儲(chǔ)的元素?cái)?shù)量，該表中存儲(chǔ)了 n個(gè)元素
*
* 實(shí)際測(cè)試值：
* 本環(huán)境測(cè)試：數(shù)組長(zhǎng)度5：60000 是己，數(shù)組長(zhǎng)度5萬(wàn)：1 369 711
* LeetCode：時(shí)間 4 ms 內(nèi)存 36.6 MB
*
*/
private static void solution2() {
System.out.println("-----Solution2-----\n");
//測(cè)試數(shù)據(jù)
//隨機(jī)數(shù)組
int[] numArray = getNumArray();
//獲取隨機(jī)下標(biāo)
int[] targetIndex = getTargetIndexFromArray(numArray);
//生成target
int target = numArray[targetIndex[0]] + numArray[targetIndex[1]];
System.out.println("target:\n" + target);
//開(kāi)始時(shí)間
long sTime = System.nanoTime();
//兩遍哈希表題解算法
int[] resultIndex = new Solution().twoSum2(numArray, target);
//結(jié)束時(shí)間
long eTime = System.nanoTime();
System.out.println("nanoTime:\n" + (eTime - sTime));
printArray("resultIndex:", resultIndex);
}
/**
* @param numArray 給定一個(gè)整數(shù)數(shù)組
* @param target 給定一個(gè)目標(biāo)值
* @return 和為目標(biāo)值的那兩個(gè)整數(shù)的下標(biāo)
*/
public int[] twoSum2(int[] numArray, int target) {
// 條件檢查
if (numArray == null || numArray.length < 2) {
return new int[2];
}
//初始化一個(gè)HashMap
Map<Integer, Integer> numMap = new HashMap<>();
//將數(shù)組中<元素,下標(biāo)> 轉(zhuǎn)化為Map中的<key,value>
for (int i = 0; i < numArray.length; i++) {
numMap.put(numArray[i], i);
}
//遍歷整個(gè)數(shù)組寒波，找到每個(gè)元素
for (int firstIndex = 0; firstIndex < numArray.length; firstIndex++) {
// //方式一 secondIndex
// //根據(jù)兩數(shù)之和為target嘗試獲取secondIndex
// Integer secondIndex = numMap.get(target - numArray[firstIndex]);
// //如果找到了secondIndex并且secondIndex != firstIndex
// if (secondIndex != null && secondIndex != firstIndex) {
// return new int[]{firstIndex, secondIndex};
// }
//方式二 secondNum
//根據(jù)兩數(shù)之和為target獲取 secondNum
int secondNum = target - numArray[firstIndex];
//如果map中包含secondNum并且 secondNum != firstNum
if (numMap.containsKey(secondNum) && numMap.get(secondNum) != firstIndex) {
return new int[]{firstIndex, numMap.get(secondNum)};
}
}
//其它情況
throw new IllegalArgumentException("No two sum solution");
}
運(yùn)行結(jié)果：
-----Solution2-----
numArray:
30, 28, 92, 60, 29
target:
152
nanoTime:
90198
resultIndex:
2, 3
-----Solution2-----
numArray:
5萬(wàn)條數(shù)據(jù)（請(qǐng)自行測(cè)試）
target:
1477048
nanoTime:
15 190 543
resultIndex:
7, 46604
方案3：一遍哈希表
測(cè)試代碼：
/**
* Solution3: 一遍哈希表
* 事實(shí)證明俄烁，我們可以一次完成页屠。在進(jìn)行迭代并將元素插入到表中的同時(shí)蓖柔，
* 我們還會(huì)回過(guò)頭來(lái)檢查表中是否已經(jīng)存在當(dāng)前元素所對(duì)應(yīng)的目標(biāo)元素况鸣。
* 如果它存在竹观，那我們已經(jīng)找到了對(duì)應(yīng)解臭增，并立即將其返回。
*
* 復(fù)雜度分析：
* 時(shí)間復(fù)雜度：O(n)
* 我們只遍歷了包含有 nn 個(gè)元素的列表一次列牺。在表中進(jìn)行的每次查找只花費(fèi) O(1)O(1) 的時(shí)間
* 空間復(fù)雜度：O(n)
* 所需的額外空間取決于哈希表中存儲(chǔ)的元素?cái)?shù)量拗窃，該表中存儲(chǔ)了 n個(gè)元素
*
* 實(shí)際測(cè)試值：
* 本環(huán)境測(cè)試：數(shù)組長(zhǎng)度5：50000 随夸，數(shù)組長(zhǎng)度5萬(wàn)：1 307 594
* LeetCode：時(shí)間 3 ms 內(nèi)存 37.8 MB
*/
private static void solution3() {
System.out.println("-----Solution3-----\n\n");
//測(cè)試數(shù)據(jù)
//隨機(jī)數(shù)組
int[] numArray = getNumArray();
//獲取隨機(jī)下標(biāo)
int[] targetIndex = getTargetIndexFromArray(numArray);
//生成target
int target = numArray[targetIndex[0]] + numArray[targetIndex[1]];
// int target = 6;
System.out.println("target:\n" + target);
//開(kāi)始時(shí)間
long sTime = System.nanoTime();
//一遍哈希表題解算法
int[] resultIndex = new Solution().twoSum3(numArray, target);
//結(jié)束時(shí)間
long eTime = System.nanoTime();
System.out.println("nanoTime:\n" + (eTime - sTime));
printArray("resultIndex:", resultIndex);
}
/**
* @param numArray 給定一個(gè)整數(shù)數(shù)組
* @param target 給定一個(gè)目標(biāo)值
* @return 和為目標(biāo)值的那兩個(gè)整數(shù)的下標(biāo)
*/
public int[] twoSum3(int[] numArray, int target) {
// 條件檢查
if (numArray == null || numArray.length < 2) {
return new int[2];
}
//初始化一個(gè)HashMap
Map<Integer, Integer> numMap = new HashMap<>();
//將數(shù)組中<元素,下標(biāo)> 轉(zhuǎn)化為Map中的<key,value>
for (int firstIndex = 0; firstIndex < numArray.length; firstIndex++) {
//方式一 secondIndex
// //根據(jù)兩數(shù)之和為target嘗試獲取secondIndex
// Integer secondIndex = numMap.get(target - numArray[firstIndex]);
// //如果找到了secondIndex 此時(shí)的secondIndex肯定不會(huì)和firstIndex相等的
// if (secondIndex != null) {
// return new int[]{firstIndex, secondIndex};
// }
//方式二 secondNum
//根據(jù)兩數(shù)之和為target獲取 secondNum
int secondNum = target - numArray[firstIndex];
//如果map中包含secondNum
if (numMap.containsKey(secondNum) && numMap.get(secondNum) != firstIndex) {
return new int[]{firstIndex, numMap.get(secondNum)};
}
numMap.put(numArray[firstIndex], firstIndex);
}
//其它情況
throw new IllegalArgumentException("No two sum solution");
}
運(yùn)行結(jié)果：
-----Solution3-----
numArray:
48, 26, 13, 29, 92
target:
42
nanoTime:
72273
resultIndex:
3, 2
-----Solution3-----
numArray:
5萬(wàn)條數(shù)據(jù)（請(qǐng)自行測(cè)試）
target:
1439732
nanoTime:
1 179 748
resultIndex:
719, 250
方案4：指針?lè)ǎㄒ雅判騛rray）
測(cè)試代碼：
/**
* Solution4: 排序+指針 （該方案不能通過(guò)LeetCode荤西，下標(biāo)錯(cuò)亂）
* 如果給定的數(shù)據(jù)是已經(jīng)排序的,我們可以通過(guò)移動(dòng)指針來(lái)尋找和為目標(biāo)值的那兩個(gè)元素邪锌，使用指針可以避免使用額外的內(nèi)存開(kāi)銷(xiāo)
* <p>
* 復(fù)雜度分析：
* 時(shí)間復(fù)雜度：O(n)
* 最壞的情況我們的while循環(huán)會(huì)遍歷所有觅丰，所以時(shí)間復(fù)雜度為O(n)
* 空間復(fù)雜度：O(1)
* 所需的額外空間取決于哈希表中存儲(chǔ)的元素?cái)?shù)量妨退，該表中存儲(chǔ)了 n個(gè)元素
* <p>
* 實(shí)際測(cè)試值：
* 本環(huán)境測(cè)試：數(shù)組長(zhǎng)度5：10535 ，數(shù)組長(zhǎng)度5萬(wàn)：47 321
*/
private static void solution4() {
System.out.println("-----Solution4-----\n\n");
//測(cè)試數(shù)據(jù)
//隨機(jī)數(shù)組
int[] numArray = getNumArray();
//獲取隨機(jī)下標(biāo)
int[] targetIndex = getTargetIndexFromArray(numArray);
//生成target
int target = numArray[targetIndex[0]] + numArray[targetIndex[1]];
// int target = 6;
System.out.println("target:\n" + target);
//對(duì)數(shù)組排序
Arrays.sort(numArray);
printArray("sorted numArray:", numArray);
//開(kāi)始時(shí)間
long sTime = System.nanoTime();
//排序+指針題解算法
int[] resultIndex = new Solution().twoSum4(numArray, target);
//結(jié)束時(shí)間
long eTime = System.nanoTime();
System.out.println("nanoTime:\n" + (eTime - sTime));
printArray("resultIndex:", resultIndex);
}
/**
* @param numArray 給定一個(gè)整數(shù)數(shù)組
* @param target 給定一個(gè)目標(biāo)值
* @return 和為目標(biāo)值的那兩個(gè)整數(shù)的下標(biāo)
*/
public int[] twoSum4(int[] numArray, int target) {
// 條件檢查
if (numArray == null || numArray.length < 2) {
return new int[2];
}
//左指針初始指向第一個(gè)元素
int left = 0;
//右指針初始指向最后一個(gè)元素
int right = numArray.length - 1;
//如果左右指針在數(shù)組下標(biāo)取值范圍內(nèi)就進(jìn)入循環(huán)
while ((left > -1 && left < numArray.length) && (right > -1 && right < numArray.length)) {
//計(jì)算當(dāng)前左右指針?biāo)赶虻脑氐暮? int tempTarget = numArray[left] + numArray[right];
//當(dāng)前得到的tempTarget小于target，右指針是最大了懦底，所以需要將左指針向右增大移動(dòng)
if (tempTarget < target) {
left++;
}
//當(dāng)前得到的tempTarget大于target聚唐，左指針是最小了，所以需要將右指針向左減小移動(dòng)
else if (tempTarget > target) {
right--;
}
//tempTarget等于target扮惦，找到了目標(biāo)值
else {
return new int[]{left, right};
}
}
//其它情況
throw new IllegalArgumentException("No two sum solution");
}
運(yùn)行結(jié)果：
-----Solution4-----
numArray:
11, 86, 64, 75, 68
target:
150
sorted numArray:
11, 64, 68, 75, 86
nanoTime:
9675
resultIndex:
1, 4
-----Solution3-----
numArray:
5萬(wàn)條數(shù)據(jù)（請(qǐng)自行測(cè)試）
target:
680708
nanoTime:
580 795
resultIndex:
17, 33852
