又黄又粗又爽免费观看,色吧电影网,军人武警gay男同gvus69,精品久久久久久久久中文字幕

position>home>Archive

漫畫算法題:兩數之和與三數之和

[導讀]前一段時間,漫畫分別講解了兩道leecode上的算法數經典算法題,今天就把這兩道題整合起來,題兩并修改了其中的和數細節問題,感謝大家的漫畫指正。

前一段時間,算法數小灰分別講解了兩道leecode上的題兩經典算法題:

漫畫算法題:兩數之和與三數之和


漫畫:如何在數組中找到和為 “特定值” 的兩個數?

漫畫:如何在數組中找到和為 “特定值” 的三個數?


今天,小灰把這兩道題整合起來,和數并修改了其中的漫畫細節問題,感謝大家的算法數指正。



—————  第二天  —————



什么意思呢?我們來舉個例子,題兩給定下面這樣一個整型數組(假定數組不存在重復元素):



我們隨意選擇一個特定值,和數比如13,漫畫要求找出兩數之和等于13的算法數全部組合。


由于12+1 = 13,題兩6+7 = 13,所以最終的輸出結果(輸出的是下標)如下:


【1, 6】

【2, 7】


小灰想表達的思路,是直接遍歷整個數組,每遍歷到一個元素,就和其他元素相加,看看和是不是等于那個特定值。


第1輪,用元素5和其他元素相加:



沒有找到符合要求的兩個元素。


第2輪,用元素12和其他元素相加:



發現12和1相加的結果是13,符合要求。


按照這個思路,一直遍歷完整個數組。




————————————












讓我們來具體演示一下:


第1輪,訪問元素5,計算出13-5=8。在哈希表中查找8,發現查不到:



第2輪,訪問元素12,計算出13-12=1。在哈希表中查找1,查到了元素1的下標是6,所以元素12(下標是1)和元素1(下標是6)是一對結果:



第3輪,訪問元素6,計算出13-6=7。在哈希表中查找7,查到了元素7的下標是7,所以元素6(下標是2)和元素7(下標是7)是一對結果:



按照這個思路,一直遍歷完整個數組即可。


public class FindSumNumbers { 

    public static List> twoSum(int[] nums, int target) {
        Map map = new HashMap<>();
        List> resultList = new ArrayList<>();
        for (int i = 1; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int other = target - nums[i];
            if (map.containsKey(other) && map.get(other) != i) {
                resultList.add(Arrays.asList(i,map.get(other)));
                //為防止找到重復的元素對,匹配后從哈希表刪除對應元素
                map.remove(nums[i]);
            }
        }
        return resultList;
    }

    public static void main(String[] args) {
        int[] nums = { 5,12,6,3,9,2,1,7};
        List> resultList = twoSum(nums, 13);
        for(List list : resultList){
            System.out.println(Arrays.toString(list.toArray()));
        }
    }

}


    public static List> twoSumV2(int[] nums, int target) { 
        Map map = new HashMap<>();
        List> resultList = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int other = target - nums[i];
            if (map.containsKey(other)) {
                resultList.add(Arrays.asList(map.get(other),i));
            }
            map.put(nums[i], i);
        }
        return resultList;
    }



舉個例子,給定下面這樣一個整型數組(假定數組不存在重復元素):



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


由于5+6+2=13, 5+1+7=13,3+9+1=13,所以最終的輸出結果如下(直接輸出元素值即可):


【5, 6,2】

【5, 1,7】

【3, 9,1】



小灰的思路,是把原本的“三數之和問題”,轉化成求n次“兩數之和問題”。



我們以上面這個數組為例,選擇特定值13,演示一下小灰的具體思路:


第1輪,訪問數組的第1個元素5,把問題轉化成從后面元素中找出和為8(13-5)的兩個數:


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


第2輪,訪問數組的第2個元素12,把問題轉化成從后面元素中找出和為1(13-12)的兩個數:



第3輪,訪問數組的第3個元素6,把問題轉化成從后面元素中找出和為7(13-6)的兩個數:



以此類推,一直遍歷完整個數組,相當于求解了n次兩數之和問題。


    public static List> threeSum(int[] nums, int target) { 
        List> resultList = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            Map map = new HashMap<>();
            int d1 = target - nums[i];
            //尋找兩數之和等于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;
    }


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


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



我們仍然以之前的數組為例,對數組進行升序排列:




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


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


如何找出和為12的兩個數呢?我們設置兩個指針,指針j指向剩余元素中最左側的元素2,指針k指向最右側的元素12:


計算兩指針對應元素之和,2+12 = 14 > 12,結果偏大了。


由于數組是按照升序排列,k左側的元素一定小于k,因此我們把指針k左移一位:


計算兩指針對應元素之和,2+9 = 11< 12,這次結果又偏小了。


j右側的元素一定大于j,因此我們把指針j右移一位:


計算兩指針對應元素之和,3+9 = 12,正好符合要求!


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


但這并不是結束,我們要繼續尋找其他組合,讓指針k繼續左移:


 計算兩指針對應元素之和,3+7 = 10< 12,結果偏小了。


于是我們讓指針j右移:


計算兩指針對應元素之和,5+7 = 12,又找到符合要求的一組:


1,5,7


我們繼續尋找,讓指針k左移:


 計算兩指針對應元素之和,5+6 = 11< 12,結果偏小了。


于是我們讓指針j右移:


此時雙指針重合在了一起,如果再繼續移動,就有可能和之前找到的組合重復,因此我們直接結束本輪循環。


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


我們仍然設置兩個指針,指針j指向剩余元素中最左側的元素3,指針k指向最右側的元素12:


 計算兩指針對應元素之和,3+12 = 15 > 11,結果偏大了。


我們讓指針k左移:


 計算兩指針對應元素之和,3+9 = 12 > 11,結果仍然偏大。


我們讓指針k繼續左移:


 計算兩指針對應元素之和,3+7 = 10 < 11,結果偏小了。


我們讓指針j右移:


 計算兩指針對應元素之和,5+7 = 12 > 11,結果又偏大了。


我們讓指針k左移:


 計算兩指針對應元素之和,5+6 = 11,于是我們又找到符合要求的一組:


2,5,6


我們繼續尋找,讓指針k左移:


此時雙指針又一次重合在一起,我們結束本輪循環。


按照這個思路,我們一直遍歷完整個數組。


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


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


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


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


—————END—————



喜歡本文的朋友,歡迎關注公眾號 程序員小灰,收看更多精彩內容

點個[在看],是對小灰最大的支持!


免責聲明:本文內容由21ic獲得授權后發布,版權歸原作者所有,本平臺僅提供信息存儲服務。文章僅代表作者個人觀點,不代表本平臺立場,如有問題,請聯系我們,謝謝!

Popular articles