怎么在數(shù)組中找到和為特定值的三個(gè)數(shù)

本篇內(nèi)容主要講解“怎么在數(shù)組中找到和為特定值的三個(gè)數(shù)”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“怎么在數(shù)組中找到和為特定值的三個(gè)數(shù)”吧!

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

我們隨意選擇一個(gè)特定值，比如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ù)之和問(wèn)題”，轉(zhuǎn)化成求n次“兩數(shù)之和問(wèn)題”。

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

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

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

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

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

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

public static List<List<Integer>> threeSum(int[] nums, int target) {        List<List<Integer>> resultList = new ArrayList<>();        for (int i = 0; i < nums.length; i++) {            Map<Integer, Integer> map = new HashMap<>();            int d1 = target - nums[i];            //尋找兩數(shù)之和等于d1的組合            for (int j = i+1; j < nums.length; j++) {                int d2 = d1 - nums[j];                if (map.containsKey(d2)) {                    resultList.add(Arrays.asList(nums[i], d2, nums[j]));                }                map.put(nums[j], j);            }        }        return resultList;    }

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

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

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

這樣說(shuō)起來(lái)有些抽象，我們來(lái)具體演示一下：

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

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

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

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

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

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

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

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

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

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

于是我們讓指針j右移：

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

1，5，7

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

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

于是我們讓指針j右移：

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

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

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

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

我們讓指針k左移：

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

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

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

我們讓指針j右移：

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

我們讓指針k左移：

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

2，5，6

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

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

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

像這樣利用兩個(gè)指針指向數(shù)組兩端，不斷向中間靠攏調(diào)整來(lái)尋找匹配組合的方法，就是雙指針?lè)ǎ脖环Q(chēng)為“夾逼法”。

public static List<List<Integer>> threeSumv2(int[] nums, int target) {     Arrays.sort(nums);     List<List<Integer>> resultList = new ArrayList<List<Integer>>();     //大循環(huán)     for (int i = 0; i < nums.length; i++) {         int d = target - nums[i];         // j和k雙指針循環(huán)定位，j在左端，k在右端         for (int j=i+1,k=nums.length-1; j<nums.length; j++) {             // k指針向左移動(dòng)             while (j<k && (nums[j]+nums[k])>d) {                 k--;             }             //雙指針重合，跳出本次循環(huán)             if (j == k) {                 break;             }             if (nums[j] + nums[k] == d) {                 List<Integer> list = Arrays.asList(nums[i], nums[j], nums[k]);                 resultList.add(list);             }         }     }     return resultList; }

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

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

到此，相信大家對(duì)“怎么在數(shù)組中找到和為特定值的三個(gè)數(shù)”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢(xún)，關(guān)注我們，繼續(xù)學(xué)習(xí)！