Plain's Blog

休想打败我的生活🔥

  1. 1. 题目
  2. 2. 分析
  3. 3. Java实现

题目

一个按升序排列好的数组int[] array = -5, -1, 0, 5, 11, 13, 15, 22, 35, 46},输入一个x,int x = 31,在数据中找出和为x的两个数,例如9+22=31,要求算法的时间复杂度为O(n).

分析

本题主要的关注点在于时间复杂度要求为O(n),因为数组是按升序排序,所以可以定义指针i、j,分别从数组的两端开始遍历,如果一个a[i]+a[j]大于31,则应该让尾指针j前移,如果a[i]+a[j]小于31,则应该让头指针后移,知道找到a[i]+a[j]等于31,遍历完成。

Java实现

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
34
public class FindNumSum {
public static void main(String [] args){
int array[] = {-5, -1, 0, 5, 11, 13, 15, 22, 35, 46};
int sum = 31;
find(array,sum);
}

public static void find(int array[], int sum){

if (array.length <= 1){
System.out.println("无效的数组");
return;
}
int i = 0;
int j = array.length - 1;

while (i != j){
int temSum = array[i] + array[j];
if (temSum == sum){
System.out.println("a[" + i + "]:" + array[i] + " + "+ "a[" + j +"]:" + array[j] + " = " + temSum);
return;
}

if (temSum < sum){
i ++;
}

if (temSum > sum) {
j --;
}
}
System.out.println("未找到");
}
}

本文作者 : Plain
This blog is under a CC BY-NC-SA 3.0 Unported License
本文链接 : https://plain-dev.com/leetcode-two-sum/

本文最后更新于 天前,文中所描述的信息可能已发生改变