和为s的两个数字
题目描述
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
示例：
输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]
输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]
提示：
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6
题目分析
题目划重点递增数组
-
暴力法，从第一个数开始，选定一个当前数，去和它后面的数相加，如果等于target，就返回，如果大于target，就选定下一个当前数，循环直至找到答案，时间复杂度O(N^2)，显然，这里没有把递增数组这一特性用上，时间超限。
暴力法 -
优化暴力法，前面的步骤和暴力法一样，但是在“如果大于目标”开始进行了优化，定义了一个全局变量big，当前数+nums[j]如果比target大的话，big就修改为j，下一次内层循环就到big结束，不用循环到nums.length，为什么可以这么做呢，因为数组是有序的，如果前面第i个数加第j个数比target大，那么第i+1个数加第j个数肯定比target大，所有下一次循环的终点是j-1；但是优化暴力法原理上还是双层循环，时间复杂度是O(N^2)，尝试了一下，还是时间超限。
优化暴力法 两头开工法（双指针），优化暴力法是从头加到尾，并尾部往前推，双指针法是头指针往后退，尾指针往前推，思想和优化暴力法的思想是差不多的，一开始头指针为0，尾指针为nums.length - 1
. 如果两数相加等于target，直接返回
· 如果两数相加大于target，因为头指针是有可能为答案的数里最小的数，那么头指针往后的数加尾指针都会大于target，尾指针就可以舍弃（不可能是答案），尾指针往前推
. 如果两数相加小于target，因为尾指针是有可能为答案的数里最大的数，那么尾指针往前的数加头指针都会小于target，头指针就可以舍弃（不可能为答案），头指针往后推
双指针法通过循环不断的缩小有可能为答案的范围，每一次计算都可以将两极不可能为答案的数字排除掉，因为答案是肯定存在的，所以最多只要遍历一遍就可以得到答案，时间复杂度是O(N)，显然，AC了！
fun twoSum(nums: IntArray, target: Int): IntArray {
// 优化暴力法
var big = nums.size
for (i in nums.indices) {
for (j in 0 until big) {
if (nums[i] + nums[j] == target)
return intArrayOf(nums[i], nums[j])
if (nums[i] + nums[j] > target) {
big = j
break
}
}
}
// 双指针法
var head = 0
var tail = nums.size - 1
while (head != tail){
if(nums[head] + nums[tail] == target)
return intArrayOf(nums[head],nums[tail])
if(nums[head] + nums[tail] > target)
tail--
else
head++
}
return intArrayOf(0)
}
