力扣每日一練之數組中篇Day2

🍕前面的話🥞

大家好！本篇文章将介紹2周搞定資料結構的題，來自力扣的1.兩數之和和88.合并兩個有序數組，本文将以這兩道題作為背景，介紹經典的數組排序以及線性查找，展示語言為java（部落客學習語言為java)。今天呢，是部落客開始刷力扣的第二天，如果有想要開始準備自己的算法面試的同學，可以跟着我的腳步一起，共同進步。大家都是并肩作戰的夥伴，一起努力奮力前行，路漫漫其修遠兮，吾将上下而求索，相信我們一定都可以拿到自己期望的offer，沖沖沖！

👩‍💻部落格首頁：京與舊鋪的部落格首頁

✨歡迎關注🖱點贊🎀收藏⭐留言✒

🔮本文由京與舊鋪原創！

😘系列專欄：java學習

💻首發時間：🎞2022年4月30日🎠

🎨你做三四月的事，八九月就會有答案，一起加油吧

🔏參考線上程式設計網站：🎧力扣

🀄如果覺得部落客的文章還不錯的話，請三連支援一下部落客哦

🎧最後的話，作者是一個新人，在很多方面還做的不好，歡迎大佬指正，一起學習哦，沖沖沖

💬推薦一款模拟面試、刷題神器👉點選進入網站

🏓導航小助手📻

文章目錄

力扣每日一練之數組中篇Day2

@[toc]

💥LeetCode1 兩數之和💝
💤題目詳情💦
💫解題思路

🥌題目講解
🎑暴力解法【線性查找】

🩳注意點
💨源代碼
🎄LeetCode 88.合并兩個有序數組
🎉題目詳情🎊
👡解題思路

直接合并後排序

🌌總結

覺得文章寫的不錯的親親，點贊評論關注走一波，愛你們哦🛴

💥LeetCode1 兩數之和💝

💤題目詳情💦

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

你可以假設每種輸入隻會對應一個答案。但是，數組中同一個元素在答案裡不能重複出現。

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

示例 1：

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

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

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

。

💫解題思路

🥌題目講解

這道題有很多種方法，因為部落客本人呢，算法還沒有學多少，是以我們在這裡隻提供第一種解法，也是更好了解的一種辦法，好的，下面我們來具體看看如何解決叭

首先，這道題給我們的是一個數組nums以及一個和target，找到兩個元素之和為target，再傳回兩個數之和就可以了，這樣的話，我們可以發現，可能最後有多個解，但是這個題目也說明了，隻要傳回一個解，就算運作成功了。但是要注意，同一個元素，不能使用兩次。

🎑暴力解法【線性查找】

一開始我們會采用最暴力的解法，也就是線性查找。首先，我們從第一個元素開始，固定第一個元素，之後我們用target減掉第一個數得到的，去查找有沒有這個值。查找方式為用指針向後一個一個查找，這就是線性查找、如果沒有找到的話，我們就固定第二個元素。之後以此類推尋找第二個元素有沒有對應的值，沒有找到的話，我們接着尋找第三個值，如果找到了，那我們就傳回對應的i，j值，也就是它們的角标。

之後我們就開始寫代碼了，第一步，先輸入數組和target，也就是定義這兩個值。第二步，我們用if語句進行一個特判，就是判斷數組是否為空，以及數組的長度是否為0，在這兩種情況下，都無法選出兩個值。之後第三步，由于我們使用的是暴力查找，是以先定義一個for循環，然後我們先固定一個元素的值，定義為x。之後第四步，我們定義一個變量為i+1，當滿足題中的條件時，即可傳回數組的角标。

接下來我們來分析一下時間複雜度和空間複雜度，因為我們沒有開辟任何新的數組空間，是以空間複雜度為O（1）

當i=0時，需要比較n-1次，數組的長度為n。當i=1時，需要比較n-2次。一直到比較1次，是以比較的次數是(n-1)+(n-2)+…+1,這個是第二個for語句要執行的次數，經過數學計算以及化簡，最終得到時間複雜度為O（n*n）

🩳注意點

1.首先設定一個前提條件就是數組不為空，用null表示，以及長度不為0

2.i是從0開始的，到最後一個結束，是以不應該減掉1

3.j是從i之後周遊的

💨源代碼

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

🎄LeetCode 88.合并兩個有序數組

🎉題目詳情🎊

給你兩個按非遞減順序排列的整數數組 nums1 和 nums2，另有兩個整數 m 和 n ，分别表示 nums1 和 nums2 中的元素數目。

請你合并 nums2 到 nums1 中，使合并後的數組同樣按非遞減順序排列。

注意：最終，合并後數組不應由函數傳回，而是存儲在數組 nums1 中。為了應對這種情況，nums1 的初始長度為 m + n，其中前 m 個元素表示應合并的元素，後 n 個元素為 0 ，應忽略。nums2 的長度為 n 。

示例 1：

輸入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
輸出：[1,2,2,3,5,6]
解釋：需要合并 [1,2,3] 和 [2,5,6] 。
合并結果是 [1,2,2,3,5,6] ，其中斜體加粗标注的為 nums1 中的元素。
示例 2：

輸入：nums1 = [1], m = 1, nums2 = [], n = 0
輸出：[1]
解釋：需要合并 [1] 和 [] 。
合并結果是 [1] 。
示例 3：

輸入：nums1 = [0], m = 0, nums2 = [1], n = 1
輸出：[1]
解釋：需要合并的數組是 [] 和 [1] 。
合并結果是 [1] 。
注意，因為 m = 0 ，是以 nums1 中沒有元素。nums1 中僅存的 0 僅僅是為了確定合并結果可以順利存放到 nums1 中。

👡解題思路

直接合并後排序

思路：最直覺的方法就是先将數組num2放進nums1的尾部，然後直接對整個數組進行排序

首先題目已經給我們提示定義好了兩個數組以及兩個變量m，n，之後用一個for循環，定義i并且設定條件為i不等于n，意思就是把第二個數組的内容放到第一個數組的後面，然後用一個排序得出nums1

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = 0; i != n; ++i) {
            nums1[m + i] = nums2[i];
        }
        Arrays.sort(nums1);
    }
}

複雜度分析

時間複雜度：O((m+n)\log(m+n))O((m+n)log(m+n))。

排序序列長度為 m+nm+n，套用快速排序的時間複雜度即可，平均情況為 O((m+n)\log(m+n))O((m+n)log(m+n))

空間複雜度：O(\log(m+n))O(log(m+n))。

排序序列長度為 m+nm+n，套用快速排序的空間複雜度即可，平均情況為 O(\log(m+n))O(log(m+n))

力扣每日一練之數組中篇Day2