??引言??
大家好，我是執梗，今天為大家講解的是力扣經典的幾數之和系列，有句話說得好——有人夜里看海，有人力扣第一題都做不出來，大家應該都知道力扣的第一題是兩數之和，但其實兩數之和只是一個起始，在進階的還有三數之和，四數之和以及四數相加等等，今天我為大家將這一系列從易到難為大家整合好，其中詳細決議各種方法，幫助大家總結其中規律，以達到舉一反三的效果，建議大家收藏，方便訓練，

同時在這為兄弟們推薦我的鏈表專題，幫助大家手撕鏈表，系統訓練——鏈表專題

📒博客首頁：執梗的博客

🎉歡迎關注🔎點贊👍收藏??留言📝

?? ：熱愛Java與演算法學習，期待一起交流！

🙏作者水平很有限，如果發現錯誤，求告知，多謝！

🌺有問題可私信交流！！！

??導航助手??

🍋1.刷題與觀看須知

🍋2.逐步訓練，鏖戰力扣

🐱 1.兩數之和

🐭2.兩數之和||——輸入有序陣列

🐸3.兩數之和IV——輸入BST

🐶4.三數之和

🐯5.四數之和

🐷6.四數相加ll

🍋3.刷題總結

🍋1.刷題與觀看須知

幾數幾何系列是力扣最經典的系列套題之一，它的每道題解法都非常多樣化，用到了各種各樣的演算法知識，比如暴力列舉、哈希、排序+雙指標等等，但是，雖然很多人能做出來，但是卻只會一種樸素的解法，這就感到沾沾自喜了，這類題一定要會做到舉一反三觸類旁通，希望大家每道題都能多樣化解題，同時總結出這類題的規律，

🍋2.逐步訓練，鏖戰力扣

🐱 1.兩數之和

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

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

你可以按任意順序回傳答案，

題目鏈接：兩數之和

作為力扣的第一題，它是很多人成神的起點，這道題也有著自己的美麗，

題目分析：第一個想到肯定是暴力遍歷，其次是利用哈希表，哈希表的解法也有不同型別，這里我們用的是Hashmap，用key存放值，value存放下標，在遍歷陣列nums[i]的同時尋找哈希表內是否有符合的數，有則回傳兩個下標，無則將nums[i]放入哈希表中，

1.暴力遍歷

時間復雜度O(N^2)：使用兩層for回圈，最壞的情況每兩個數都要被遍歷幾次

空間復雜度O(1)：常數級的陣列空間

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
 }

2.利用HashMap

時間復雜度O(N) ：只遍歷了一次陣列

空間復雜度O(N)：主要為哈希表的開銷

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n=nums.length;
        //key存放值，value存放下標
        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<n;i++){
            //找到了
            if(map.containsKey(target-nums[i])){
                //回傳下標
                return new int[]{map.get(target-nums[i]),i};
            }
            //沒找到放入map中
            map.put(nums[i],i);
        }
        //遍歷結束仍然未找到
        return new int[0];
    }
}

🐭2.兩數之和||——輸入有序陣列

給定一個已按照 非遞減順序排列 的整數陣列 numbers ，請你從陣列中找出兩個數滿足相加之和等于目標數 target ，

函式應該以長度為 2 的整數陣列的形式回傳這兩個數的下標值，numbers 的下標 從 1 開始計數 ，所以答案陣列應當滿足 1 <= answer[0] < answer[1] <= numbers.length ，

你可以假設每個輸入 只對應唯一的答案 ，而且你 不可以 重復使用相同的元素，

題目鏈接：兩數之和||——輸入有序陣列

思路分析：這道題可以同上一道一樣使用暴力求解以及哈希表，但那是針對與無序陣列的，因為是一個排好序的陣列，我們自然要想到雙指標，從兩頭開始遍歷，當兩指標相加的元素大于target，右指標向左移動，當小于target時，讓左指標右移，

時間復雜度：O(n)，其中n是陣列的長度，兩個指標移動最多一共n次

空間復雜度：O(1)

class Solution {
    public int[] twoSum(int[] numbers, int target) {
         int n=numbers.length;
         int left=0;
         int right=n-1;
         while(left<right){
             int count=numbers[left]+numbers[right];
             //找到了，但是下標要加1，因為題目要求
             if(count==target){
                 return new int[]{left+1,right+1};
             //加起來太大了，right--，這樣count會變小
             }else if(count>target){
                 right--;
             //加起來太小了,left++,這樣count會變大
             }else{
                 left++;
             }
         }
         return new int[0];
    }
}

🐸3.兩數之和IV——輸入BST

