LeetCode（1）之两数之和(Two Sum) | Plain's Blog

题目

一个按升序排列好的数组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实现

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("未找到");
    }
}