優質博文：IT-BLOG-CN

一、題目

給定一個整數數組nums和一個整數目標值target，請你在該數組中找出"和"為目標值target的那兩個整數，并返回它們的數組下標。

你可以假設每種輸入只會對應一個答案。但是，數組中同一個元素在答案里不能重復出現。

你可以按任意順序返回答案。

示例 1：
輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因為nums[0] + nums[1] == 9，返回[0, 1]。

示例 2：
輸入：nums = [3,2,4], target = 6
輸出：[1,2]

示例 3：
輸入：nums = [3,3], target = 6
輸出：[0,1]

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只會存在一個有效答案

進階： 你可以想出一個時間復雜度小于O(n2)的算法嗎？

二、代碼

哈希表思路：
【1】先獲取數組中的第一個元素，通過target - num[i] = x，直接過去x的下標，存在直接返回當前索引和查詢到的索引，但需要對[3,3]=6等特殊場景進行處理。
【2】們發現這個題目屬于hash表下面的，所以使用hash表來實現。可以用key保存數值，用value在保存數值所在的下標。map中的存儲結構為{key：數據元素，value：數組元素對應的下表}

在遍歷數組的時候，只需要向map去查詢是否存在target - num[i] = x中的x，如果存在，就返回value也就是下標和i，如果沒有，就把目前遍歷的元素放進map中，因為map存放的就是我們訪問過的元素。

class Solution {public int[] twoSum(int[] nums, int target) {// 先獲取數組中的第一個元素，通過 target - num[i] = x， 直接過去x的下標，存在直接返回，需要對[3,3]相同的做特殊處理。// 我們發現這個題目屬于 hash表下面的，所以使用hash表來實現。可以用key保存數值，用value在保存數值所在的下標// map中的存儲結構為 {key：數據元素，value：數組元素對應的下表}int[] res = new int[2];Map<Integer,Integer> map = new HashMap();for (int i = 0; i < nums.length; i++) {int x = target - nums[i];if (map.containsKey(x)) {res[0] = map.get(x);res[1] = i;return res;}map.put(nums[i], i);}return res;}
}

時間復雜度： O(N)，其中N是數組中的元素數量。對于每一個元素x，我們可以O(1)地尋找target - x。
空間復雜度： O(N)，其中N是數組中的元素數量。主要為哈希表的開銷。

暴力枚舉： 最容易想到的方法是枚舉數組中的每一個數x，尋找數組中是否存在target - x。

當我們使用遍歷整個數組的方式尋找target - x時，需要注意到每一個位于x之前的元素都已經和x匹配過，因此不需要再進行匹配。而每一個元素不能被使用兩次，所以我們只需要在x后面的元素中尋找target - x。

class Solution {public int[] twoSum(int[] nums, int target) {int n = nums.length;for (int i = 0; i < n; ++i) {for (int j = i + 1; j < n; ++j) {if (nums[i] + nums[j] == target) {return new int[]{i, j};}}}return new int[0];}
}

時間復雜度： O(N^2)，其中N是數組中的元素數量。最壞情況下數組中任意兩個數都要被匹配一次。
空間復雜度： O(1)。

思考：
1、如果nums是有序的，是否還需要哈希表？換句話說，能否做到O(1)額外空間？
2、如果要求尋找三個數，它們的和等于target呢？

含有重復元素的兩數之和（字節算法工程師面試題） ：給定一個可能包含重復元素的有序數組，以及一個目標值target。計算數組中有多少對兩個整數的組合滿足和等于target。
示例1： nums=[2,2,2,2], target= 4, ans=6
示例2： nums=[1,1,2,2,2,2,3,3], target=4, ans=10
示例3： nums=[1,1,1,1], target=4, ans=0

其實第一眼看上去倒也不難，就是一個變體的兩數之和。所以剛開始的思路就是先統計每一個數出現的次數，然后再按照兩數之和的方法去算，只不過算的時候要考慮兩個數出現的次數相乘才是所有的組合。

但是面試官說還有更好的，讓我往三數之和上想。但是我想偏了，我一直想的是在三數之和中如果當前數和前一個數相等，那么會直接跳過。這里的話應該是可以根據前一個數對答案的貢獻度直接推出來當前數的貢獻度的。比如[1,1,2,2,2,2,4,4]的測試用例，首先第一次計算出第一個1對結果的貢獻度是2之后，指針右移，又遇到一個1，那么可以不用計算，直接加上上一次的答案，同理，第一次遇到2也是，但是由于2 = 4 - 2，所以，第二次遇到2的時候，不能直接加上上一次的答案，應該加上上一次的答案-1。

import bisect
def solve(nums, target):ans = 0pre = 0for i, num in enumerate(nums):if num == target - num:r = bisect.bisect_right(nums, num)ans += (r - i) * (r - i - 1) // 2return ansif i > 0 and nums[i-1] == num:ans += precontinuel, r = bisect.bisect_left(nums, target - num), bisect.bisect_right(nums, target - num)if l < r:ans += r - lpre = r - lreturn ans

面試完又想了一下另一個思路，可以按照三數之和內層循環的思路，用兩個指針分別指向首尾，
1、如果這兩個數的和小于taregt，右移左指針，
2、如果大于target，左移右指針。
3、如果等于target，分情況討論
4、如果兩個數相等，可以直接計算，然后終止循環。因為數組有序，繼續循環下去也沒意義。
5、如果兩個數不相等，分別計算出左右兩個數出現的次數。然后再計算對答案的貢獻度。

時間復雜度： 因為每個數最多只會遍歷一次，所以是O(n)
空間復雜度： 只需要常數級的額外空間，所以是：O(1)

class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:ans = 0left, right = 0, len(nums) - 1while left <= right:current_sum = nums[left] + nums[right]if current_sum == target:# 找到一組滿足條件的組合if nums[left] == nums[right]:ans += (right - left + 1) * (right - left) // 2break# 統計左右兩個數各自出現的次數left_num, right_num = 1, 1left += 1right -= 1while left <= right and nums[left] == nums[left - 1]:left_num += 1left += 1while left <= right and nums[right] == nums[right + 1]:right_num += 1right -= 1ans += left_num * right_numelif current_sum < target:left += 1else:right -= 1return ans