LeetCode刷題（一）-----數組-------easy部分
1.兩數之和
給定一個整數數組 nums 和一個目标值 target，請你在該數組中找出和為目标值的那 兩個 整數，并傳回他們的數組下标。
數組長度：nums.length
nums.size() 擷取向量元素個數；
題解：
方法一：暴力法—暴力枚舉
暴力法很簡單，周遊每個元素 xx，并查找是否存在一個值與 target - xtarget−x 相等的目标元素。
• 時間複雜度 O(n^2)
• 空間複雜度 O(1)
• 總結：該方法簡單但是時間複雜度為O(n2),空間複雜度為O(1);運作速度慢且記憶體空間消耗大
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int i,j;
for(i=0;i<nums.size()-1;i++)
{
for(j=i+1;j<nums.size();j++)
{
if(nums[i]+nums[j]==target)
{
return {i,j};
}
}
}
return {i,j};
};
};
方法二：兩遍哈希表
為了對運作時間複雜度進行優化，我們需要一種更有效的方法來檢查數組中是否存在目标元素。如果存在，我們需要找出它的索引。保持數組中的每個元素與其索引互相對應的最好方法是什麼？哈希表。
通過以空間換取速度的方式，我們可以将查找時間從 O(n)降低到 O(1)。哈希表正是為此目的而建構的，它支援以 近似 恒定的時間進行快速查找。我用“近似”來描述，是因為一旦出現沖突，查找用時可能會退化到 O(n)。但隻要你仔細地挑選哈希函數，在哈希表中進行查找的用時應當被攤銷為 O(1)。
一個簡單的實作使用了兩次疊代。在第一次疊代中，我們将每個元素的值和它的索引添加到表中。然後，在第二次疊代中，我們将檢查每個元素所對應的目标元素（target - nums[i]）是否存在于表中。
注意，該目标元素不能是 nums[i]本身！
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map<int,int> a;//建立hash表存放數組元素
vector<int> b(2,-1);//存放結果
for(int i=0;i<nums.size();i++) //将數組元素插入哈希表中
a.insert(map<int,int>::value_type(nums[i],i));
for(int i=0;i<nums.size();i++)
{
if(a.count(target-nums[i])>0&&(a[target-nums[i]]!=i))
//判斷是否找到目标元素且目标元素不能是本身
{
b[0]=i;
b[1]=a[target-nums[i]];
break;
}
}
return b;
};
};
注：
1.該方法用map實作，map是STL的一個關聯容器，它提供一對一（其中第一個可以稱為關鍵字，每個關鍵字隻能在map中出現一次，第二個可能稱為該關鍵字的值）的資料處理能力
方法三：一編哈希表
改進：在進行疊代并将元素插入到表中的同時，我們還會回過頭來檢查表中是否已經存在目前元素所對應的目标元素。如果它存在，那我們已經找到了對應解，并立即将其傳回。
事實證明，我們可以一次完成。在進行疊代并将元素插入到表中的同時，我們還會回過頭來檢查表中是否已經存在目前元素所對應的目标元素。如果它存在，那我們已經找到了對應解，并立即将其傳回。
給定一個排序數組，你需要在原地删除重複出現的元素，使得每個元素隻出現一次，傳回移除後數組的新長度。
不要使用額外的數組空間，你必須在原地修改輸入數組并在使用 O(1) 額外空間的條件下完成。
說明:為什麼傳回數值是整數，但輸出的答案是數組呢?請注意，輸入數組是以“引用”方式傳遞的，這意味着在函數裡修改輸入數組對于調用者是可見的。
方法：雙指針法
算法
數組完成排序後，我們可以放置兩個指針 i和 j，其中 i是慢指針，而 j 是快指針。隻要 nums[i]不等于nums[j]，我們就增加 jj以跳過重複項。
當我們遇到 nums[j]不等于nums[i]時，跳過重複項的運作已經結束，是以我們必須把它（nums[j]）的值複制到 nums[i + 1]。然後遞增 i，接着我們将再次重複相同的過程，直到 j到達數組的末尾為止。
複雜度分析
• 時間複雜度：O(n)，假設數組的長度是n，那麼i和j分别最多周遊n步。
• 空間複雜度：O(1)。
27.移除元素
給定一個數組nums和一個值val，你需要原地移除所有數值等于val的元素，傳回移除後數組的新長度。
不要使用額外的數組空間，你必須在原地修改輸入數組并在使用 O(1) 額外空間的條件下完成。
元素的順序可以改變。你不需要考慮數組中超出新長度後面的元素。
我的解法：
思路
既然問題要求我們就地删除給定值的所有元素，我們就必須用 O(1)的額外空間來處理它。如何解決？我們可以保留兩個指針i和j，其中i是慢指針，j是快指針。
算法
當 nums[j]與給定的值相等時，遞增j以跳過該元素。隻要nums[j]不等于val，我們就複制 nums[j]到 nums[i]并同時遞增兩個索引。重複這一過程，直到j到達數組的末尾，該數組的新長度為i。
該解法與 删除排序數組中的重複項 的解法十分相似。
35.搜尋插入位置
給定一個排序數組和一個目标值，在數組中找到目标值，并傳回其索引。如果目标值不存在于數組中，傳回它将會被按順序插入的位置。
你可以假設數組中無重複元素。
我的解法： LeetCode刷題（一）-----數組-------easy部分 53.最大子序和
給定一個整數數組nums，找到一個具有最大和的連續子數組（子數組最少包含一個元素），傳回其最大和。
題解：思路
這道題用動态規劃的思路并不難解決，比較難的是後文提出的用分治法求解，但由于其不是最優解法，是以先不列出來
動态規劃的是首先對數組進行周遊，目前最大連續子序列和為 sum，結果為 ans。如果 sum > 0，則說明 sum 對結果有增益效果，則 sum 保留并加上目前周遊數字。如果 sum <= 0，則說明 sum 對結果無增益效果，需要舍棄，則 sum 直接更新為目前周遊數字。每次比較 sum 和 ans的大小，将最大值置為ans，周遊結束傳回結果。
時間複雜度：O(n)
代碼二
時間複雜度：O(n)
空間複雜度：O(n)
優化空間
因為以目前數結尾的最大序列和僅與前一個序列和相關，是以可以用一個變量儲存。
我的：
想知道更多解法可以去leetcode上哈。歡迎點贊^-