🟢 剑指 Offer II 006. 排序数组中两个数字之和

LeetCode 提示

题目难度 简单

原题链接 🔗 leetcode

题解1

二分法。时间复杂度 O(nlogn)

class Solution {    private int findPair(int[] numbers, int target, int start) {        int left = start, right = numbers.length, mid;                while (left < right) {            mid = (left + right) / 2;            if (numbers[mid] == target) {                return mid;            }            if (numbers[mid] < target) {                left = mid + 1;            } else {                right = mid;            }        }
        return -1;    }
    public int[] twoSum(int[] numbers, int target) {        for (int i=0; i<numbers.length; i+=1) {            int pair = findPair(numbers, target-numbers[i], i+1);            if (pair > i) {                return new int[]{i, pair};            }        }
        return new int[2];    }}

题解2

双指针法。时间复杂度 O(n)

class Solution {    public int[] twoSum(int[] numbers, int target) {        int left = 0, right = numbers.length-1, sum;        while (left < right) {            sum = numbers[left] + numbers[right] - target;
            if (sum == 0) {                return new int[]{left, right};            }
            if (sum > 0) {                right -= 1;            } else {                left += 1;            }        }
        return new int[2];    }}