這是一道面試題，簡稱為“兩數(shù)之和”，即給定一個值 n 和一個數(shù)組 nums，判斷數(shù)組 nums 中是否存在兩個數(shù)，其和值為 n。本篇經驗將分享兩種算法，其時間復雜度分別為 O(n^2) 和 O(n)。

這是一道面試題，簡稱為“兩數(shù)之和”，即給定一個值 n 和一個數(shù)組 nums，判斷數(shù)組 nums 中是否存在兩個數(shù)，其和值為 n。本篇經驗將分享兩種算法，其時間復雜度分別為 O(n^2) 和 O(n)。注意：數(shù)組可以包含重復元素，但每個元素只允許使用一次。

算法一：雙重遍歷

實現(xiàn)基于雙重遍歷的普通算法，算法思想為：通過雙重循環(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

實現(xiàn)基于 Map 的改進算法，算法思想為：第一次遍歷數(shù)組，將數(shù)組所有元素添加到 Map 中，再次遍歷數(shù)組，對于數(shù)組的每一個值 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;

}

```

編寫本地測試主方法

在主方法中調用兩種算法來測試其準確性。

```

public static void main(String[] args) {

int[] nums {2, 7, 11, 15};

int target 9;

Solution solution new Solution();

((nums, target));

}

```

運行本地測試主方法

運行本地測試主方法，觀察控制臺輸出，符合預期，兩個算法本地測試均通過。

算法復雜度分析

數(shù)組長度為 n，算法一：需要雙重遍歷，時間復雜度為 O(n^2)，空間復雜度為 O(1)。算法二：只需一次遍歷輔助查找時間復雜度為 O(1) 的 Map，總體時間復雜度為 O(n)，空間復雜度為 O(n)。