本文共 1675 字，大约阅读时间需要 5 分钟。

题目描述

输入一个递增排序的数组和一个数字s，在数组中查找两个数，是的它们的和正好是s。如果有多对数字的和等于s。输入任意一对即可。

分析

直接思路：遍历数组，去一个数字与该数字后面进行求和比较，如果和等于s则找到这两个数字，在有n个数字的数组中，时间复杂度为$O(n^2)$。

推荐解法：由于数组已经递增排序，借鉴“前后指针”的思想，使用“前后索引”，前索引初始指向0，后索引初始指向数组最后的元素，将两个索引位置的数字求和。根据数组递增排序的特性，如果和等于s，则找到这两个数字；如果和小于s，则将前索引向后移动一位（求和将会增大）；如果和大于s，则将后索引向前移动一位（求和将会减小）。循环判断即可，循环进行的条件是前索引必须小于后索引。扫描一遍就可以找出所有满足条件的数字，输出第一对即可，时间复杂度为$O(n)$。

代码：

package com.problem;public class TwoNumSum {
       public static void main(String[] args) {        TwoNumSum twoNumSum = new TwoNumSum();        int[] arr = {
  1, 2, 4, 7, 11, 15};        int s = 15;        int[] num1 = new int[1];        int[] num2 = new int[1];        System.out.println(twoNumSum.findNumsWithSum(arr, s, num1, num2));        System.out.println(num1[0] + ", " + num2[0]);    }    public boolean findNumsWithSum(int[] arr, int s, int[] num1, int[] num2) {        if(arr == null || arr.length <= 1)            return false;        boolean isFound = false;        int length = arr.length;        int leftIndex = 0;  // 左索引初始指向0        int rightIndex = length - 1;    // 右索引初始指向最后一个元素        while(leftIndex < rightIndex) {            int leftNum = arr[leftIndex];            int rightNum = arr[rightIndex];            int sum = leftNum + rightNum;            if(sum == s) {  // 前后索引所指的元素和刚好为s，则找到                num1[0] = leftNum;                num2[0] = rightNum;                isFound = true;                break;            } else if(sum < s) {    // 元素和小于s，则前索引向后移动一位（值增加）                leftIndex++;            } else if(sum > s){     // 元素和大于s,则后索引向前移动一位（值减少）                rightIndex--;            }        }        return isFound;    }}

参考

转载地址：http://mzxgi.baihongyu.com/