数组中2个数之和为target
题⽬
数组中到所有的和为target的整数对
例如：数组 [1,8,7,4,4,5,2,4,10,0]，target为8
结果为：(0，8)(1，7)(4，4)
因为：0+8=8，1+7=8，4+4=8
数学数组的定义是什么
解题思路
1. 数组nums[]按照升序排序
2. 定义两个下标，i指向第⼀个元素，j指向最后⼀个元素
3. 求和当前两个数组元素(nums[i] + nums[j])，并且与target相⽐较
3.1. 如果nums[i] + nums[j]等于target，记录下来当前两个数。i加1(向右移动⼀位)，如果新的nums[i]与旧的nums[i]值相同，继续加1，
直到不相同为⽌，且i不可以超过j，这么做是为了过滤掉重复的数字对；j与i正好相反，j减1(向左移动⼀位)，如果新的nums[j]与旧的nums[j]相等，继续j减1，直到不相等且j不可以⼩于i。
3.2. 如果nums[i] + nums[j]⼤于target，也就是nums[i] + nums[j]这两个值之和需要减⼩，那么在升序的数组中，后⾯的坐标j就需要向左
移动，j⾃减1。
3.3. 如果nums[i] + nums[j]⼩于target，也就是nums[i] + nums[j]这两个值之和需要增加，i⾃增1。
4. 持续上⾯第3步的操作，直到遍历完整个数组，得到所有的数字对。
上⾯的算法，假设数组长度为n，时间复杂度就是O(n)，因为只遍历了⼀次数组。
在这道题中⽐较容易想到的，并且符合直觉的想法就是两次循环遍历数组，把数组的每⼀个元素都与数组其他元素加和⽐较，到最终结果，此时时间复杂度O(n*n)。⽽关于上⾯的算法，⽐较有疑问的地⽅就是i和j同时移动会不会漏掉⼀些数据对呢？
证明上⾯时间复杂度O(n)的算法可⾏
如果完整的证明需要使⽤数学归纳法，这⾥⽤不太标准，但是容易理解的⽅法证明上⾯的算法。
已知数组nums[]升序，两个下标，前⾯的下标为i，后⾯的下标为j，⽬标值为target。
现在假设nums[i] + nums[j] > target，
按照算法此时应该执⾏j--，如果错过了某个符合结果的数据对，那么这个数据对只可能在0-i的区间，因为⼤于i区间，nums[i] + nums[j]的和只会更⼤。
⽽nums[0]与nums[i]之间的元素已经被遍历过了，遍历的时候，是在j更⼤，nums[i] + nums[j]⼩于target的情况下，i加1。所以nums[0]与nums[i]之间的元素与当前的下标j对应的nums[j]求和，只会更⼩于target。所以在nums[i] + nums[j] > target时，执⾏j--，移动j不会错过数据对。
同样地，另外两种情况nums[i] + nums[j]⼩于和等于target的情况，推导过程与⼤于相反。
代码
细节在代码中已经注释，main⽅法⽤于测试结果，也写在类中了。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。