Eric's Blogs

Better Code, Better Life

0%

和为S的两个数字

发表于 分类于
本文字数： 913 阅读时长 ≈ 1 分钟

题目描述

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

输出描述:

1
对应每个测试案例，输出两个数，小的先输出。

解答

两层遍历，O(N^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
    ArrayList<Integer> ans = new ArrayList<>();
    for (int i = 0; i < array.length; i++) {

        for (int j = array.length - 1; j >= 0; j--) {
            if (array[i] + array[j] < sum) {
                break;
            } else if (array[i] + array[j] == sum) {
                ans.add(array[i]);
                ans.add(array[j]);
                return ans;
            }
        }
    }
    return ans;
}

更快的做法，O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
    ArrayList<Integer> ans = new ArrayList<>();
    int i = 0, j = array.length - 1;
    while (i != j && i < array.length && j > 0) {
        if (array[i] + array[j] < sum) {
            i++;
        } else if (array[i] + array[j] > sum) {
            j--;
        } else {
            ans.add(array[i]);
            ans.add(array[j]);
            break;
        }
    }
    return ans;

}