Leetcode 167:Two Sum II - Input array is sorted

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;
    }
}
提交结果
Leetcode 167:Two Sum II - Input array is sorted
代码分析
  • 时间复杂度:双层遍历,很明显是 O(n2)
  • 空间复杂度:O(1)
改进思路

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

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

[法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;
    }
}
提交结果
Leetcode 167:Two Sum II - Input array is sorted
代码分析
  • 时间复杂度:因为第一层遍历是循环遍历,第二层遍历是二分查找,故时间复杂度是 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;
    }
}
提交结果
Leetcode 167:Two Sum II - Input array is sorted
代码分析
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)
上一篇:Ivan and Powers of Two


下一篇:在Netbeans上配置Android开发环境