题目描述
给定一个整数数组 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(n^2) 的算法吗？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解法 1：暴力O(n^2)解法
作为力扣第一题，简单肯定是足够简单了。这道题的暴力解都不需要解释，两个for循环比较即可。
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)排序+双指针解法
基本思路如下：（证明的过程用的是非形式化描述）
- 首先将数组 按非降序序 排序。
- 定义两个下标，
head和tail，分别指向数组的首个元素和最后一个元素。 - 如果
tail下标比head下标大，说明head和tail指向了两个不同的元素，那么比较head和tail对应元素的和sum。 - 如果
sum比target大，那么将head往前移（即加一）无济于事，只会让sum变得更大，所以我们将tail往后移（即减一）。 - 如果
sum比target小，那么将tail往后移无济于事，只会让sum变得更小，所以我们将head往前移（即加一）。
由于题目要求是返回数组的原下标，而我们的数组已经被排序过了，原来的下标已经被打乱，所以我这里的解法是引入一个类Item用来保存数组元素，组成新的数组，并单独配置一个index保存数组原来的下标，这样即使Item数组被排序，原来的索引依然保留。
如果我们用稍微严谨一点 循环不变式 述来论证这个方法的正确性，可以这么表达。
已知 按非降序序 的数组A[0...n-1]，有n>=2，并且数组中存在两个元素之和等于target。
-
初始化： 当
i=0且j=n-1时，必有A[i...j]中存在两个元素P和Q之和等于target。 -
循环： 已知
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。 -
终止： 由于每一次循环，如果没找到
P和Q，都必然会导致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
