T1. 存在重復元素

（一）集合法

class Solution:def containsDuplicate(self, nums: List[int]) -> bool:the_set=set(nums)if len(the_set)==len(nums):return Falseelse:return True

（二）排序

? 先排序，然后判斷相鄰兩個元素是否相等。因為排序算法太多所以在此不列了。

T2. 最大子數組和

（一）窮舉法（暴力解法）

? 最基本的思想是：以每個元素作為開頭，記錄各開頭帶來的元素序列中和最大的一個；然后再比較不同元素開頭得到的元素序列中和最大的那個。

? 其實最初想要使用的是“相鄰之間比較”的方法，直接取出每個開頭最大的那一個。然而，在內循環中——如果加了下一個元素整體就變小了，不如不加這個元素；如果加了下一個元素整體變為負數，則不如不加這倆直接選取下一個開頭的；但存在概率加了下一個元素整體變小但仍然大于0，后面的序列加上也比不加好，這樣就很難操作。所以沒法在不存儲的情況下，直接通過相鄰兩個相比較的貪心算法得到最優結果。

? 因此只能存儲，即采取窮舉法：

#O(n2) class Solution:def maxSubArray(self, nums: List[int]) -> int:if len(nums)==1:return nums[0]else:all_list=[]for begin in range(len(nums)):sum=0in_list=[]for j in nums[begin:]:sum+=jin_list.append(sum)all_list.append(in_list)final=[]for l in all_list:final.append(max(l))return max(final) #如果更麻煩地來一層更無謂的循環，就是這樣： #O(n^3) class Solution:def maxSubArray(self, nums: List[int]) -> int:if len(nums)==1:return nums[0]else:all_list=[]for begin in range(len(nums)):in_list=[]for i in range(len(nums[begin:])-1):sum=0for j in nums[begin:begin+i+2]:sum+=jin_list.append(sum)all_list.append(in_list)final=[]for l in all_list:final.append(max(l))return max(final)

? 不過這屬于低效的暴力求解，超出時間限制。

（二）貪心法

? 上一個的問題其實是可以解決的，雖然*“如果加了下一個元素整體變為負數，則不如不加這倆直接選取下一個開頭的；但存在概率加了下一個元素整體變小但仍然大于0，后面的序列加上也比不加好”*，但其實就直接往后走就好了，就把max先存好，往后繼續走看看是不是更大就好了。另一個點是我沒注意到的——如果這些加起來小于0了，則為0的序列所包含的數字可以直接扔掉了，從它末尾的下一個開始繼續即可【我覺得那段代碼我寫的還算蠻有條理】（但是要注意一點就是前提是得還有下一個，要加上判斷條件）。然后就是到最前面來考慮是否存在大于0的元素，在前面加上p的判別。

#O(n) class Solution:def maxSubArray(self, nums: List[int]) -> int:for one in nums:if one<=0:p=Falseelif one>0:p=Truebreakif p:begin=one#修改后（使用了前面已經獲得的東西）#begin=nums[0]#while begin<=0:# begin=nums[nums.index(begin)+1]Max=beginSum=0for i in nums[nums.index(begin):]:Sum+=iif Sum>=0:if Sum>Max:Max=Sumelif Sum<0 and nums.index(i)<len(nums)-1:begin=nums[nums.index(i)+1]Sum=0return Maxelse:return max(nums)

如果使用的是帶#的，則會出現超時情況，原因是：index獲得的是值為-3的第一個的索引，所以那個while循環就被卡在-3無限循環了。
但是替換之后就好了。

（三）動態規劃

? 動歸的方法就是，找到了一個一一對應性，每一個元素，以其作為末尾的子串，最大長度是可以知道的，所以就構建一一對應的一個數組。而其可行性在于一個遞推關系，即i的最大sum是“它自己”與“i-1的最大sum與它自己的和”二者之間更大的那一個。（這也是基于“末尾”特征而可行的）

#1 數組 #O(n) class Solution:def maxSubArray(self, nums: List[int]) -> int:Max=[]for i in range(len(nums)):if Max==[]:Max.append(nums[0])else:Max.append(max(nums[i],nums[i]+Max[i-1]))return max(Max) #2 int #O(n) class Solution:def maxSubArray(self, nums: List[int]) -> int:Max=nums[0]now=nums[0]for i in nums[1:]:now=max(now+i,i)if now>Max:Max=nowreturn Max

T3. 兩數之和

（一）窮舉法（暴力解法）

#錯誤示例，原因還是list.index()方法對相同元素的處理造成的 class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:result=[]for i in nums:for j in nums:if i+j==target and nums.index(i)!=nums.index(j):result.append(nums.index(i))result.append(nums.index(j))return result #正確示例 class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:result=[]for i in range(len(nums)):for j in range(len(nums)):if nums[i]+nums[j]==target and i!=j:result.append(i)result.append(j)return result

