簡述

想要撿起算法功底。
準備長期更新這個blog，對每個算法都做簡要的分析。便于以后復習的時候，通過一些簡短的話，就能想起來。

另外會在題目上寫上，用的方法的縮寫，這樣以后想找對應考點啥的時候也好找。

文章目錄

• 簡述
• • 1-兩數之和(哈希表)
  • 15-三數之和(雙指針法)
  • 18-四數之和(雙指針法)
  • 2-兩數相加 (鏈表)
  • 3-無重復字符的最長子串(哈希+滑動窗口)

1-兩數之和(哈希表)

• 建立哈希表，存儲歷史被訪問過的節點。然后差差值是否被寫入過即可。
• https://leetcode-cn.com/problems/two-sum/

from typing import Listclass Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:hashtable = {}for i in range(len(nums)):if target - nums[i] in hashtable:return [hashtable[target - nums[i]], i]hashtable[nums[i]] = ireturn []

15-三數之和(雙指針法)

• https://leetcode-cn.com/problems/3sum/

暴力求解的方式，就是三層遍歷。注意去重： 每一層只有跟上次枚舉的數值不一樣的時候，才會枚舉。時間復雜度O(N^3)

但是這樣太慢了，畢竟有三層循環。一個很顯然的想法，就是認為選了一個數之后，剩下不就是一個兩數之和的問題了嗎。而兩數之和的解法是O(N)，這樣時間就可以被壓縮到只有O(N^2)

用兩數之和的空間換時間的解法。來代替選定第一個數之后，剩下兩個但是這樣就沒有考慮重復解的問題。所以以后再看看這個方法吧。時間復雜度O(N^2)

雙指針解法。這個方法的前提條件是，數組是有序的。因此用一次快排。O(nlogn) 。

遍歷第一個數a[i]。

從i+1開始遍歷第二個數a[j]，同時，讓第三個數a[k]選最后一個數a[n-1]。

如果a[i]+a[j]+a[k] == 0 ，完美，記錄一個組合j,k同時向中間靠攏。

如果a[i]+a[j]+a[k] > 0 ，k--

如果a[i]+a[j]+a[k] < 0 ，j++

雙指針法解釋：

• 這里理解為同時在遍歷i,j會比較好理解一點。
• 因為已經排過序的，所以之后所有的a[j]都會大于 現在的a[j](只有大于是因為不允許重復)
• 這種情況下，去看第4步，相當于說，出現a[i]+a[j]+a[k] > 0，說明未來所有更大的j，更大甚至現在這個k其實都不用看了。
• 同樣的，其實j,k是對稱的，這里如果理解為同時在遍歷i,k（只不過k是在反向遍歷）
• 由于序列已經被排過序了，所以，后面出現的a[k]，一定是會比現在的a[k]要小。
• 這種情況下，去看第5步，相當于說，出現a[i]+a[j]+a[k] < 0，說明未來所有更小的k，更小甚至現在這個j其實也都不用看了。

from typing import List class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:ans = []nums = sorted(nums)for i in range(0, len(nums)-1):if i > 0 and nums[i] == nums[i-1]:continuej, k = i+1, len(nums) - 1update_J, update_K = False, Falsewhile j < k:if nums[i] + nums[j] + nums[k] == 0:ans.append([nums[i], nums[j], nums[k]])update_J = Trueupdate_K = Trueelif nums[i] + nums[j] + nums[k] > 0:update_K = Trueelif nums[i] + nums[j] + nums[k] < 0:update_J = Trueif update_J:j += 1while (j < k) & (nums[j] == nums[j-1]):j += 1update_J = Falseif update_K:k -= 1while (j < k) & (nums[k] == nums[k+1]):k -= 1update_K = Falseif j == k:breakreturn ans

18-四數之和(雙指針法)

• https://leetcode-cn.com/problems/4sum/submissions/
• 跟三數之和一樣，就是再加一層循環就好了。算法復雜度被壓縮到了O(N^3)

from typing import List class Solution:def fourSum(self, nums: List[int], target: int) -> List[List[int]]:ans = []n = len(nums)nums = sorted(nums)update_P, update_Q = False, False# print(nums)for i in range(0, n-2):if i > 0 and nums[i] == nums[i-1]:continuefor j in range(i+1, n-1):if j > i+1 and nums[j] == nums[j-1]:continuep, q = j + 1, n - 1while p < q:# print(i, j, p, q)if nums[i] + nums[j] + nums[p] + nums[q] == target:ans.append([nums[i], nums[j], nums[p], nums[q]])update_P, update_Q = True, Trueif nums[i] + nums[j] + nums[p] + nums[q] < target:update_P = Trueif nums[i] + nums[j] + nums[p] + nums[q] > target:update_Q = Trueif update_P:p += 1while p < q and nums[p] == nums[p-1]:p += 1update_P = Falseif update_Q:q -= 1while p < q and nums[q] == nums[q + 1]:q -= 1update_Q = Falsereturn ans

2-兩數相加 (鏈表)

• 這個主要是鏈表使用考察，很簡單的。
• 用一個指針記錄整個鏈表表頭，用一個指針記錄當前的指針位置就好了。

# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = Noneclass Solution:def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:x, y, flag = 0, 0, 0ans, cur = None, Nonewhile (l1 is not None) or (l2 is not None):x = 0 if l1 is None else l1.valy = 0 if l2 is None else l2.vall1 = None if l1 is None else l1.nextl2 = None if l2 is None else l2.nextx = x + y + flagflag = x // 10x = x % 10if ans is None:ans = ListNode(x)cur = anselse:cur.next = ListNode(x)cur = cur.nextwhile flag != 0:cur.next = ListNode(flag)cur = cur.nextflag //= 10if ans is None:return ListNode(0)return ans

3-無重復字符的最長子串(哈希+滑動窗口)

• 用個哈希表記錄訪問過的字符的最新位置
• 用滑動窗口的機制
• 對于最新訪問的字符，看該字符是否被訪問過.
  • 如果出現沖突，那么就是將窗口左側跳到沖突字符歷史最新位置+1的地方。

class Solution:def lengthOfLongestSubstring(self, s: str) -> int:charPos = {}ans, start = 0, 0for i in range(len(s)):if (s[i] in charPos) and (charPos[s[i]] >= start):start = charPos[s[i]] + 1ans = max(ans, i - start + 1)charPos[s[i]] = ireturn ans

總結

以上是生活随笔為你收集整理的[Leetcode]笔记的全部內容，希望文章能夠幫你解決所遇到的問題。

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