Leetcode 167,三种解法,最佳时间复杂度为O(n)

给定一个数,求有序数组中两个数的和刚好等于它,返回索引

最简单直接的就是两层循环,时间复杂度为O(n^2)

    public int[] twoSum(int[] numbers, int target) {
        for(int i = 0; i < numbers.length; i ++){
            for(int j = i + 1; j < numbers.length; j ++){
                if(numbers[i] + numbers[j] == target){
                    int[] index = {i+1, j+1};//index[0] = i + 1;
                    return index;
                }
            }
        }
        throw new IllegalArgumentException("the input has no solution !");
    }

第二种方法

是根据有序数组的性质,在第二层开始使用二分法进行查找
时间复杂度为O(nlog^n)

    public static int[] twoSum(int[] numbers, int target) {

        for(int i = 0; i < numbers.length; i ++){
            int l = i + 1;
            int r = numbers.length;
            while(l < r){
                int mid = l + (r - l) / 2;
                if(target - numbers[i] > numbers[mid])
                    l = mid + 1;
                else if(target - numbers[i] < numbers[mid])
                    r = mid;
                else { //target - numbers[i] == numbers[mid]
                    int[] index = {i+1, j+1};//index[0] = i + 1;
                    return index;
                }
            }
        }
     throw new IllegalArgumentException("the input has no solution !");
    }

第三种

时间复杂度为O(n),对撞指针法,设置两个指针,一左一右,如果两者相加大于target,说明数字太大了,右边的向左移,如果小于target,说明太小了,左边的往右移。

public static int[] twoSum(int[] numbers, int target) {
        
        int l = 0;
        int r = numbers.length - 1;
        while (l < r){
            if(numbers[l] + numbers[r] == target) {
                int[] index = {l + 1, r + 1};
                return index;
            }
            if(numbers[l] + numbers[r] < target)
                l++;
            if(numbers[l] + numbers[r] > target)
                r--;
        }

        throw new IllegalArgumentException("input error !");
    }
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。