<算法很美> 部分习题

1.升序数组中寻找两数相加等于K
我使用的是双指针的方法,时间复杂度为o(n)
老师讲还可以通过二分法来查找(比如从第一个开始,K-arr[0],二分法寻找数组中是否存在符合条件的数)

//升序数组,找到两数之和等于K
public static int[][] findTwoNumbers(int[] arr,int k){
    int length = arr.length;
    int[][] ans = new int[length/2][2];
    int anslength  = 0;
    int left = 0;
    int right = length-1;
    //先找到最大的可能数
    while(arr[right] > k){
        right--;
    }
    //找到最小的左边可能数
    while(arr[left]+arr[right] < k ){
        left++;
    }
    while(left<right){
        int sum = arr[left] + arr[right];
        //说明数小了,左指针右移
        if(sum < k){
            left++;
            //说明数大了,右指针左移
        }else if(sum >k){
            right--;
        }else{
            ans[anslength][0] = arr[left];
            ans[anslength++][1] = arr[right];
            left++;
        }
    }
    return ans;
}


//拓展:如果是寻找三个数相加等于10呢?
public static int[][] findTwoNumbers3(int[] arr,int k){
    int length = arr.length;
    int[][] ans = new int[length/3][3];
    int ansLength = 0;
    int left = 0;
    int right = length-1;
    //先找到最大的可能数
    while(arr[right] > k){
        right--;
    }
    //找到最小的左边可能数
    while(arr[left]+arr[right] < k ){
        left++;
    }
    int mid = left+1;
    //只有找到了左指针才会改变,否则改变的是Mid
    while(mid<right) {
        //计算总和
        int sum = arr[left] + arr[right] + arr[mid];
        //如果sum>K 说明右指针向左移
        if(sum > k){
            right--;
        }else if(sum<k){
            //中间指针右移
            mid++;
        }else{
            //找到所求的三个数
            ans[ansLength][0] =  arr[left];
            ans[ansLength][1] = arr[mid];
            ans[ansLength++][2] = arr[right];
            //左指针向右移一位 此处右指针不宜改变,万一下一个数和目前下标的值也一样呢?
            left++;
            mid = left+1;
        }
    }
    return ans;
}

PS:感觉双指针应该算入门了把...