題目-來自編程之美

給定一個(gè)數(shù)組，快速從其中找出兩個(gè)數(shù)滿足其之和等于給定的數(shù)鬼佣，這里假設(shè)其中至少存在一組符合要求的解驶拱；

分析

這里的關(guān)鍵在于快速

• 最為愚鈍的方式當(dāng)然是：窮舉，從數(shù)組中任意取出兩個(gè)數(shù)字進(jìn)行判斷晶衷，但是時(shí)間復(fù)雜度為;
• 一般是數(shù)組蓝纲，首先進(jìn)行排序阴孟，采用時(shí)間復(fù)雜度為, 然后通過一次遍歷求出所需的解，時(shí)間復(fù)雜度為税迷， 所以整個(gè)時(shí)間復(fù)雜度為永丝，
  • 書中分析： 令i = 0, j = n - 1, 查看arr[i] + arr[j]是否等于sum，如果是則結(jié)束箭养，否則判斷大小慕嚷，如果小于sum，則i++,否則j--, 這樣從兩端向中間移動(dòng)毕泌，則一定會(huì)找到的喝检。
  • 同時(shí)我借助快排思想中移動(dòng)，上面每次只移動(dòng)一個(gè)位置撼泛，能不能一次移動(dòng)多個(gè)挠说，這樣在兩個(gè)目標(biāo)數(shù)距離比較近時(shí)，能過更加快速的找到愿题。詳見代碼损俭！事實(shí)證明可行！

實(shí)現(xiàn)(java)

package com.jiajia.find;

/**
 * @ClassName: FindTowNum
 * @Author: fanjiajia
 * @Date: 2019/3/7 下午7:28
 * @Version: 1.0
 * @Description: 在一個(gè)序列中快速查找兩個(gè)滿足條件的兩個(gè)數(shù)
 */
public class FindTowNum {

    public static void main(String[] args) {

        int[] arr = {2,3,9,5,7,8,4,6};

        function(arr, 14);

    }


    private static void function(int[] arr, int targetNum) {
        // 先排序（從小到大）
        quickSort(arr, 0, arr.length - 1);
        // 方法1：每次只移動(dòng)一個(gè)下標(biāo)
        boolean flag = false;   // 方法1是否尋找到
        for (int i = 0, j = arr.length - 1; i < j; ){
            if (arr[i] + arr[j] == targetNum){
                System.out.println("方法1->存在兩個(gè)數(shù)潘酗，分別為:" + arr[i] + "," + arr[j]);
                flag = true;
                break;
            }else if (arr[i] + arr[j] < targetNum){
                i++;
            }else {
                j--;
            }
        }
        if (!flag){
            System.out.println("不存在");
        }

        // 方法2
        int i = 0, j = arr.length - 1;
        while (i < j && (arr[i] + arr[j] != targetNum)) { // i 和 j不可能重合
            while (arr[i] + arr[j] < targetNum && i < j) { // 移動(dòng)i
                i++;
            }
            while (arr[i] + arr[j] > targetNum && i < j) { // 移動(dòng)j
                j--;
            }
        }
        if (i < j){
            System.out.println("方法2->存在兩個(gè)數(shù)杆兵，分別為:" + arr[i] + "," + arr[j]);
        }else {
            System.out.println("不存在");
        }
    }

    /**
     * 快排
     * @param arr
     * @param left
     * @param right
     */
    private static  void quickSort(int[] arr, int left, int right){

        if (left >= right) {    // 必須加
            return;
        }

        int temp = arr[left]; // 以左邊的元素為基準(zhǔn)元素
        int i = left, j = right; // i,j為兩個(gè)游標(biāo)
        while (i < j) {
            while (i < j && arr[j] >= temp){ // 右邊先走
                j--;
            }
            while (i < j && arr[i] <= temp) {
                i++;
            }
            if (i < j) {
                swap(arr, i, j);
            }
        }
        arr[left] = arr[i]; // 注意，這一步必須要崎脉，填上最左邊的坑
        arr[i] = temp; // 基準(zhǔn)元素就位
        quickSort(arr, left, i - 1);    // 遞歸操作左邊部分
        quickSort(arr, i + 1, right);   // 遞歸操作右邊部分
    }

    /**
     * 交換兩個(gè)元素
     * @param arr
     * @param i
     * @param j
     */
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}

最后

此致拧咳，敬禮！