摘要：一個(gè)面試題一個(gè)數(shù)組找出這樣的三個(gè)元素它們的和與目標(biāo)值最接近如原始數(shù)組目標(biāo)值這樣的三個(gè)元素算法沒(méi)有想到什么好的算法可以快捷的找到這樣的三個(gè)元素只想到了窮舉法即找出所有的任意三元素?cái)?shù)組長(zhǎng)度放到優(yōu)先隊(duì)列中按三個(gè)元素的和與目標(biāo)值的差值絕對(duì)值進(jìn)行排序

一個(gè)面試題

一個(gè)數(shù)組 找出這樣的三個(gè)元素 它們的和與目標(biāo)值最接近
如
原始數(shù)組： [15, 27, 31, 33, 39, 44, 50, 57, 86, 91]
目標(biāo)值: 98
這樣的三個(gè)元素：15,33,50 （15+33+50=98）

沒(méi)有想到什么好的算法 可以快捷的找到這樣的三個(gè)元素
只想到了窮舉法 即

找出所有的任意三元素 C(數(shù)組長(zhǎng)度,3)

放到優(yōu)先隊(duì)列中 按三個(gè)元素的和與目標(biāo)值的差值（絕對(duì)值）進(jìn)行排序

第一個(gè)即是與目標(biāo)值最接近的三元素

// 得到所有的三元素組合列表 如["1,2,3", "4,5,6" , ...]
List allUniqueThreeElements = getAllUniqueThreeElements(a,3);

// 三元素列表轉(zhuǎn)成對(duì)象  對(duì)象中提供了這樣的方法：getDiff (計(jì)算三元素的和與目標(biāo)值的差值（絕對(duì)值）)
List threeElementsList = new ArrayList<>();
for (String s : allUniqueThreeElements) {
    elementsList.add(new ThreeElements(s));
}
// 構(gòu)造優(yōu)先隊(duì)列 按三元素的和與目標(biāo)值的差值（絕對(duì)值）進(jìn)行排序 優(yōu)先隊(duì)列默認(rèn)大小為三元素組合列表大小
PriorityQueue pq = new PriorityQueue<>(threeElementsList.size(),comparingInt(o -> o.getDiff(target))); 

// 將三元素組合對(duì)象 逐一放到優(yōu)先隊(duì)列中
for (ThreeElements e : threeElementsList) {
    pq.offer(e);
}

ThreeElements poll = pq.poll(); // 優(yōu)先隊(duì)列中 第一個(gè)即為要找的三元素

即C(n,m)

如 數(shù)組 [1,2,3,4,5] 找出所有的三元素組合

相當(dāng)于將同一數(shù)組復(fù)制三份 每一份中 取一個(gè)元素 不重復(fù)即可

這樣的取法

    /**
     * 
     * @param indexArray 索引數(shù)組
     * @param maxIndexValue 最大索引值
     * @param startIndex indexArray中從此位開(kāi)始遞增
     * @return
     */
    private boolean next(final int[] indexArray, final int maxIndexValue, int startIndex){
//        System.out.println("indexArray: "+Arrays.toString(indexArray));
//        System.out.println("startIndex: "+startIndex);
        indexArray[startIndex]++; // 從此位開(kāi)始遞增
        if(indexArray[startIndex] > maxIndexValue){ // 超過(guò)最大索引值 從前一位開(kāi)始遞增
            return next(indexArray,maxIndexValue,startIndex-1);
        }else{
            // 同時(shí)逐個(gè)累加之后的元素 后一位的值 = 前一位+1
            for (int i = startIndex+1; i < indexArray.length; i++) {
                indexArray[i] = indexArray[i-1]+1;
                if(indexArray[i] > maxIndexValue){
                    if(startIndex -1 < 0){ // 如果是從第一位開(kāi)始遞增的 即不存在更前一位了 則退出遞歸
                        return false;
                    }
                    return next(indexArray,maxIndexValue,startIndex-1);
                }
            }
            return true;
        }
    }

測(cè)試代碼

    @Test
    public void test_next(){
        // 測(cè)試從一個(gè)數(shù)組中得到所有的三元素組合
        int[] a = {1, 2, 3, 4, 5}; // 數(shù)組
        int maxIndexValue = a.length-1; // 最大索引值
        int[] indexArray = {0,1,2}; // 初始化索引數(shù)組
        int startIndex = indexArray.length-1; // 從末位開(kāi)始遞增

        // 驗(yàn)證  [0,1,2] --> [0,1,3]
        boolean next = next(indexArray, maxIndexValue, startIndex);
        assertTrue(next);
        assertArrayEquals(new int[]{0,1,3}, indexArray);

        // 驗(yàn)證 [0,1,4] --> [0,2,3]
        indexArray = new int[]{0, 1, 4};
        next = next(indexArray, maxIndexValue, startIndex);
        assertTrue(next);
        assertArrayEquals(new int[]{0,2,3}, indexArray);

        // 驗(yàn)證 [0,3,4] --> [1,2,3]
        indexArray = new int[]{0, 3, 4};
        next = next(indexArray, maxIndexValue, startIndex);
        assertTrue(next);
        assertArrayEquals(new int[]{1,2,3}, indexArray);

        // 驗(yàn)證 [2,3,4] --> X
        indexArray = new int[]{2, 3, 4};
        next = next(indexArray, maxIndexValue, startIndex);
        assertFalse(next);
    }

當(dāng)驗(yàn)證其他一些極端情況的時(shí)候 如從一個(gè)數(shù)組中得到所有一個(gè)元素的組合 即C(n,1) 測(cè)試沒(méi)有通過(guò)

    @Test
    public void test_next_and_only_choose_one_element(){
        // 測(cè)試一些更極端的情況 如 一個(gè)數(shù)組中選出所有1個(gè)元素的組合(C(n,1))
        final int[] a = {1, 2, 3, 4, 5};
        int maxIndexValue = a.length-1;
        int[] indexArray = {0};
        int startIndex = indexArray.length-1;


        //驗(yàn)證 [0] -> [1]
        boolean next = next(indexArray, maxIndexValue, startIndex);
        assertTrue(next);
        assertArrayEquals(new int[]{1},indexArray);
        System.out.println();
        // 驗(yàn)證 [4] -> X
        indexArray = new int[]{4};
        next = next(indexArray, maxIndexValue, startIndex);
        assertFalse(next);
    }

修復(fù)代碼 將判斷最后沒(méi)有下一組的代碼給提取出來(lái)了

    private boolean next(final int[] indexArray, final int maxIndexValue, int startIndex){
        if(startIndex < 0){ // 如果不存在更前一位了 則退出遞歸
            return false;
        }
        indexArray[startIndex]++; // 從此位開(kāi)始遞增
        if(indexArray[startIndex] > maxIndexValue){ // 超過(guò)最大索引值 從前一位開(kāi)始遞增
            return next(indexArray,maxIndexValue,startIndex-1);
        }else{
            // 同時(shí)逐個(gè)累加之后的元素 后一位的值 = 前一位+1
            for (int i = startIndex+1; i < indexArray.length; i++) {
                indexArray[i] = indexArray[i-1]+1;
                if(indexArray[i] > maxIndexValue){
                    return next(indexArray,maxIndexValue,startIndex-1);
                }
            }
            return true;
        }
    }

http://wiki.jikexueyuan.com/p...