Leetcode 167：Two Sum II - Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note：

• Your returned answers (both index1 and index2) are not zero-based.
• You may assume that each input would have exactly one solution and you may not use the same element twice.

说人话：

一个有序数组中找 2 个元素和为 target，返回它们的索引（索引从1开始）。

几个要点：

• 数组本身有序
• 索引从1开始计算
• 一个元素不能使用2次
• 本题保证有解、且是唯一解

[法1] 暴力法

思路

暴力解法思路非常清晰，就是双层遍历数组。

代码

class Solution {
    public int[] twoSum(int[] numbers, int target) {
      	int[] result = new int[2];
				for(int i=0;i<numbers.length-1;i++){
          	for(int j=i+1; j<numbers.length;j++){
              if((numbers[i] + numbers[j]) == target){
                    result[0] = i+1;
                    result[1] = j+1;
                    return result;
                } 
            }
        }
        return result;
    }
}

提交结果

代码分析

• 时间复杂度：双层遍历，很明显是 O(n²)
• 空间复杂度：O(1)

改进思路

很明显这里时间复杂度 O(n²) 是比较大的，我们改进的方向应该就是想办法尽可能少遍历数组。

暴力算法中双层遍历并没有利用到题目给的一个有用信息：数组本身有序，所以我们可以从这个突破口寻求改进的方法。

[法2] 二分查找

思路

因为数组本身有序，那么我们就想到了二分查找法。所以我们在确定了 nums[i] 后要找 nums[j] 的时候，这个时候找 nums[j] 就可以用二分查找，这样时间复杂度就优化为 O(nlogn) 了。

代码

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        //结果
        int[] result = new int[2];
        
        //遍历，首先确定 numbers[i]
        for(int i=0;i<numbers.length-1;i++){
            //二分查找 numbers[j]
            int jIndex = binarySearch(numbers,i+1,numbers.length-1, target-numbers[i]);
            if( jIndex != -1){
                result[0] = i+1;
                result[1] = jIndex+1;
            }
        }
        return result;
    }

    //二分查找法
    public int binarySearch(int[] nums, int start, int end, int target){
        //从 [start...end] 中查找
        int l = start;
        int r = end;
        while( l<=r ){
            int mid = l + (r-l)/2;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] < target){
                l = mid+1;
            }else if(nums[mid] > target){
                r = mid-1;
            }
        }
        return -1;
    }
}

提交结果

代码分析

• 时间复杂度：因为第一层遍历是循环遍历，第二层遍历是二分查找，故时间复杂度是 O(nlogn)
• 空间复杂度：O(1)

改进思路

这次我们用上了数组的有序性这个有利条件，大大降低了时间复杂度。但是有没有可能只遍历一次数组就解决问题呢？

[法3] 对撞指针

思路

因为数组本身是有序的，所以我们可以利用这个有序性，建立两个指针，一个在头一个在尾，两个不断向中间夹，直到找到两个和为 target 的元素。

整体思路：

• 建立头指针 head 和 尾指针 tail
• 计算 numbers[head] + numbers[tail] 的值
• 如果 == target，完成
• 如果 < target，则说明 numbers[head] 不够大，就 head++
• 如果 > target，则说明 numbers[tail] 太大，就 tail–
• 不断向中间夹，直到 numbers[head] + numbers[tail] == target
• 如果 head = tail，这说明找不到

代码

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        //头指针
      	int head = 0;
        //尾指针
        int tail = numbers.length-1;
        //结果
        int[] result = new int[2];
        //两边夹
        while(head < tail){
            int sum = numbers[head] + numbers[tail];
            //== target，完成
            if(sum == target){
                result[0] = head+1;
                result[1] = tail+1;
                break;
            }
            // < target，说明 numbers[head] 太小，head++
            else if(sum < target){
                head++;
            }
            // > target，说明 numbers[tail] 太大，tail++
            else if(sum > target){
                tail--;
            }
        }
        return result;
    }
}

提交结果

代码分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)