【leetcode】排序数组中两个数字之和

一、 题目描述

给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 0 开始计数 ，所以答案数组应当满足

0 <= answer[0] < answer[1] < numbers.length 。

假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。

二、 思路

2.1 暴力求解

嵌套for循环，两两比较即可。

2.2 二分查找

• for循环依次遍历数组，对于特定数组元素x，在数组中使用二分查找找target-x的数。
• 二分查找本质上就是对有序数组进行的查找，O（logn）；

2.3 双指针操作

0 2 1 3 4 5 7 target=6
↑--------------↑

第一轮：0+7太大，右指针左移一个

0 2 1 3 4 5 7 target=6
↑-----------↑

第二轮：1+5太小，左指针右移一个

0 2 1 3 4 5 7 target=6
–↑---------↑
依次类推直到找到正确结果。

三、 代码

class Solution {
    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) 
                    return new int [] {Math.min(i,j),Math.max(i,j)};
            }
        }
        return numbers;        
    }
}
1
2
3
4
5
6
7
8
9
10
11

时间复杂度：O(N^2)

二分查找：

class Solution {
    // 时间复杂度：O(nlogn)
    // 空间复杂度：O(1)
    public int[] twoSum(int[] nums, int target) {
        int index=0;
        for(int i=0;i<nums.length;i++){
            // 线性查找 - O(n)
            // 1. 二分查找 - O(logn)
            // [i + 1, nums.length - 1] 区间二分查找 target - x
            if((index=binarySearch(nums,i+1,nums.length-1,target-nums[i]))!=-1){
                return new int[]{i,index};
            }
        }
        return new int [0];
    }
    public int binarySearch(int nums[],int left,int right,int target){
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]==target){
                return mid;
            }else if(nums[mid]>target){
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

双指针：

// 时间复杂度：O(n)
// 空间复杂度：O(1)
public int[] twoSum(int[] nums, int target) {
    if (nums == null || nums.length == 0) return new int[0];

    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            return new int[]{left, right};
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }

    return new int[0];
}

作者：tangweiqun
链接：https://leetcode.cn/problems/kLl5u1/solution/jian-dan-yi-dong-javac-pythonjs-liang-sh-et4y/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

时间复杂度： 0（n）