• 💂 個人主頁: IT學習日記
• 🤟 著作權: 本文由【IT學習日記】原創、在CSDN首發、需要轉載請聯系博主
• 💬 如果文章對你有幫助、歡迎關注、點贊、收藏(一鍵三連)和訂閱專欄哦
• 💅 想尋找共同成長的小伙伴，請點擊【技術圈子】

💨 一、前言

• 大家好，我是小誠，終于，我還是將“魔爪”伸到了演算法，在撰寫《演算法日記》之前，我也考慮過許多問題，現在網上關于leetcode演算法的案例這么多，我再重新"造輪子"有沒有必要，

• 最后和圈子中的朋友聊了聊(有能夠聊天的朋友還是不錯的)，其實這些擔心都是多余的，在撰寫的程序中，我自己不僅在演算法和文筆上有了進步，還可能會幫助到一些"有緣"看到文章的朋友，這樣即使重復"造輪子"又如何，

• 《演算法日記》系列特點：更加注重結合實際情況，將演算法和實際開發中問題或面試舉例相結合，讓學習演算法更有意義，(不信繼續往下看！)

• 如果文章對你有幫助，可以幫忙一鍵三連和專欄訂閱哦！ 同時，誠摯邀請你加入我們的【技術圈子】，

🔮 二、兩數求和

🔴 2.1、演算法題目

??給定一個整數陣列 nums 和一個整數目標值 target，請你 在該陣列中找出和為目標值 target 的那個整數，并回傳它們的陣列下標，

??你可以假設每種輸入只會對應一個答案，但是，陣列中同一個元素在答案里不能重復出現，回傳答案順序任意，

??示例：

示例一：

輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因為 nums[0] + nums[1] == 9 ，回傳 [0, 1] ，

示例二：
輸入：nums = [3,2,4], target = 6
輸出：[1,2]

示例三：
輸入：nums = [3,3], target = 6
輸出：[0,1]

🟠 2.2、分析題目

??題目的意思很清晰，輸入一個目標值，然后在陣列中找到兩個元素值之和為這個目標值，并回傳它們這兩個元素的陣列下標，需要注意的題目要求中提到：陣列中同一個元素在答案中不能重復出現，這個是什么含義呢?

??其實看上面的示例三就知道，輸入目標值為6，但是陣列中元素都為3，這時候回傳的結果必須為【0，1】或者【1，0】，而不能是【0，0】或者【1，1】即不能回傳下標都是一樣的結果，

🟡 2.3、解題方案一

??一、解題思路