給定一個二叉搜索樹 root 和一個目標結果 k，如果樹中存在兩個元素且它們的和等于給定的目標結果，則回傳 true，

題目鏈接：兩數之和 IV - 輸入 BST

題目分析:這道題與前面的兩數之和類似，只不過是元素存放的形式變成了樹，我們同樣可以利用Hashset來遍歷樹，

方法：Hashset加遍歷樹，判斷當前root時，set中是否存在k-root.val，如果存在直接回傳true，不存在的話將此時的root.val存放進set中，同時去左子樹和右子樹中繼續查找，

時間復雜度O(n)，n為節點的數量，最壞的情況下，整棵樹被遍歷一次

空間復雜度O(n)，最壞的情況下，set存盤n個節點的值，

class Solution {
    public boolean findTarget(TreeNode root, int k) {
        Set<Integer> set=new HashSet<>();
        return find(root,k,set);
    }
    public boolean find(TreeNode root,int k,Set set){
        //如果root為空直接回傳false
        if(root==null) return false;
        if(set.contains(k-root.val)){
            return true;
        }
        //這個沒找到就加入到set集合中
        set.add(root.val);
        //同時去左子樹和右子樹查找
        return find(root.left,k,set)||find(root.right,k,set);
    }
}

🐶4.三數之和

給你一個包含 n 個整數的陣列 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？請你找出所有和為 0 且不重復的三元組，

注意：答案中不可以包含重復的三元組，

題目鏈接：三數之和

題目分析：這道題和兩數之和看上去類似，但做法卻不相同，難度也不在一個檔次，樸素暴力的做法再最后幾個例子會超時

方法1：樸素暴力（超時）

時間復雜度O(N^3)

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int n=nums.length;
        List<List<Integer>> list=new ArrayList<>();
        for(int i=0;i<n-2;i++){
            for(int j=n-1;j>i+1;j--){
                int x=i+1;
                while(x<j){
                int count=nums[i]+nums[x]+nums[j];
                if(count==0){
                    List<Integer> arr=new ArrayList<>();
                    arr.add(nums[i]);
                    arr.add(nums[x]);
                    arr.add(nums[j]);
                    if(!list.contains(arr)){
                        list.add(arr);
                    }
                    x++;
                }else if(count>0){
                    break;
                }else{
                    x++;
                }
            }
            }
        }
        return list;
    }
}

方法2：排序加雙指標

思路：在為了方便去重和減少遍歷次數，我們應該保證三指標滿足i<j<k的關系，i我們通過for回圈固定，j和k從兩頭向內移動，

時間復雜度O(n^2)：陣列排序O(nlogn),遍歷陣列O(n),雙指標遍歷O(n)，總體O(n^2)

空間復雜度O(1)

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        //對陣列排序
        Arrays.sort(nums);
        int n=nums.length;
        List<List<Integer>> list=new ArrayList<>();
        for(int i=0;i<n-2;i++){
            //定一個i,移動兩指標j,k,注意j是從末尾開始移動
           int j=i+1;
           int k=n-1;
           while(j<k){
               int count=nums[i]+nums[j]+nums[k];
               //找到符合的
               if(count==0){
                   List<Integer> arr=new ArrayList<>();
                   arr.add(nums[i]);
                   arr.add(nums[j]);
                   arr.add(nums[k]);
                   //為了去重
                   if(!list.contains(arr)){
                       list.add(arr);
                   }
                   j++;
                   k--;
                //加起來太大，讓k--從而和變小
               }else if(count>0){
                   k--;
                //加起來太小,讓j++從而和變大
               }else{
                   j++;
                   }
              }
        }
        return list;
    }
}

對上述代碼可進行優化：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);//排序，nums變成遞增陣列
        List<List<Integer>> res = new ArrayList<>();
        //k < nums.length - 2是為了保證后面還能存在兩個數字
        for(int k = 0; k < nums.length - 2; k++){
            if(nums[k] > 0) break;//若nums[k]大于0，則后面的數字也是大于零（排序后是遞增的）
            if(k > 0 && nums[k] == nums[k - 1]) continue;//nums[k]值重復了，去重
            int i = k + 1, j = nums.length - 1;//定義左右指標
            while(i < j){
                int sum = nums[k] + nums[i] + nums[j];
                if(sum < 0){
                    while(i < j && nums[i] == nums[++i]);//左指標前進并去重
                } else if (sum > 0) {
                    while(i < j && nums[j] == nums[--j]);//右指標后退并去重
                } else {
                    res.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[i], nums[j]);
                    while(i < j && nums[i] == nums[++i]);//左指標前進并去重
                    while(i < j && nums[j] == nums[--j]);//右指標后退并去重
                }
            }
        }
        return res;
    }
}