（二）哈希

class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:result=[]a=[]for i in range(len(nums)):a.append(target-nums[i])for j in range(len(nums)):if nums[j]==a[j]:a[j]=Noneif nums[j] in a: #and nums[j]!=a[j]result.append(j)result.append(a.index(nums[j]))break return result

T4. 合并兩個有序數組

（一）合并＋全排序

class Solution(object):def merge(self, nums1, m, nums2, n):""":type nums1: List[int]:type m: int:type nums2: List[int]:type n: int:rtype: None Do not return anything, modify nums1 in-place instead."""for i in range(len(nums2)):nums1[i+m]=nums2[i]nums1.sort() #直接調用python內置函數了

（二）合并+對新插入的部分排序

#錯誤示例 class Solution(object):def merge(self, nums1, m, nums2, n):""":type nums1: List[int]:type m: int:type nums2: List[int]:type n: int:rtype: None Do not return anything, modify nums1 in-place instead."""for i in range(n):nums1[m+i]=nums2[i]for j in range(len(nums1[m:])):while nums1[m+j]<nums1[m+j-1]: #囿于這兩位，不能向左傳遞著排now=nums1[m+j]nums1[m+j]=nums1[m+j-1]nums1[m+j-1]=now #正確示例 #O(mn) class Solution(object):def merge(self, nums1, m, nums2, n):""":type nums1: List[int]:type m: int:type nums2: List[int]:type n: int:rtype: None Do not return anything, modify nums1 in-place instead."""for i in range(n):nums1[m+i]=nums2[i]for j in range(len(nums1[m:])):while j>-m and nums1[m+j]<nums1[m+j-1]:now=nums1[m+j]nums1[m+j]=nums1[m+j-1]nums1[m+j-1]=nowj-=1

（三）按序插入

#錯誤示例 #畢竟只涉及了nums1與nums2中元素的比較，不涉及nums2與自己已插入元素的排序，因此會錯。不過因為它本身是自帶順序的，所以只要將nums2中的元素倒序插入就好，于是有了下面的正確示例。 class Solution(object):def merge(self, nums1, m, nums2, n):""":type nums1: List[int]:type m: int:type nums2: List[int]:type n: int:rtype: None Do not return anything, modify nums1 in-place instead."""nums1=nums1[:m]for i in range(n):j=0while j<m:if nums2[i]>nums1[j]:j+=1else:break #一開始忘了加這個break了，陷入死循環nums1.insert(j,nums2[i]) #正確示例 #O(mn) class Solution(object):def merge(self, nums1, m, nums2, n):""":type nums1: List[int]:type m: int:type nums2: List[int]:type n: int:rtype: None Do not return anything, modify nums1 in-place instead."""nums1=nums1[:m]i=n-1while i>=0:j=0while j<m:if nums2[i]>nums1[j]:j+=1else:breaknums1.insert(j,nums2[i])i-=1

? 正確示例在本地環境運行，各輸出與答案相同，但是online judge不知道為什么報錯（還是直接輸出了原封不動的nums1…），待解決，不過代碼應該是沒問題吧。

T5. 兩個數組的交集

（一）窮舉法 （暴力解法）

#O(mn) class Solution(object):def intersect(self, nums1, nums2):""":type nums1: List[int]:type nums2: List[int]:rtype: List[int]"""a=[]for i in nums1:for j in range(len(nums2)):if i==nums2[j]:a.append(nums2.pop(j))breakreturn a

（二）排序＋雙指針

class Solution(object):def intersect(self, nums1, nums2):""":type nums1: List[int]:type nums2: List[int]:rtype: List[int]"""nums1.sort()nums2.sort()i=0j=0a=[]while i<len(nums1) and j<len(nums2):if nums1[i]==nums2[j]:a.append(nums1[i])i+=1j+=1elif nums1[i]>nums2[j]:j+=1elif nums1[i]<nums2[j]:i+=1return a

（三）哈希表

class Solution(object):def intersect(self, nums1, nums2):""":type nums1: List[int]:type nums2: List[int]:rtype: List[int]"""hashmap={}a=[]for i in nums1:if i not in hashmap:hashmap[i]=1else:hashmap[i]+=1for j in nums2:if j in hashmap and hashmap[j]>0:a.append(j)hashmap[j]-=1return a

初步總結：
數組類問題常使用的解決方法除了窮舉（暴力解法）外，還有哈希、雙指針、動態規劃等。

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的【leetcode记录01】 数组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。