題目01：兩數之和
題目02：刪除排序數組中的重複項
題目03：移除元素
題目04：最大子序和
題目05：盛最多水的容器
題目06：搜索旋轉排序數組
題目07：數組中的第K個最大元素
題目08：除自身以外數組的乘積
題目09：尋找兩個有序數組的中位數
題目10：缺失的第一個正數
題目01：兩數之和https://leetcode-cn.com/problems/two-sum/給定一個整數數組 nums 和一個目標值 target，請你在該數組中找出和為目標值的那 兩個整數，並返回他們的數組下標。
你可以假設每種輸入只會對應一個答案。但是，你不能重複利用這個數組中同樣的元素。
示例1:
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9，所以返回 [0, 1]示例2：
給定 nums = [230, 863, 916, 585, 981, 404, 316, 785, 88, 12, 70, 435, 384, 778, 887, 755, 740, 337, 86, 92, 325, 422, 815, 650, 920, 125, 277, 336, 221, 847, 168, 23, 677, 61, 400, 136, 874, 363, 394, 199, 863, 997, 794, 587, 124, 321, 212, 957, 764, 173, 314, 422, 927, 783, 930, 282, 306, 506, 44, 926, 691, 568, 68, 730, 933, 737, 531, 180, 414, 751, 28, 546, 60, 371, 493, 370, 527, 387, 43, 541, 13, 457, 328, 227, 652, 365, 430, 803, 59, 858, 538, 427, 583, 368, 375, 173, 809, 896, 370, 789], target = 542
因為 nums[28] + nums[45] = 221 + 321 = 542，所以返回 [28, 45]參考代碼：
思路：直接利用暴力匹配算法。
執行用時：432 ms, 在所有 C# 提交中擊敗了 65.82% 的用戶內存消耗：30.8 MB, 在所有 C# 提交中擊敗了 8.67% 的用戶public class Solution
{
public int[] TwoSum(int[] nums, int target)
{
int[] result = new int[2];
for (int i = 0; i < nums.Length - 1; i++)
{
int find = target - nums[i];
for (int j = i + 1; j < nums.Length; j++)
{
if (find == nums[j])
{
result[0] = i;
result[1] = j;
return result;
}
}
}
return result;
}
}
題目02：刪除排序數組中的重複項https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/給定一個 排序數組，你需要在 原地 刪除重複出現的元素，使得每個元素只出現一次，返回移除後數組的新長度。
不要使用額外的數組空間，你必須在 原地修改輸入數組 並在使用 O(1) 額外空間的條件下完成。
示例 1:
給定數組 nums = [1,1,2],
函數應該返回新的長度 2, 並且原數組 nums 的前兩個元素被修改為 1, 2。
你不需要考慮數組中超出新長度後面的元素。示例 2:
給定 nums = [0,0,1,1,1,2,2,3,3,4],
函數應該返回新的長度 5, 並且原數組 nums 的前五個元素被修改為 0, 1, 2, 3, 4。
你不需要考慮數組中超出新長度後面的元素。說明:
為什麼返回數值是整數，但輸出的答案是數組呢?
請注意，輸入數組是以「引用」方式傳遞的，這意味著在函數裡修改輸入數組對於調用者是可見的。
你可以想像內部操作如下:
// nums 是以「引用」方式傳遞的。也就是說，不對實參做任何拷貝
int len = removeDuplicates(nums);
// 在函數裡修改輸入數組對於調用者是可見的。
// 根據你的函數返回的長度, 它會列印出數組中該長度範圍內的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}參考代碼：
思路：雙索引法，就是一個快索引一個慢索引，j快i慢，當nums[j] == nums[i]時，j++就可以跳過重複項，不相等時，讓i++並讓nums[i] = nums[j]，把值複製過來繼續執行到末尾即可，時間複雜度為O(n)。
執行用時：300 ms, 在所有 C# 提交中擊敗了 64.43% 的用戶內存消耗：33.5 MB, 在所有 C# 提交中擊敗了 5.48% 的用戶public class Solution
{
public int RemoveDuplicates(int[] nums)
{
if (nums.Length < 2)
return nums.Length;
int i = 0;
for (int j = 1; j < nums.Length; j++)
{
if (nums[j] != nums[i])
{
i++;
nums[i] = nums[j];
}
}
return i + 1;
}
}
題目03：移除元素https://leetcode-cn.com/problems/remove-element/給定一個數組nums和一個值val，你需要原地移除所有數值等於val的元素，返回移除後數組的新長度。
不要使用額外的數組空間，你必須在原地修改輸入數組並在使用 O(1) 額外空間的條件下完成。
元素的順序可以改變。你不需要考慮數組中超出新長度後面的元素。
示例 1:
給定 nums = [3,2,2,3], val = 3,
函數應該返回新的長度 2, 並且 nums 中的前兩個元素均為 2。
你不需要考慮數組中超出新長度後面的元素。示例 2:
給定 nums = [0,1,2,2,3,0,4,2], val = 2,
函數應該返回新的長度 5, 並且 nums 中的前五個元素為 0, 1, 3, 0, 4。
注意這五個元素可為任意順序。
你不需要考慮數組中超出新長度後面的元素。示例 3:
輸入：[] value = 0
輸出：0示例 4:
輸入：[1] value = 1
輸出：0示例 5:
輸入：[4,5] value = 5
輸出：1說明:
為什麼返回數值是整數，但輸出的答案是數組呢?
請注意，輸入數組是以「引用」方式傳遞的，這意味著在函數裡修改輸入數組對於調用者是可見的。
你可以想像內部操作如下:
// nums 是以「引用」方式傳遞的。也就是說，不對實參作任何拷貝
int len = removeElement(nums, val);
// 在函數裡修改輸入數組對於調用者是可見的。
// 根據你的函數返回的長度, 它會列印出數組中該長度範圍內的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}參考代碼：
思路：雙索引法，利用雙索引i和j，i為慢索引拖後，j為快索引向前衝。如果nums[j]!=val，將num[j]的值賦給num[i]，循環結束後，i指針前面的元素，即為需要保留的元素，從而達到了移除元素的目的，時間複雜度為 O(n)。
執行用時：272 ms, 在所有 C# 提交中擊敗了 94.41% 的用戶內存消耗：29.9 MB, 在所有 C# 提交中擊敗了 5.21% 的用戶public class Solution
{
public int RemoveElement(int[] nums, int val)
{
int i = 0;
for (int j = 0; j < nums.Length; j++)
{
if (nums[j] != val)
{
nums[i] = nums[j];
i++;
}
}
return i;
}
}
題目04：最大子序和https://leetcode-cn.com/problems/maximum-subarray/給定一個整數數組nums，找到一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。
示例 1:
輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續子數組 [4,-1,2,1] 的和最大，為 6。示例 2:
輸入: [-2,1],
輸出: 1進階:
如果你已經實現複雜度為O(n)的解法，嘗試使用更為精妙的分治法求解。
參考代碼：
思路：利用暴力算法。
執行用時: 596 ms, 在所有 C# 提交中擊敗了 14.18% 的用戶內存消耗: 24.5 MB, 在所有 C# 提交中擊敗了 5.88% 的用戶public class Solution {
public int MaxSubArray(int[] nums) {
int len = nums.Length;
if (len == 0)
return 0;
if (len == 1)
return nums[0];
int max = int.MinValue;
for (int i = 0; i < len; i++)
{
int sum = nums[i];
if (sum > max)
{
max = sum;
}
for (int j = i + 1; j < len; j++)
{
sum += nums[j];
if (sum > max)
{
max = sum;
}
}
}
return max;
}
}
題目05：盛最多水的容器https://leetcode-cn.com/problems/container-with-most-water/給定n個非負整數a1，a2，...，an，每個數代表坐標中的一個點(i, ai)。在坐標內畫n條垂直線，垂直線i 的兩個端點分別為(i, ai)和(i, 0)。找出其中的兩條線，使得它們與x軸共同構成的容器可以容納最多的水。
說明：你不能傾斜容器，且n的值至少為 2。
圖中垂直線代表輸入數組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍色部分）的最大值為 49。
示例:
輸入: [1,8,6,2,5,4,8,3,7]
輸出: 49參考代碼：
思路：利用雙索引的方法。
以0-7走到1-7這一步為例，解釋為什麼放棄0-6這一分支：
用h(i)表示第i條線段的高度，S(ij)表示第i條線段和第j條線段圈起來的面積。
已知 h(0) < h(7)，從而S(07) = h(0) * 7。
有S(06) = min(h(0), h(6)) * 6。
當h(0) <= h(6)，有S(06) = h(0) * 6；
當h(0) > h(6)，有S(06) = h(6) * 6，S(06) < h(0) * 6。
由此可知，S(06)必然小於S(07)。把每一棵子樹按照同樣的方法分析，很容易可以知道，雙索引法走的路徑包含了最大面積。
執行用時: 144 ms, 在所有 C# 提交中擊敗了 99.64% 的用戶內存消耗: 26.6 MB, 在所有 C# 提交中擊敗了 5.45% 的用戶public class Solution
{
public int MaxArea(int[] height)
{
int i = 0, j = height.Length - 1;
int max = int.MinValue;
while (i < j)
{
int temp = (j - i) * Math.Min(height[i], height[j]);
if (temp > max)
{
max = temp;
}
if (height[i] < height[j])
{
i++;
}
else
{
j--;
}
}
return max;
}
}
題目06：搜索旋轉排序數組https://leetcode-cn.com/problems/search-in-rotated-sorted-array/假設按照升序排序的數組在預先未知的某個點上進行了旋轉。
( 例如，數組 [0,1,2,4,5,6,7] 可能變為 [4,5,6,7,0,1,2] )。
搜索一個給定的目標值，如果數組中存在這個目標值，則返回它的索引，否則返回 -1 。
你可以假設數組中不存在重複的元素。
你的算法時間複雜度必須是O(log n)級別。
示例 1:
輸入: nums = [4,5,6,7,0,1,2], target = 0
輸出: 4示例 2:
輸入: nums = [4,5,6,7,0,1,2], target = 3
輸出: -1示例 3:
輸入: nums = [5,1,3], target = 5
輸出: 0示例 4:
輸入: nums = [4,5,6,7,8,1,2,3], target = 8
輸出: 4示例 5:
輸入: nums = [3,1], target = 1
輸出: 1參考代碼：
思路：利用二分法。
執行用時: 128 ms, 在所有 C# 提交中擊敗了 97.17% 的用戶內存消耗: 23.8 MB, 在所有 C# 提交中擊敗了 12.00% 的用戶public class Solution
{
public int Search(int[] nums, int target)
{
int i = 0, j = nums.Length - 1;
while (i <= j)
{
int mid = (i + j) / 2;
if (nums[mid] == target)
return mid;
if (nums[mid] >= nums[i])
{
//左半部分有序
if (target > nums[mid])
{
i = mid + 1;
}
else
{
if (target == nums[i])
return i;
if (target > nums[i])
j = mid - 1;
else
i = mid + 1;
}
}
else
{
if (target < nums[mid])
{
j = mid - 1;
}
else
{
if (target == nums[j])
return j;
if (target < nums[j])
i = mid + 1;
else
j = mid - 1;
}
}
}
return -1;
}
}
題目07：數組中的第K個最大元素https://leetcode-cn.com/problems/kth-largest-element-in-an-array/在未排序的數組中找到第 k 個最大的元素。請注意，你需要找的是數組排序後的第 k 個最大的元素，而不是第 k 個不同的元素。
示例 1:
輸入: [3,2,1,5,6,4] 和 k = 2
輸出: 5示例 2:
輸入: [3,2,3,1,2,4,5,5,6] 和 k = 4
輸出: 4說明:
你可以假設 k 總是有效的，且 1 ≤ k ≤ 數組的長度。
參考代碼：
思路：利用排序的方法。
執行用時: 152 ms, 在所有 C# 提交中擊敗了 76.47% 的用戶內存消耗: 24.6 MB, 在所有 C# 提交中擊敗了 5.55% 的用戶public class Solution
{
public int FindKthLargest(int[] nums, int k)
{
nums = nums.OrderBy(a => a).ToArray();
return nums[nums.Length - k];
}
}
題目08：除自身以外數組的乘積https://leetcode-cn.com/problems/product-of-array-except-self/給定長度為n的整數數組nums，其中n > 1，返回輸出數組output，其中output[i]等於 nums中除nums[i]之外其餘各元素的乘積。
示例:
輸入: [1,2,3,4]
輸出: [24,12,8,6]說明: 請不要使用除法，且在O(n) 時間複雜度內完成此題。
進階：
你可以在常數空間複雜度內完成這個題目嗎？（ 出於對空間複雜度分析的目的，輸出數組不被視為額外空間。）
參考代碼：
思路：乘積 = 當前數左邊的乘積 * 當前數右邊的乘積
[1, 2, 3, 4]
左邊的乘積 [1, 1, 2, 6]
右邊的乘積 [24,12,4, 1]
結果 = 左*右 [24,12,8, 6]
執行用時: 304 ms, 在所有 C# 提交中擊敗了 100.00% 的用戶內存消耗: 34.6 MB, 在所有 C# 提交中擊敗了 100.00% 的用戶public class Solution
{
public int[] ProductExceptSelf(int[] nums)
{
int len = nums.Length;
int[] output1 = new int[len];//正向乘積
int[] output2 = new int[len];//反向乘積
output1[0] = 1;
output2[len - 1] = 1;
for (int i = 1; i < len; i++)
{
output1[i] = output1[i - 1]*nums[i - 1];
output2[len - i - 1] = output2[len - i]*nums[len - i];
}
for (int i = 0; i < len; i++)
{
output1[i] *= output2[i];
}
return output1;
}
}
題目09：尋找兩個有序數組的中位數https://leetcode-cn.com/problems/median-of-two-sorted-arrays/給定兩個大小為m和n的有序數組nums1和nums2。
請你找出這兩個有序數組的中位數，並且要求算法的時間複雜度為O(log(m + n))。
你可以假設nums1和nums2不會同時為空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
則中位數是 2.0示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
則中位數是 (2 + 3)/2 = 2.5參考代碼：
思路：利用二分策略。
中位數：用來將一個集合劃分為兩個長度相等的子集，其中一個子集中的元素總是大於另一個子集中的元素。
由於題目要求時間複雜度為O(log(m + n))，所以不能從兩個有序數組的首尾挨個遍歷來找到中位數（複雜度 O(m + n)）；而是要通過二分策略，通過每次比較，能夠直接按比例的刷掉一組數字，最後找到中位數（複雜度O(log(m + n))）。
nums1: [a1,a2,a3,...am]
nums2: [b1,b2,b3,...bn]
[nums1[:i],nums2[:j] | nums1[i:], nums2[j:]]
nums1 取 i 個數的左半邊
nums2 取 j = (m+n+1)/2 - i 的左半邊只要保證左右兩邊 個數 相同，中位數就在 | 這個邊界旁邊產生，從而可以利用二分法找到合適的i。
執行用時: 160 ms, 在所有 C# 提交中擊敗了 99.18% 的用戶內存消耗: 26.8 MB, 在所有 C# 提交中擊敗了 5.05% 的用戶public class Solution {
public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.Length;
int n = nums2.Length;
if (m > n)
return FindMedianSortedArrays(nums2, nums1);
int k = (m + n + 1)/2;
int left = 0;
int right = m;
while (left < right)
{
int i = (left + right)/2;
int j = k - i;
if (nums1[i] < nums2[j - 1])
left = i + 1;
else
right = i;
}
int m1 = left;
int m2 = k - left;
int c1 = Math.Max(m1 == 0 ? int.MinValue : nums1[m1 - 1],
m2 == 0 ? int.MinValue : nums2[m2 - 1]);
if ((m + n)%2 == 1)
return c1;
int c2 = Math.Min(m1 == m ? int.MaxValue : nums1[m1],
m2 == n ? int.MaxValue : nums2[m2]);
return (c1 + c2)*0.5;
}
}
題目10：缺失的第一個正數https://leetcode-cn.com/problems/first-missing-positive/給定一個未排序的整數數組，找出其中沒有出現的最小的正整數。
示例1:
輸入: [1,2,0]
輸出: 3示例2:
輸入: [3,4,-1,1]
輸出: 2示例3:
輸入: [7,8,9,11,12]
輸出: 1示例4:
輸入: [1,1]
輸出: 2實例5:
輸入: []
輸出: 1說明:
你的算法的時間複雜度應為O(n)，並且只能使用常數級別的空間。
參考代碼：
思路：把數組進行一次「排序」，「排序」的規則是：如果這個數字i落在「區間範圍裡」，i就應該放在索引為i - 1的位置上。
執行用時：100 ms, 在所有 C# 提交中擊敗了 93.75% 的用戶內存消耗：24.2 MB, 在所有 C# 提交中擊敗了 97.44% 的用戶public class Solution {
public int FirstMissingPositive(int[] nums) {
int len = nums.Length;
for (int i = 0; i < len; i++)
{
while (nums[i] != i + 1 && nums[i] <= len && nums[i] > 0 && nums[i] != nums[nums[i] - 1])
{
int temp = nums[i];
nums[i] = nums[temp - 1];
nums[temp - 1] = temp;
}
}
for (int i = 0; i < len; i++)
{
if (nums[i] != i + 1)
{
return i + 1;
}
}
return len + 1; //nums.Length = 0
}
}後臺回復「搜搜搜」，隨機獲取電子資源！
歡迎關注，請掃描二維碼：