這是一道面試題，簡(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 map new HashMap<>();

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)。