日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
如何在數(shù)組中找到和為“特定值”的三個數(shù)？

前一段時間，我們介紹了LeetCode上面的一個經(jīng)典算法題【兩數(shù)之和問題】。

創(chuàng)新互聯(lián)建站10多年成都企業(yè)網(wǎng)站建設(shè)服務(wù);為您提供網(wǎng)站建設(shè),網(wǎng)站制作,網(wǎng)頁設(shè)計及高端網(wǎng)站定制服務(wù),成都企業(yè)網(wǎng)站建設(shè)及推廣,對塑料袋等多個領(lǐng)域擁有豐富的網(wǎng)站制作經(jīng)驗的網(wǎng)站建設(shè)公司。

這一次，我們把問題做一下擴展，嘗試在數(shù)組中找到和為“特定值”的三個數(shù)。

題目的具體要求是什么呢?給定下面這樣一個整型數(shù)組：

我們隨意選擇一個特定值，比如13，要求找出三數(shù)之和等于13的全部組合。

由于5+6+2=13， 5+1+7=13，3+9+1=13，所以最終的輸出結(jié)果如下：

【5， 6，2】

【5， 1，7】

【3， 9，1】

小灰的思路，是把原本的“三數(shù)之和問題”，轉(zhuǎn)化成求n次“兩數(shù)之和問題”。

我們以上面這個數(shù)組為例，選擇特定值13，演示一下小灰的具體思路：

第1輪，訪問數(shù)組的第1個元素5，把問題轉(zhuǎn)化成從后面元素中找出和為8(13-5)的兩個數(shù)：

如何找出和為8的兩個數(shù)呢?按照上一次所講的，我們可以使用哈希表高效求解：

第2輪，訪問數(shù)組的第2個元素12，把問題轉(zhuǎn)化成從后面元素中找出和為1(13-12)的兩個數(shù)：

第3輪，訪問數(shù)組的第3個元素6，把問題轉(zhuǎn)化成從后面元素中找出和為7(13-6)的兩個數(shù)：

以此類推，一直遍歷完整個數(shù)組，相當(dāng)于求解了n次兩數(shù)之和問題。

 
 
 
 
    
  
  
  
  
  1. public static List> threeSum(int[] nums, int target) {
    2. 
  
  
  
  
  2.        List> resultList = new ArrayList<>();
    3. 
  
  
  
  
  3.        for (int i = 0; i < nums.length; i++) {
    4. 
  
  
  
  
  4.            Map map = new HashMap<>();
    5. 
  
  
  
  
  5.            int d1 = target - nums[i];
    6. 
  
  
  
  
  6.            //尋找兩數(shù)之和等于d1的組合
    7. 
  
  
  
  
  7.            for (int j = i+1; j < nums.length; j++) {
    8. 
  
  
  
  
  8.                int d2 = d1 - nums[j];
    9. 
  
  
  
  
  9.                if (map.containsKey(d2)) {
    10. 
  
  
  
  
  10.                    resultList.add(Arrays.asList(nums[i], d2, nums[j]));
    11. 
  
  
  
  
  11.                }
    12. 
  
  
  
  
  12.                map.put(nums[j], j);
    13. 
  
  
  
  
  13.            }
    14. 
  
  
  
  
  14.        }
    15. 
  
  
  
  
  15.        return resultList;
    16. 
  
  
  
  
  16.    }
    17.

在上面的代碼中，每一輪解決“兩數(shù)之和問題”的時間復(fù)雜度是O(n)，一共迭代n輪，所以該解法總的時間復(fù)雜度是O(n2)。

至于空間復(fù)雜度，同一個哈希表被反復(fù)構(gòu)建，哈希表中最多有n-1個鍵值對，所以該解法的空間復(fù)雜度是O(n)。

我們?nèi)匀灰灾暗臄?shù)組為例，對數(shù)組進行升序排列：

這樣說起來有些抽象，我們來具體演示一下：

第1輪，訪問數(shù)組的第1個元素1，把問題轉(zhuǎn)化成從后面元素中找出和為12(13-1)的兩個數(shù)。

如何找出和為12的兩個數(shù)呢?我們設(shè)置兩個指針，指針j指向剩余元素中最左側(cè)的元素2，指針k指向最右側(cè)的元素12：

計算兩指針對應(yīng)元素之和，2+12 = 14 > 12，結(jié)果偏大了。

由于數(shù)組是按照升序排列，k左側(cè)的元素一定小于k，因此我們把指針k左移一位：

計算兩指針對應(yīng)元素之和，2+9 = 11< 12，這次結(jié)果又偏小了。

