題目描述
給定一個整數(shù)數(shù)組 nums 和一個整數(shù)目標(biāo)值 target，請你在該數(shù)組中找出 和為目標(biāo)值 target 的那 兩個 整數(shù)呀伙，并返回它們的數(shù)組下標(biāo)。
你可以假設(shè)每種輸入只會對應(yīng)一個答案。但是日丹，數(shù)組中同一個元素在答案里不能重復(fù)出現(xiàn)。
你可以按任意順序返回答案蚯嫌。
示例 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
只會存在一個有效答案
進(jìn)階：你可以想出一個時間復(fù)雜度小于 O(n^2) 的算法嗎择示？
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/two-sum
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有束凑。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處栅盲。
解法 1：暴力O(n^2)解法
作為力扣第一題汪诉，簡單肯定是足夠簡單了。這道題的暴力解都不需要解釋谈秫，兩個for循環(huán)比較即可扒寄。
class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
for i in 0..<nums.count-1 {
for j in i+1..<nums.count {
if nums[i] + nums[j] == target {
return [i, j]
}
}
}
return [-1, -1]
}
}
解法 2：O(nlogn)排序+雙指針解法
基本思路如下：（證明的過程用的是非形式化描述）
- 首先將數(shù)組 按非降序序 排序。
- 定義兩個下標(biāo)拟烫，
head和tail旗们，分別指向數(shù)組的首個元素和最后一個元素。 - 如果
tail下標(biāo)比head下標(biāo)大构灸，說明head和tail指向了兩個不同的元素上渴，那么比較head和tail對應(yīng)元素的和sum。 - 如果
sum比target大喜颁，那么將head往前移（即加一）無濟(jì)于事稠氮，只會讓sum變得更大，所以我們將tail往后移（即減一）半开。 - 如果
sum比target小隔披，那么將tail往后移無濟(jì)于事，只會讓sum變得更小寂拆，所以我們將head往前移（即加一）奢米。
由于題目要求是返回數(shù)組的原下標(biāo)抓韩，而我們的數(shù)組已經(jīng)被排序過了，原來的下標(biāo)已經(jīng)被打亂鬓长，所以我這里的解法是引入一個類Item用來保存數(shù)組元素谒拴，組成新的數(shù)組，并單獨配置一個index保存數(shù)組原來的下標(biāo)涉波，這樣即使Item數(shù)組被排序英上，原來的索引依然保留。
如果我們用稍微嚴(yán)謹(jǐn)一點 循環(huán)不變式 述來論證這個方法的正確性啤覆，可以這么表達(dá)苍日。
已知 按非降序序 的數(shù)組A[0...n-1]，有n>=2窗声，并且數(shù)組中存在兩個元素之和等于target相恃。
-
初始化： 當(dāng)
i=0且j=n-1時，必有A[i...j]中存在兩個元素P和Q之和等于target笨觅。 -
循環(huán)： 已知
A[i...j]中存在兩個元素之和等于target豆茫，那么存在分如下三種情況：
a. 如果A[i]+A[j] > target，由于A[j...n-1]中的任何元素都不小于A[j]屋摇，所以A[j...n-1]的任何元素和A[i]相加都必然大于target揩魂，所以可知P和Q必然是存在于A[i...j-1]中。
b. 如果A[i]+A[j] < target炮温，由于A[0...i]中的任何元素都不大于A[i]火脉，所以A[0...i]的任何元素和A[j]相加都必然小于target，所以可知P和Q必然是存在于A[i+1...j]中柒啤。
c. 如果A[i]+A[j] = target倦挂，說明我們找到了P和Q。 -
終止： 由于每一次循環(huán)担巩，如果沒找到
P和Q方援，都必然會導(dǎo)致A[i...j]的查找范圍縮小1。又由于P和Q必然存在涛癌。所以最終P和Q必然被找到犯戏。
代碼如下。
class Solution {
class Item {
var index = 0
var value = 0
}
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var items = nums.map { i -> Item in
let item = Item()
item.value = i
return item
}
for i in 0..<items.count {
items[i].index = i
}
items.sort { $0.value < $1.value }
var head = 0
var tail = items.count - 1
while head < tail {
let sum = items[head].value + items[tail].value
if sum > target {
tail -= 1
} else if sum < target {
head += 1
} else {
return [items[head].index, items[tail].index]
}
}
return []
}
}
完整代碼也可以參見我的github拳话，點擊這里先匪，也可以直接訪問地址：https://github.com/FengHaiTongLuo/LeetCode4Swift/blob/main/1.%20Two%20Sum.swift
