题目描述

给定一个整数数组 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)排序+双指针解法

基本思路如下：（证明的过程用的是非形式化描述）

1. 首先将数组 按非降序序 排序。
2. 定义两个下标，head和tail，分别指向数组的首个元素和最后一个元素。
3. 如果tail下标比head下标大，说明head和tail指向了两个不同的元素，那么比较head和tail对应元素的和sum。
4. 如果sum比target大，那么将head往前移（即加一）无济于事，只会让sum变得更大，所以我们将tail往后移（即减一）。
5. 如果sum比target小，那么将tail往后移无济于事，只会让sum变得更小，所以我们将head往前移（即加一）。

由于题目要求是返回数组的原下标，而我们的数组已经被排序过了，原来的下标已经被打乱，所以我这里的解法是引入一个类Item用来保存数组元素，组成新的数组，并单独配置一个index保存数组原来的下标，这样即使Item数组被排序，原来的索引依然保留。

如果我们用稍微严谨一点 循环不变式 述来论证这个方法的正确性，可以这么表达。

已知 按非降序序 的数组A[0...n-1]，有n>=2，并且数组中存在两个元素之和等于target。

1. 初始化： 当i=0且j=n-1时，必有A[i...j]中存在两个元素P和Q之和等于target。
2. 循环： 已知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。
3. 终止： 由于每一次循环，如果没找到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