编程之美_010快速寻找满足条件的两个数

时间:2023-02-22 19:29:07
// 快速寻找满足条件的两个数
// 数组中两个数的和满足指定结果
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--;
            }
        }
    }
}