题目
一个按升序排列好的数组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/