Ming
0%

LeetCode-167

Posted on Edited on In

LeetCode-167 两数之和II - 输入有序数组

题目

结果

代码

暴力法

1
2
3
4
5
6
7
8
9
10
11
12
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[]{i + 1, j + 1};
                }
            }
        }
        return null;
    }
}

二分法

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
30
31
32
33
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; i++) {
            // 如果加上最大的都小于target，那就可以进入下一轮了
            if (numbers[i] + numbers[numbers.length - 1] < target) {
                continue;
            }
            int index = search(numbers, target - numbers[i], i + 1);
            // 如果没找到
            if (index == -1) {
                continue;
            }
            return new int[]{i + 1, index + 1};
        }
        return null;
    }

    // 二分法搜索target
    public int search(int[] numbers, int target, int begin) {
        int end = numbers.length - 1;
        while (begin <= end) {
            int mid = (begin + end) / 2;
            if (numbers[mid] == target) {
                return mid;
            } else if (numbers[mid] < target) {
                begin = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return -1;
    }
}

双指针法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int begin = 0, end = numbers.length - 1;
        while (begin < end) {
            int sum = numbers[begin] + numbers[end];
            if (sum == target) {
                return new int[]{begin + 1, end + 1};
            } else if (sum < target) {
                begin++;
            } else {
                end--;
            }
        }
        return null;
    }
}

复杂度

暴力法

时间复杂度：O（n²）

空间复杂度：O（1）

二分法

时间复杂度：O（nlogn）

空间复杂度：O（1）

双指针法

时间复杂度：O（n）

空间复杂度：O（1）