🐯5.四數之和

給你一個由 n 個整陣列成的陣列 nums ，和一個目標值 target ，請你找出并回傳滿足下述全部條件且不重復的四元組 [nums[a], nums[b], nums[c], nums[d]] （若兩個四元組元素一一對應，則認為兩個四元組重復）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意順序 回傳答案 ，

題目鏈接：四數之和

題目思路：這道題是在三數之和的基礎之上個進階，也可以說是兩數之和的進階，只不過變成了四個數，我們不可能用4個for回圈遍歷，而且還得去重，肯定是會超時的，這時我們同樣可以利用三數之和的性質，先將陣列排序，利用四個指標i,p1,p2,j，同時保證i<p1<p2<j，每次固定i和j，判斷四個下標相加的和 ，如果比target大，讓p2--，如果比target小，讓p1++，如果相等就放入到答案集合中，

方法: 排序加雙指標

時間復雜度：O(n^3)

空間復雜度: O(logn)

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> list=new ArrayList<>();
        Arrays.sort(nums);
        int n=nums.length;
        //i得保證后面還得有三個位，所以<n-3
        for(int i=0;i<n-3;i++){
            //得保證和i之間還有兩個位，所以>i+2
            for(int j=n-1;j>i+2;j--){
                int x=nums[i]+nums[j];
                //兩指標開始的位置
                int p1=i+1;
                int p2=j-1;
                while(p1<p2){
                    int count=x+nums[p1]+nums[p2];
                    if(count==target){
                        List<Integer> arr=new ArrayList<>();
                        arr.add(nums[i]);
                        arr.add(nums[j]);
                        arr.add(nums[p1]);
                        arr.add(nums[p2]);
                        //去重
                        if(!list.contains(arr)){
                          list.add(arr);  
                        }                       
                        p1++;
                        p2--;
                    }else if(count>target){
                        p2--;
                    }else{
                        p1++;
                    }
                }
            }
        }
        return list;
    }
}

🐷6.四數相加ll

給你四個整數陣列 nums1、nums2、nums3 和 nums4 ，陣列長度都是 n ，請你計算有多少個元組 (i, j, k, l) 能滿足：

0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

題目鏈接：四數相加ll

題目思路：這道題其實比上一道題四數之和要簡單一些，不過它卻也有自己比較難處理的地方，我們不可能用四個for回圈遍歷，因為即使能遍歷不超時，去重的步驟也是很麻煩的，其實也相當于又是兩數之和的進階，我們可以將陣列兩兩分組，A組和B組遍歷相加，將結果作為key，value當做該結果出現的次數，然后再遍歷C組和D組相加的和為count，去判斷map中是否有和count相加為0的key，如果有則加上該key對應的value，這樣相當于進行了兩次O(n^2)的遍歷，總體來說還是O(n^2)的世界復雜度

方法：分組+哈希表

時間復雜度O(n^2)：兩個兩層for回圈，總體來時間復雜度還是O(n^2)

空間復雜度O(n^2)：哈希映射需要的空間，最壞的情況下存入的值個數位n^2，也就需要O(n^2)的空間

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer,Integer> map=new HashMap<>();
        int n=nums1.length;
        //用來統計答案
        int anser=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                int count=nums1[i]+nums2[j];
                //已存在
                if(map.containsKey(count)){
                    //讓出現的次數加1，也就是value
                   map.put(count,map.get(count)+1); 
                }else{
                    //未存在，放入map中,value為1
                    map.put(count,1);
                }
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                int count2=nums3[i]+nums4[j];
                //找到匹配的
                if(map.containsKey(-count2)){
                    //加上value，也就是出現的次數
                    anser+=map.get(-count2);
                }
            }
        }
        return anser;
    }
}

🍋3.刷題總結

幾數之和的題目都非常的干貨，深度地考察了我們演算法基礎能力的實踐應用，特別是對哈希能力的訓練，因為哈希是經典的以空間換時間，如果我們不用哈希就會超時，而且去重也非常麻煩，其次是雙指標的運用，因為幾數之和的題目資料大部分都在陣列中，在陣列中找元素大部分都離不開雙指標演算法，大家做完這型別的題目一定要多總結其中的規律，從二數到三數到四數，它的變化是怎樣，做法又如何變化，這樣才能高效刷題，早日成神！ 后續我也會出哈希專題系列以及雙指標專題系列，

如果有用，希望兄弟們三連多多支持一下！！！感謝

文末驚喜：

Java學習路線總結，搬磚工逆襲Java架構師