排序数组中的两个数字之和

题目：
输入一个递增排序的数组和一个值k，请问如何在数组中找出两个和为k的数字并返回它们的下标？假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。例如，输入数组[1,2,4,6,10]，k的值为8，数组中的数组2与6的和为8，它们的下标分别为1和3.

先在数组中固定一个数字，再依次判断数组中其余数字与它的和是否为k。
假设扫描到数字i，如果数组中存在另一个数字k-i，那么就找到了一对和为k的数字。
由于数组是递增排序的，因此可以用二分查找在数组中搜索k-i。

代码如下：

    public int[] TwoSum1(int[] arrays, int k)
    {   int a=0;
        int i=0;
        for (;i arr[middle]) {
                start = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }

二分查找的时间复杂度是O(logn)，因此优化之后的解法的时间复杂度是O(nlogn)。

先将数组中的所有数字都放入一个哈希表，然后逐一扫描数组中的每个数字。假设扫描到数字i，如果哈希表中存在另一个数字（k-i），那么就找到了一对和为k的数字。

代码如下：

    public int[] TwoSum2(int[] arrays, int k)
    {
        Map hashmap = new HashMap<>();
        for (int i=0; i 
 
 
判断哈希表中是否存在一个数字的时间复杂度是O(1)，所以此解法的时间复杂度是O(n)，空间复杂度也是O(n).
 
 
解法三： 
 
 
用两个指针P1和P2分别指向数组中的两个数字。指针P1初始化指向数组的第1个(下标为0的)数字，指针P2初始化指向数组的最后一个数字。
 ①如果指针P1和P2指向的两个数字之和等于输入的k，那么就找到了符合条件的两个数字。
 ② 如果指针P1和P2指向的两个数字之和小于k，那么我们希望两个数字的和再大一点。由于数组已经排好序，因此可以考虑把指针P1向右移动。因为在排序数组中右边的数字要大一些，所以两个数字的和也要大一些，这样就有可能等于输入的数字k。
 ③同样，当两个数字的和大于输入的数字k时，可以把指针P2向左移动，因为在排序数组中左边的数字要小一些。
 
 
代码如下
 
    public int[] TwoSum(int[] arrays, int k)
    {
        int p1=0;
        int p2=arrays.length-1;
        while (p1k)//如果两数之和小于k
            {
                p2 = p2-1;//右指针左移一位
            }else
                {
                    p1 = p1 + 1;//左指针右移一位
                }
        }
    return new int[]{p1,p2};//返回一个存储两个指针下标的数组
    }
 
由于上述代码中只有一个while循环，循环执行的次数最多等于数组的长度，因此这种思路的时间复杂度是O(n)。