2019.08.05

---

3.無(wú)重復(fù)字符的最長(zhǎng)字串

• 基本思想：雙指針、哈希表
• 實(shí)現(xiàn)：
• 使用 head 指向無(wú)重復(fù)子串的頭，ind 指向當(dāng)前位置（即當(dāng)前無(wú)重復(fù)子串的尾），len_max記錄當(dāng)前無(wú)重復(fù)字串的最長(zhǎng)長(zhǎng)度，使用字典的 key 存儲(chǔ)串 s 的字符，value 存儲(chǔ)字符在串中的位置。
• 當(dāng) k（當(dāng)前字符）不在字典中時(shí)，表明 k 是當(dāng)前無(wú)重復(fù)子串的尾元素，故當(dāng)前無(wú)重復(fù)字符的子串長(zhǎng)度為( ind - head + 1 )，與最大長(zhǎng)度進(jìn)行比較看是否更新，然后將此 k 放入字典中；
• 當(dāng) k 已經(jīng)存在于字典中時(shí)，還需判斷 字典中的這個(gè) k 的 value（即在串中的位置）是否大于等于 head，（因?yàn)?head 是當(dāng)前無(wú)重復(fù)子串的首位置）如果小于 head 則認(rèn)為這個(gè)已經(jīng)存在的 k 早已廢棄（與當(dāng)前無(wú)重復(fù)子串無(wú)關(guān)），與 k 不在字典中時(shí)的情況一致處理，k 的 value 大于等于 head 則認(rèn)為遇到了重復(fù)元素，k 之前的無(wú)重復(fù)子串的長(zhǎng)度為 ( ind - head )，與最大長(zhǎng)度進(jìn)行比較看是否需要更新，然后 head 跟新為 被重復(fù)了的元素 k~ 的下一個(gè)位置，這樣從 k~ 的下一個(gè)位置到當(dāng)前 k 的位置的子串又是另一個(gè)無(wú)重復(fù)子串，同時(shí)更新 k 的 value 值，最后返回依次遍歷過(guò)程中的最大長(zhǎng)度。

def lengthOfLongestSubstring(self, s: str) -> int:head = 0len_max = 0_dict = {}for ind, k in enumerate(s):if k in _dict and _dict.get(k) >= head:len_max = (ind - head) if (ind - head) > len_max else len_maxhead = _dict.get(k) + 1_dict[k] = indelse:len_max = (ind - head + 1) if (ind - head + 1) > len_max else len_max_dict[k] = indreturn len_max

15.三數(shù)之和

• 基本思想：雙指針、回溯
• 實(shí)現(xiàn)：
  1. 找組合思路：固定三個(gè)數(shù)字中最左數(shù)字的指針 a，遍歷數(shù)組找到每個(gè) a 對(duì)應(yīng)的所有滿足nums[a] + nums[b] + nums[c] == 0 的 b,c 組合：
  2. 當(dāng) nums[a] > 0 時(shí)直接跳出，因?yàn)?c > b > a，即三個(gè)數(shù)字都大于 0，在此k之后不可能找到組合了
  3. 當(dāng) a > 0 且 nums[a] == nums[a - 1] 時(shí)跳過(guò)此數(shù)字，因?yàn)?nums[a - 1] 的所有組合已經(jīng)被加入到結(jié)果中，本次搜索只會(huì)搜索到重復(fù)組合。
  4. b，c 分設(shè)在數(shù)組 [a+1, len(nums)-1] 兩端，根據(jù) sum 與 0 的大小關(guān)系交替向中間逼近，如果遇到等于 0 的組合則加入 arr 中，需要注意：移動(dòng) i，j 需要跳過(guò)所有重復(fù)值，以避免重復(fù)答案被計(jì)入 arr。

def threeSum(self, nums: List[int]) -> List[List[int]]:nums.sort()arr = []for a in range(len(nums)-2):if nums[a] > 0:break# 剪枝操作if a > 0 and nums[a] == nums[a-1]:continueb = a + 1c = len(nums) - 1while b < c:if nums[a] + nums[b] + nums[c] == 0:arr.append([nums[a], nums[b], nums[c]])b += 1c -= 1while b < c and nums[b] == nums[b-1]:b += 1while b < c and nums[c] == nums[c+1]:c -= 1elif nums[a] + nums[b] + nums[c] > 0:c -= 1while b < c and nums[c] == nums[c+1]:c -= 1else:b += 1while b < c and nums[b] == nums[b-1]:b += 1return arr

2019.08.06

---

18.四數(shù)之和

• 基本思想：雙指針、回溯
• 實(shí)現(xiàn)：可以在三數(shù)之和的基礎(chǔ)上做，或者找出所有符合條件的四數(shù)，再去重。

def fourSum(self, nums: List[int], target: int) -> List[List[int]]:nums.sort()ans=set() #去重for i in range(len(nums)-3): #固定第一個(gè)數(shù)if i > 0 and nums[i] == nums[i-1]:continue # 剪枝for j in range(i+1,len(nums)-2): #固定第二個(gè)數(shù)if j > i+1 and nums[j] == nums[j-1]:continue # 剪枝left=j+1 #左指針right=len(nums)-1 #右指針while(right>left):temp=nums[i]+nums[j]+nums[left]+nums[right]if temp==target:ans.add((nums[i],nums[j],nums[left],nums[right]))left+=1right-=1if temp>target:right-=1 #太大了，右指針左移if temp<target:left+=1 #反之res=[] #修改返回格式for i in ans:res.append(list(i))return res

2019.08.09

---

16.最接近的三數(shù)之和

• 基本思想：雙指針、回溯
• 實(shí)現(xiàn)：在三數(shù)之和的基礎(chǔ)上設(shè)置最小差值，每次出現(xiàn)新的組合時(shí)更新最小差值，并保留最小差值時(shí)的三數(shù)之和。

def threeSumClosest(self, nums: List[int], target: int) -> int:nums.sort()min_t = sys.maxsizefor i in range(len(nums) - 2):#剪枝操作if i > 0 and nums[i] == nums[i-1]:continueleft = i + 1right = len(nums) - 1while(left < right):sum_t = nums[i] + nums[right] + nums[left]if abs(sum_t - target) < min_t:min_t = abs(sum_t - target) res = sum_tif sum_t > target:right -= 1elif sum_t < target:left += 1else:return sum_treturn res 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的leetcode--数组（Medium1）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。