如何判斷數(shù)組中是否存在和為指定值的兩個(gè)數(shù)
這是一道面試題,簡(jiǎn)稱為“兩數(shù)之和”,即給定一個(gè)值 n 和一個(gè)數(shù)組 nums,判斷數(shù)組 nums 中是否存在兩個(gè)數(shù),其和值為 n。本篇經(jīng)驗(yàn)將分享兩種算法,其時(shí)間復(fù)雜度分別為 O(n^2) 和 O(n)。
這是一道面試題,簡(jiǎn)稱為“兩數(shù)之和”,即給定一個(gè)值 n 和一個(gè)數(shù)組 nums,判斷數(shù)組 nums 中是否存在兩個(gè)數(shù),其和值為 n。本篇經(jīng)驗(yàn)將分享兩種算法,其時(shí)間復(fù)雜度分別為 O(n^2) 和 O(n)。注意:數(shù)組可以包含重復(fù)元素,但每個(gè)元素只允許使用一次。
算法一:雙重遍歷
實(shí)現(xiàn)基于雙重遍歷的普通算法,算法思想為:通過(guò)雙重循環(huán),遍歷數(shù)組中每一組兩數(shù)組和,如果和值為指定值,則返回 true,否則返回 false。
```
public boolean twoSum(int[] nums, int target) {
for (int i 0; i < nums.length; i ) {
for (int j i 1; j < nums.length; j ) {
if (nums[i] nums[j] target) {
return true;
}
}
}
return false;
}
```
算法二:使用 Map
實(shí)現(xiàn)基于 Map 的改進(jìn)算法,算法思想為:第一次遍歷數(shù)組,將數(shù)組所有元素添加到 Map 中,再次遍歷數(shù)組,對(duì)于數(shù)組的每一個(gè)值 k,判斷 Map 中是否存在 n-k(n即指定和值),如果存在,則返回 true,否則返回 false。
```
public boolean twoSum(int[] nums, int target) {
Map
for (int i 0; i < nums.length; i ) {
map.put(nums[i], i);
}
for (int i 0; i < nums.length; i ) {
int complement target - nums[i];
if ((complement) (complement) ! i) {
return true;
}
}
return false;
}
```
編寫本地測(cè)試主方法
在主方法中調(diào)用兩種算法來(lái)測(cè)試其準(zhǔn)確性。
```
public static void main(String[] args) {
int[] nums {2, 7, 11, 15};
int target 9;
Solution solution new Solution();
((nums, target));
}
```
運(yùn)行本地測(cè)試主方法
運(yùn)行本地測(cè)試主方法,觀察控制臺(tái)輸出,符合預(yù)期,兩個(gè)算法本地測(cè)試均通過(guò)。
算法復(fù)雜度分析
數(shù)組長(zhǎng)度為 n,算法一:需要雙重遍歷,時(shí)間復(fù)雜度為 O(n^2),空間復(fù)雜度為 O(1)。算法二:只需一次遍歷輔助查找時(shí)間復(fù)雜度為 O(1) 的 Map,總體時(shí)間復(fù)雜度為 O(n),空間復(fù)雜度為 O(n)。