// 快速寻找满足条件的两个数
// 数组中两个数的和满足指定结果
public class Test
{
    static int[] arr =
    {
            1, 5, 9, 3, 4, 7, 6, 2, 8
    };
    static int maxIndex = arr.length - 1;// 索引最大值
    static int sum = 11;// 求两个数的和等于的值

    public static void main(String[] args)
    {
        find1(arr);
    }

    // 1.所有数字两两组合，计算；时间复杂度O(n*n)
    // 2.先把数组排序，然后利用二分查找在数组中查找,判断sum-arr[i]是否在数组中；时间复杂度O(n*longn)
    // 3.先对数组排序i=0,j=n-1，如果:sum<arr[i]+arr[j] i++;如果:sum<arr[i]+arr[j] j--
    // 如果有序，直接两个指针两端扫描，时间O（N）；如果无序，先排序后两端扫描，时间O（N*logN+N）=O（N*logN），空间始终都为O（1）
    static void find1(int[] arr)
    {
        Arrays.sort(arr);// 对数组排序
        for (int i = 0, j = maxIndex; i < j;)
        {
            if (arr[i] + arr[j] == sum)
            {
                System.out.println(sum + " = " + arr[i] + " + " + arr[j]);
                i++;// 没有这一句死循环
            }
            else if (arr[i] + arr[j] < sum)
            {
                i++;
            }
            else
            {
                j--;
            }
        }
    }
}
//java/6695