两数之和（有序数组的情况）

63 阅读 0 评论 42 点赞

我是靠谱客的博主虚拟荔枝，最近开发中收集的这篇文章主要介绍两数之和（有序数组的情况），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

在LeedCode中有一个两数之和的练习，那是无序的数组。现在，对其进行深一步讨论，加入该数组是有序的，这里仅仅以升序做为例子。
找出一对索引，并返回。
分为两种情况：

找出一组索引就直接返回。
找出所有符合条件的索引，返回。

import java.util.ArrayList;
import java.util.List;

/**
 * 问题描述(初级版1.0：只需找出一组，不分先后。)：
 * 一个有序的整型数组（比如：升序。），给定一个数，求出数组中是否存在俩数之和等于这个数。
 * 如果存在，返回这俩数的索引（用长度为2的数组保存）。
 * 不存在时，返回null。
 * 比如：{1,2,4,8}
 * 传入的target=6
 * 返回值{1,2}
 * 
 * 问题描述(升级版2.0：找出所有的2个数。)：
 * 
 * 注意：
 * 实现中使用的都是升序数组。
 * @author Feng
 * 2018年9月13日下午3:14:22
 */
public class Array3 {

    /**
     * 找出数组中两个数之和为target的数在数组中的位置。
     * 任意找出一组，返回其下标。
     * @param arr
     * @param target
     * @return
     */
    public static int[] twoNumSum(int[] arr, int target) {
        int[] results = new int[2];

        final int length = arr.length;
        System.out.println("数组的length = " + length);
        for(int i = 0, j = length - 1; i < length;) {
            if(target > arr[i] + arr[j] && i != j) {
                i ++;
                continue;
            }

            if(target < arr[i] + arr[j] && i != j) {
                j --;
                continue;
            }
            results[0] = i;
            results[1] = j;
            break;
        }

        return results;
    }

    /**
     * 2.0版本：找出所有的符合上述条件的2个数的索引。
     * @param arr
     * @param target
     * @return 使用集合存储，泛型类型是数组类型。
     */
    public static List<Integer[]> listTwoSum(int[] arr, int target){
        // 过滤异常情况。
        if(arr == null || arr.length < 2) {
            throw new IllegalArgumentException("Array is exception");
        }
        // 数组中的数小于最小的2个数之和，或者大于最大的2个数之和，直接抛出异常。
        if(target <= arr[0] + arr[1] || target > arr[arr.length - 1] + arr[arr.length - 2]) {
            throw new IllegalArgumentException("target is exception");
        }

        Integer[] result = null;// 存放结果
        List<Integer[]> list = new ArrayList<>();// 存放结果集

        /* i表示数组从前至后的移动，j表示从最后一个元素往前移动。
         * 循环结束条件是，当移动到同一个数的位置结束。即arr[i] = arr[j]时。
         */ 
        for(int i = 0, j = arr.length  - 1; i != j;) {
            if(target > arr[i] + arr[j]) {
                i ++;
                continue;
            }

            if(target < arr[i] + arr[j]) {
                j --;
                continue;
            }

            // 创建数组，保存索引值，添加到集合中。
            result = new Integer[2];
            result[0] = i;
            result[1] = j;
            list.add(result);

            i ++;// 更新，左边的数往右移。
            j --;// 更新，右边的数往左移。
        }

        return list;
    }

    // 打印整型集合，其实打印的是集合中数组里面的元素。
    public static void printList(List<Integer[]> list) {
        for(int i = 0; i < list.size(); i ++) {
            Integer[] res = list.get(i);
            System.out.println("第" + (i+1) + "组索引：【" + res[0] + "," + res[1] + "】");
        }
    }

    // 测试
    public static void main(String[] args) {
        int[] arr = {1,3,4,5,7,9,10};
        int[] res = twoNumSum(arr, 14);
        // 找不到时，打印出的是[0,0]
        System.out.println(res[0] + "," + res[1]);

        // 找出所有的2个数。
        List<Integer[]> list = listTwoSum(arr, 14);
        printList(list);

    }
}