題目大意：

??找到數(shù)組中兩個(gè)元素相加等于指定數(shù)的所有組合

情況一：給定數(shù)組中不含重復(fù)元素厌处，且均為正整數(shù)

思路：

??使用Hash表存儲(chǔ)數(shù)組各元素是否存在的標(biāo)志行瑞，然后遍歷數(shù)組叹阔，判斷sum與當(dāng)前數(shù)組元素的差值是否在hash表中截酷。時(shí)間復(fù)雜度為O（n）,空間復(fù)雜度為O（n）蔓同。

代碼實(shí)現(xiàn)：

 private static List<List<Integer>> execute1(int[] array, int m) {
        List<List<Integer>> rst = new ArrayList<>();
        List<Integer> subList = new ArrayList<>();
        int size = array.length;
        int hash[] = new int[size];
        for(int i = 0; i < size; i++) {
            hash[array[i]%size] = 1;
        }

        for(int i = 0; i < size; i++) {
            int tmp = m - array[i];
            if((tmp > array[i]) && (hash[tmp%size] == 1)){
                subList.clear();
                subList.add(array[i]);
                subList.add(tmp);
                rst.add(new ArrayList<>(subList));
            }


        }
        return rst;
    }

情況二：給定數(shù)組是有序的

思路：

??遍歷數(shù)組饶辙，判斷sum與數(shù)組元素的差值是否在數(shù)組中，由于數(shù)組有序可以采用二分查找的方法斑粱。二分查找的時(shí)間復(fù)雜度為O(logn),查找n次弃揽，總的時(shí)間復(fù)雜度為O(nlogn)，避免了空間的浪費(fèi)

代碼實(shí)現(xiàn)：

  private static  List<List<Integer>> execute2(int[] array, int m) {
        List<List<Integer>> rst = new ArrayList<>();
        List<Integer> subList = new ArrayList<>();
        for(int i = 0; i < array.length; i++) {
            int tmp = m - array[i];
            if (tmp > array[i]) {
                if (binarySearch(array, tmp) != -1) {
                    subList.clear();
                    subList.add(array[i]);
                    subList.add(tmp);
                    rst.add(new ArrayList<>(subList));
                }
            }
        }
        return rst;
    }
    private static int binarySearch(int[] array, int key) {
        if (array.length == 0) {
            return -1;
        }

        int first = 0;
        int last = array.length -1;

        int mid;
        while(first <= last) {
            mid = (first + last) / 2;
            if (array[mid] == key) {
                return mid;
            } else if (array[mid] < key) {
                first = mid + 1;
            } else {
                last = mid -1;
            }
        }
        return -1;
    }

情況三：給定數(shù)組是有序的

思路：

??使用兩個(gè)指針则北，分別指向最后一個(gè)元素和第一個(gè)元素矿微，判斷它們的和是否等于sum，若等于則添加到返回鏈表尚揣，并且first向后移動(dòng)涌矢，last向前移動(dòng)；若它們的和小于sum快骗，則說明first太小了娜庇，需要first向后移動(dòng)塔次；若它們的和大于sum，則說明last太大了名秀，需要last向前移動(dòng)俺叭，直到last>=first。時(shí)間復(fù)雜度為O（n）

代碼實(shí)現(xiàn)：

 private static List<List<Integer>> execute3(int[] array, int m) {
        List<List<Integer>> rst = new ArrayList<>();
        List<Integer> subList = new ArrayList<>();
        int first = 0;
        int last = array.length -1;
        int sum = 0;
        while(first < last ) {
            sum = array[first] + array[last];
            if (sum == m) {
                subList.clear();
                subList.add(array[first]);
                subList.add(last);
                rst.add(new ArrayList<>(subList));
                first++;
                last--;
            } else if (sum < m) {
                first++;
            } else {
                last--;
            }
        }
        return rst;
    }