??梳理完題目的含義后，相信很多人腦海里已經浮現了一個解題方案，那就是：使用for回圈 + if條件判斷來找出和目標值一致的兩個元素，下面來看看如何實作：

    /**
     * 方案一：雙重for回圈
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum2(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = 1; j < nums.length; j++) {
            	// 比較查詢找到符合目標值的兩個元素
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return null;
    }

??二、解題方案評審

??如果是在面試中，使用上面的題目解決這個問題，面試官最多給你打60分，為什么? 我們需要先看看這個演算法的時間復雜度是多少！(不知道時間復雜度和演算法指標的一定要先看我之前發的一篇文章：【演算法基礎知識講解】小白都也能看得懂)

??從演算法知識講解的文章中，我們可以知道 時間復雜度主要是跟：對運行時間有消耗的基本操作的執行次數成正比， 再繼續看上面的程式，我們會發現，對運行時間消耗的基本操作實際上就是if條件判斷的陳述句，

??隨著問題規模n的增大，它的判斷次數也會增多，使用問題規模函式來表達的話就是：f(n) = n²，既它的時間復雜度為O(n²)， 那我們有沒有更好的方式來進行優化呢? 答案是有滴，請繼續往下看！

🟢 2.4、解題方案一優化

??一、優化思路

??上面的方案我們使用的是暴力破解的方式，最差情況是兩個回圈到最后一個元素才能夠找到符合題目的答案，既然我們知道了運行時間都花費在if條件的比較邏輯上，是否能夠通過減少比較邏輯達到減少運行時間呢，沒錯，確實存在可以優化的方法，下面先來看看優化后的代碼吧，

??二、優化后的代碼

/**
     * 方案一優化：選擇排序法
     *
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum2(int[] nums, int target) {
        // length - 1的目的：每輪都會和集合其他元素比較篩選出一個最大/小值
        // 意味著最后一個元素已經和之前所有的元素比較過了，無需再回圈一次
        for (int i = 0; i < nums.length - 1; i++) {
            // j = i + 1表示：比較元素跳過與自身的比較，較少比較次數
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return null;
    }

??特點： 對比第一種方案和優化后的方案，你會發現它們的區別主要是在第二層的 for (int j = i + 1; j < nums.length; j++) 中，這個的含義主要是：每輪都將最外層之前比較過的元素篩選出去，不再進行重復比較，具體可以通過下面的案例來清楚認識到，

??比如要回圈一個陣列【1、2、11、7】找出和為9的兩個元素下標，我們會進行如下的操作：

??1、第一輪回圈外層會使用【1】和內層中【2,、11、7】做運算，但沒找有符合條件的兩個元素，繼續回圈，

??2、第二次外層回圈拿2和內層中的【11,7】做元素，得到符合條件的結果，如果沒有，則以此類推繼續進行第三輪、第四輪…的操作，

??通過這個操作，我們會發現，每次回圈都會跳過之前已經比較過的元素(因為已經確定它們是不滿足條件的)，即內層回圈都是從i+1開始比較的，這個就減少了不必要的比較，節省了運算時間，下面我們來推到下它的時間復雜度吧，

??三、推導優化后的代碼的時間復雜度

??通過上面的案例步驟我們會發現，隨著每次回圈的進行(即i++)，內層回圈的次數(即j<nums.length)會逐漸減小(因為j=i+1)，呈現如下規律：n-1次、n-2次，n-3次...等等，你是不是已經發現，內層回圈的比較次數就是一個等引數列，公差為1(注：如果對等引數列不是很熟悉的同學，可以直接百度下，幾分鐘就能掌握)

??通過等引數列的求和方式：Sn=n*a1+n(n-1)d/2，我們可以得到耗費運行時間的函式f(n) = n*a1+n(n-1)d/2，再根據大O記法的推斷，可以得出優化后的方法時間復雜度為O(n^2^)， 不知道大O記法的請看：演算法基礎

??四、這個優化方式有何意義

??上面優化后的方案后演算法推算出來的時間復雜度還是O(n²)，肯定有同學會疑問，既然最終的時間復雜度和優化之前一樣，這個方案有啥作用？誠然，這個方法如果當輸入規模即n無限擴大的時候，和沒有優化之前效率相差不大，但是在面試的時候，如果你能夠給面試官講解出來，面試官會在60分的基礎給你加10分，為什么？

??這10分是對你遇到問題肯鉆研、并且能夠找到一些提高效率的方式的一個肯定，面試官看重的不僅是你當前的一個能力，還要考量的是你的一個學習力、成長力，

🔵 2.5、解題方案二

??既然使用上面的優化方式不能解決我們的問題，我們就需要另辟蹊徑，相信開發的同學或多或少都聽說過“使用時間換空間和使用空間換時間”這兩個概念，那么在這個題目中能否采用這個方式呢？沒錯，解決這個問題采用空間換取時間的方式會更好，下面就來看看具體的實作方式吧，

    public static int[] twoSum(int[] nums, int target) {
    	// 使用HashTable存盤陣列的值和下標
        Hashtable<Integer, Integer> keyMap = new Hashtable<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
        	// 每次回圈時判斷是否在hashtable中存在與當前回圈的值相加等于target，如果有則回傳
            if (keyMap.containsKey(target - nums[i])) {
                return new int[]{keyMap.get(target - nums[i]), i};
            }
            // 沒有找到符合條件的值則將元素值和下標存盤起來
            keyMap.put(nums[i], i);
        }
        return null;
    }

??通過上面的代碼，你會發現問題規模函式f(n) = n(即只存在一層回圈，隨著n的增到，回圈次數也會增大)，通過大O記法可推斷出時間復雜度為O(n)，上面的演算法中引入了Hashtable，目的就是將陣列中的值存盤起來，減少內層回圈，這個就是空間換時間的一種方式，下面通過具體的圖片來看看時間復雜度O(n)和O(n²有多大的區別，

🟣 2.6、實際業務中的運用

??在業務中，使用多層for查找符合條件的資料是很常見的業務，比如對某些資料進行排序，我們會使用到選擇排序法、冒泡排序法等，它們都是通過for去解決排序問題，

??以控制元件換時間的方案，在開發中也非常常見，比如為了提高資料的檢索速度，我們會給適當的欄位創建對應的索引，以便快速定位到需要的資料，還有各種nosql資料庫如redis，本質上也是通過控制元件換時間的方式來提高效率，

📑 三、寫在最后

??通過上面三種不同解決方案，你會發現，尋找最優方式對大多數人來說是一個循序漸進的程序，很多人剛開始并不會立馬就想到使用空間換取時間的方案來解決這個問題，就像你剛開始學習演算法的時候，可能也覺得很難，又要編程、還可能涉及到數學知識，

??你可以有退卻之心，但更要有試一試的勇氣，演算法看上去是很難，但是，你可以先開始第一步，嘗試著了解演算法的知識，嘗試著去解決簡單的演算法問題，一步步堅持下來，你會發現，演算法也沒有這么難，數學也沒有這么難，

??請記住！一個人可以走得很快，但是一群人才能走得更遠！ 歡迎加入技術人的圈子【技術圈子】，共享資源，共同成長！