j右側(cè)的元素一定大于j，因此我們把指針j右移一位：

計算兩指針對應(yīng)元素之和，3+9 = 12，正好符合要求!

因此我們成功找到了一組匹配的組合：1，3，9

但這并不是結(jié)束，我們要繼續(xù)尋找其他組合，讓指針k繼續(xù)左移：

計算兩指針對應(yīng)元素之和，3+7 = 10< 12，結(jié)果偏小了。

于是我們讓指針j右移：

計算兩指針對應(yīng)元素之和，5+7 = 12，又找到符合要求的一組：

1，5，7

我們繼續(xù)尋找，讓指針k左移：

計算兩指針對應(yīng)元素之和，5+6 = 11< 12，結(jié)果偏小了。

于是我們讓指針j右移：

此時雙指針重合在了一起，如果再繼續(xù)移動，就有可能和之前找到的組合重復(fù)，因此我們直接結(jié)束本輪循環(huán)。

第2輪，訪問數(shù)組的第2個元素2，把問題轉(zhuǎn)化成從后面元素中找出和為11(13-2)的兩個數(shù)。

我們?nèi)匀辉O(shè)置兩個指針，指針j指向剩余元素中最左側(cè)的元素3，指針k指向最右側(cè)的元素12：

計算兩指針對應(yīng)元素之和，3+12 = 15 > 11，結(jié)果偏大了。

我們讓指針k左移：

計算兩指針對應(yīng)元素之和，3+9 = 12 > 11，結(jié)果仍然偏大。

我們讓指針k繼續(xù)左移：

計算兩指針對應(yīng)元素之和，3+7 = 10 < 11，結(jié)果偏小了。

我們讓指針j右移：

計算兩指針對應(yīng)元素之和，5+7 = 12 > 11，結(jié)果又偏大了。

我們讓指針k左移：

計算兩指針對應(yīng)元素之和，5+6 = 11，于是我們又找到符合要求的一組：

2，5，6

我們繼續(xù)尋找，讓指針k左移：

此時雙指針又一次重合在一起，我們結(jié)束本輪循環(huán)。

按照這個思路，我們一直遍歷完整個數(shù)組。

像這樣利用兩個指針指向數(shù)組兩端，不斷向中間靠攏調(diào)整來尋找匹配組合的方法，就是雙指針法，也被稱為“夾逼法”。

 
 
 
 
    
  
  
  
  
  1. public static List> threeSumv2(int[] nums, int target) {
    2. 
  
  
  
  
  2.     Arrays.sort(nums);
    3. 
  
  
  
  
  3.     List> resultList = new ArrayList>();
    4. 
  
  
  
  
  4.     //大循環(huán)
    5. 
  
  
  
  
  5.     for (int i = 0; i < nums.length; i++) {
    6. 
  
  
  
  
  6.         int d = target - nums[i];
    7. 
  
  
  
  
  7.         // j和k雙指針循環(huán)定位，j在左端，k在右端
    8. 
  
  
  
  
  8.         for (int j=i+1,k=nums.length-1; j
  
  
  
  
  9.             // k指針向左移動
    10. 
  
  
  
  
  10.             while (jd) {
    11. 
  
  
  
  
  11.                 k--;
    12. 
  
  
  
  
  12.             }
    13. 
  
  
  
  
  13.             //雙指針重合，跳出本次循環(huán)
    14. 
  
  
  
  
  14.             if (j == k) {
    15. 
  
  
  
  
  15.                 break;
    16. 
  
  
  
  
  16.             }
    17. 
  
  
  
  
  17.             if (nums[j] + nums[k] == d) {
    18. 
  
  
  
  
  18.                 List list = Arrays.asList(nums[i], nums[j], nums[k]);
    19. 
  
  
  
  
  19.                 resultList.add(list);
    20. 
  
  
  
  
  20.             }
    21. 
  
  
  
  
  21.         }
    22. 
  
  
  
  
  22.     }
    23. 
  
  
  
  
  23.     return resultList;
    24. 
  
  
  
  
  24. }
    25.

上面這段代碼表面上有三層循環(huán)，但每一輪指針j和k的移動次數(shù)加起來最多n-1次，因此該解法的整體時間復(fù)雜度是O(n2)。

最關(guān)鍵的是，該解法并沒有使用額外的集合(排序是直接在輸入數(shù)組上進行的)，所以空間復(fù)雜度只有O(1)!

本文轉(zhuǎn)載自微信公眾號「程序員小灰」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系程序員小灰公眾號。


本文名稱：如何在數(shù)組中找到和為“特定值”的三個數(shù)？
鏈接地址：http://www.5511xx.com/article/dhcggce.html