Table of Contents:

🤔

　　相似的事物放一起，是讓環境井然有序的關鍵，這也是電腦世界中陣列（Array）此資料結構的設計理念。因為事物都在同處，我們可藉索引在常數時間（O(1)）內找到對應元素（隨機存取）。

　　如果不是相似的事物，如果不放在一起，我們還有方法能好好整理它們嗎？可以，用鍵（Key）值（Value）架構即可。我們先定好一個雜湊（Hashing）函數，讓要管理的事物都依循此函數的判斷放到對應區塊中。這樣就能在常數時間（O(1)）內找到鍵所對應的值。

　　以下為LeetCode中，與陣列（Array）和雜湊（Hashing）有關的題目與解答摘要。題目只會更多，但解題核心往往不變，祝大家都只練少量題目就在競試中有良好表現😊。

💡

有時反向遍歷陣列，做法會簡單很多
程式碼要一開始就簡潔很難，寫完再整理比較容易
善用陣列索引的有序性，有時會比雜湊表還好用

😎303. Range Sum Query – Immutable

Description

　　給予一個整數陣列nums，請將其化為一種資料結構，能夠應對sumRange(left, right)的要求（對於left ≤ right，回傳此區間內的元素和）。

Example 1:

Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]
Explanation
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1
numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3

Solutions

Approach #1: Brute Force

　　我們可以直接遍歷區段內的元素並加總。

　　這樣的時間複雜度為O(N)，空間複雜度為O(1)。

class NumArray:

    def __init__(self, nums: List[int]):
        self.arr = nums

    def sumRange(self, left: int, right: int) -> int:
        res = 0
        for i in range(left, right + 1):
            res += self.arr[i]

        return res

⭐Approach #2: Caching

　　若過程運算多次，紀錄先前算過的成果就能加快效能。但若儲存每個可能區間，空間複雜度會高達O(N²)。我們可藉sumRange[i, j] = sumRange[0, j] - sumRange[0, i]這概念，降低空間複雜度至O(N)，

　　這樣的時間複雜度可達O(1)，空間複雜度為O(N)。

class NumArray:
    def __init__(self, nums):
        self.sum = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            self.sum[i + 1] = self.sum[i] + nums[i]

    def sumRange(self, i, j):
        return self.sum[j + 1] - self.sum[i]

😐304. Range Sum Query 2D -Immutable

Description

　　給予一個二維陣列matrix，請建構一個資料結構NumMatrix，它的方法sumRegion能求出範圍內的數總和。

Example 1:

Input
["NumMatrix", "sumRegion", "sumRegion", "sumRegion"]
[[[[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]]
Output
[null, 8, 11, 12]
Explanation
NumMatrix numMatrix = new NumMatrix([[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (i.e sum of the red rectangle)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (i.e sum of the green rectangle)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (i.e sum of the blue rectangle)

Solutions

❌Approach #1: Brute Force

　　我們可以直接計算，但在一些測試案例中會運算超時。

　　這樣的時間複雜度可達O(M*N)，空間複雜度為O(1)。

class NumMatrix:
    def __init__(self, matrix):
        self.data = matrix

    def sumRegion(self, row1, col1, row2, col2):
        total = 0
        for r in range(row1, row2 + 1):
            for c in range(col1, col2 + 1):
                total += self.data[r][c]
        return total

⭐Approach #2: Caching Smarter

　　如同前題（No. 303），我們可在初始化時先儲存計算成果，減少日後運算。如何有效地儲存成果，我們以下圖的原點O（[0, 0]）、A（[row1, col1]）、B（[row1, col2]）、C（[row2, col1]）、D（[row2, col2]）點來說明：

算出整體面積Sum(OD)
將整體面積減去Sum(OB)、Sum(OC)，再加上Sum(OA)，即為所求Sum(AD)
注意，記憶陣列dp的長寬各為原本大小再+1，代表的是端點座標

　　這樣的時間複雜度為O(1)，空間複雜度為O(M*N)。

class NumMatrix:
    def __init__(self, matrix):
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return
        self.dp = [[0] * (len(matrix[0]) + 1) for _ in range(len(matrix) + 1)]
        for r in range(len(matrix)):
            for c in range(len(matrix[0])):
                self.dp[r + 1][c + 1] = (self.dp[r + 1][c]
                                         + self.dp[r][c + 1]
                                         + matrix[r][c]
                                         - self.dp[r][c]
                                         )

    def sumRegion(self, row1, col1, row2, col2):
        return (
                self.dp[row2 + 1][col2 + 1]
                - self.dp[row1][col2 + 1]
                - self.dp[row2 + 1][col1]
                + self.dp[row1][col1]
        )

😐307. Range Sum Query – Mutable

Description

　　給予一個整數陣列nums，請建構一個資料結構NumArray，其方法：

update(index, val)：將索引index處的值更新為val
sumRange(left, right)：回傳包含左右兩點的數和

Example 1:

Input
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
Output
[null, 9, null, 8]
Explanation
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // return 1 + 3 + 5 = 9
numArray.update(1, 2);   // nums = [1, 2, 5]
numArray.sumRange(0, 2); // return 1 + 2 + 5 = 8

Solutions

❌Approach #1: Naive

　　我們可以先直觀地處理，但這樣的解法在一些測試案例中會超時。

　　這樣的時間複雜度為O(N)，空間複雜度為O(1)。

class NumArray:
    def __init__(self, nums):
        self.nums = nums

    def sumRange(self, i, j):
        total = 0
        for l in range(i, j + 1):
            total += self.nums[l]
        return total

    def update(self, i, val):
        self.nums[i] = val

⭐Approach #2: Segment Tree

　　此題適合使用線段樹（Segment Tree），它會把每個數做為一棵二元樹的葉子節點，依循其架構就能在O(logN)內找到元素和或是修改資料。

　　這樣的時間複雜度為O(logN)，空間複雜度為O(n)。

class NumArray:
    # space: O(n)
    def __init__(self, nums: List[int]):
        if len(nums) > 0:
            self.n = len(nums)
            self.tree = [0] * (self.n * 2)
            self.buildTree(nums)

    # time: O(n)
    def buildTree(self, nums):
        for i in range(self.n, self.n * 2):
            self.tree[i] = nums[i - self.n]
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[i * 2] + self.tree[i * 2 + 1]

    def update(self, pos: int, val: int) -> None:
        pos += self.n
        self.tree[pos] = val
        while pos > 0:
            left = pos
            right = pos
            if pos % 2 == 0:
                right = pos + 1
            else:
                left = pos - 1
            # parent is updated after child is updated
            self.tree[pos // 2] = self.tree[left] + self.tree[right]
            pos //= 2

    def sumRange(self, l: int, r: int) -> int:
        # get leaf with index 'l' and 'r'
        l += self.n
        r += self.n
        sum = 0
        while l <= r:
            # if l is right child of its parent
            if l % 2 == 1:
                sum += self.tree[l]
                l += 1
            # if r is left child of its parent
            if r % 2 == 0:
                sum += self.tree[r]
                r -= 1
            l //= 2
            r //= 2
        return sum

😐347. Top K Frequent Elements

Description

　　給予一個整數陣列nums和一個整數k，請回傳陣列中出現頻率≥k的元素。

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Input: nums = [1], k = 1
Output: [1]

Solutions

Approach #1 使用堆積（Heap）

　　要求前K項元素，我們通常會想到優先佇列（Prioirty Queue），也就是堆積（Heap）。我們：

將元素與出現次數建為一個雜湊表（count）
用內建函式heapq.nlargest()，建立一個前K大的陣列
回傳它即

　　這樣的時間複雜度為O(NlogK)（僅排序前K個），空間複雜度則為O(N+K)（雜湊表O(N)，堆積O(K)）。

from collections import Counter
import heapq

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # O(1) time 
        if k == len(nums):
            return nums

        # 1. build hash map : character and how often it appears
        # O(N) time
        count = Counter(nums)
        # 2-3. build heap of top k frequent elements and
        # convert it into an output array
        # O(N log k) time
        return heapq.nlargest(k, count.keys(), key=count.get)

⭐Approach #2 用陣列索引值分類出現次數不同的元素

　　我們可將陣列索引值當成歸類的鍵。我們：

用一個雜湊表count統計元素與其出現次數
創造一個列數n+1的二維陣列，將count值依鍵放入索引值相同的陣列中
從尾端遍歷此陣列，將索引值≥k者納入res

　　這樣的時間和空間複雜度皆為O(n)。

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = {}
        freq = [[] for i in range(len(nums) + 1)]

        for n in nums:
            count[n] = 1 + count.get(n, 0)
        for n, c in count.items():
            freq[c].append(n)

        res = []
        for i in range(len(freq) - 1, 0, -1):
            for n in freq[i]:
                res.append(n)
                if len(res) == k:
                    return res

😎392. Is Subsequence

Description

　　給予兩個字串s和t，如果s是t的子序列（subsequence ）則回傳True，否則回傳False。

Example 1:

Input: s = "abc", t = "ahbgdc"
Output: true

Example 2:

Input: s = "axc", t = "ahbgdc"
Output: false

Solutions

⭐Approach #1: Two-Pointers

　　我們可以用Two-Pointers來解題：

用l和r兩指標遍歷字串s和t
- 若s[l] == t[r]，代表t當下字元已符合，可讓r往前，
- 持續讓r往前，用下個字元判斷是否符合
遍歷完s或t時，判斷l==len(s)是否為真，看s是否已比對完成

　　這樣的時間複雜度為O(|S|)，空間複雜度為O(1)。

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        l = 0
        r = 0
        while l < len(s) and r < len(t):
            if s[l] == t[r]:
                l += 1
            r += 1

        return l == len(s)

😐438. Find All Anagrams in a String

Description

　　給予兩字串s和p，請回傳在s中所有能成為p的異位構詞（anagram）之字串起始點索引為一陣列。

Example 1:

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

Solutions

⭐Approach #1: Sliding Window

　　我們可先統計p內的字元出現頻率，再用移動視窗判斷所夾擊的s子字串，其字元出現頻率也相同。

　　這樣的時間複雜度為O(N_S)，空間複雜度為O(K)。N_S為s的長度，K為出現過的元素數量。

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        l = 0
        counterP = Counter(p)
        counterS = Counter(s[0:len(p) - 1])
        res = []

        for r in range(len(p) - 1, len(s)):
            counterS[s[r]] = counterS.get(s[r], 0) + 1
            if counterP == counterS:
                res.append(l)
            l += 1
        return res

😎485. Max Consecutive Ones

Description

　　給予一個二元陣列nums，請回傳其中元素1最大連續長。

Example 1:

Input: nums = [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s. The maximum number of consecutive 1s is 3.

Example 2:

Input: nums = [1,0,1,1,0,1]
Output: 2

Solutions

⭐Approach #1: One pass

　　我們可以遍歷一次陣列，統計連續出現的最大長度。

　　這樣的時間複雜度為O(N)，空間複雜度為O(1)。

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        count = max_count = 0
        for num in nums:
            if num == 1:
                count += 1
            else:
                max_count = max(max_count, count)
                count = 0
        return max(max_count, count)

😎448. Find All Numbers Disappeared in an Array

Description

　　給予一個具備n個整數的陣列nums，其數值界在[1, n]內，請以一個陣列形式，回傳沒出現在此範圍內的數字。

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]

Example 2:

Input: nums = [1,1]
Output: [2]

Solutions

Approach #1: Using Hash Map

　　如果使用雜湊表，此題可以輕易地處理。

　　這樣的時間與空間複雜度皆為O(N)。

class Solution(object):
    def findDisappearedNumbers(self, nums):
        hash_table = {}
        for num in nums:
            hash_table[num] = 1

        result = []

        for num in range(1, len(nums) + 1):
            if num not in hash_table:
                result.append(num)

        return result

⭐Approach #2: O(1) Space InPlace Modification Solution

　　若要讓空間複雜度降為O(1)，我們得善用所給陣列，方法為：

以索引值作為數值範圍，但得注意索引值從0開始
遍歷陣列，將索引值對應數值變為負
再次遍歷陣列，若值>0代表沒出現過，加到陣列res中
回傳res

　　這樣的時間複雜度為O(N)，空間複雜度為O(1)。

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        for i in range(len(nums)):
            new_index = abs(nums[i]) - 1
            if nums[new_index] > 0:
                # 代表出現過一次
                nums[new_index] *= -1

        result = []

        for i in range(1, len(nums) + 1):
            # 代表沒出現過
            if nums[i - 1] > 0:
                result.append(i)

        return result

😐487. Max Consecutive Ones II

Description

　　給予一個二元陣列nums，若能反轉一次0為1，請回傳1所能連續的最大長度。

Example 1:

Input: nums = [1,0,1,1,0]
Output: 4
Explanation: 
- If we flip the first zero, nums becomes [1,1,1,1,0] and we have 4 consecutive ones.
- If we flip the second zero, nums becomes [1,0,1,1,1] and we have 3 consecutive ones.
The max number of consecutive ones is 4.

Example 2:

Input: nums = [1,0,1,1,0,1]
Output: 4
Explanation: 
- If we flip the first zero, nums becomes [1,1,1,1,0,1] and we have 4 consecutive ones.
- If we flip the second zero, nums becomes [1,0,1,1,1,1] and we have 4 consecutive ones.
The max number of consecutive ones is 4.

Solutions

⭐Approach #1: Sliding Window

　　我們可以用移動視窗來解題：

用指標l和r當作窗口邊界，zeroCount記錄窗口內的0數量，res記錄最大長度
用r遍歷陣列：
- 若遇到0，將zeroCount+1
- 若zeroCount>1，就持續移動l，直到zeroCount<2
- 更新res
遍歷完後，res即為所求

　　這樣的時間複雜度為O(N)，空間複雜度為O(1)。

from typing import List


class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        res = 0
        l, r = 0, 0
        zeroCount = 0

        while r < len(nums):
            if nums[r] == 0:
                zeroCount += 1

            while zeroCount > 1:
                if nums[l] == 0:
                    zeroCount -= 1
                l += 1

            res = max(res, r - l + 1)
            r += 1

        return res

😎496. Next Greater Element I

Description

　　陣列某元素x的下個更大元素（next greater element），是指其右邊比它更大的首個元素。現在給予兩個0-indexed的整數陣列nums1和nums2，前者為後者的子集合（subset）。

　　現在遍歷nums1，找出兩陣列同值時（兩陣列內的值皆相異）的nums2索引和其下個更大元素，沒有則回傳-1。請回傳等同nums1長度的答案陣列。

Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

Example 2:

Input: nums1 = [2,4], nums2 = [1,2,3,4]
Output: [3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 2 is underlined in nums2 = [1,2,3,4]. The next greater element is 3.
- 4 is underlined in nums2 = [1,2,3,4]. There is no next greater element, so the answer is -1.

Solutions

　　以下所用符號，m為nums1的元素量，n為nums2的元素量，n > m。

Approach #1: Brute Force

　　我們可以先直觀地處理。

　　這樣的時間複雜度為O(m*n)，空間複雜度為O(1)。

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        res = []
        for n in nums1:
            j = 0
            while nums2[j] != n:
                j += 1
            while j < len(nums2) and nums2[j] <= n:
                j += 1
            if j == len(nums2):
                res.append(-1)
            else:
                res.append(nums2[j])
        return res

⭐Approach #2: Using Stack

　　若先算出nums2各元素的下個更大元素，我們就能將時間複雜度降至O(n)：

用堆疊stack輔助找出nums2各元素的下個更大元素，雜湊表mp儲存
遍歷nums2
- 將元素存入stack
- 若當前元素>先前元素，則為先前元素的下個更大元素，將關係記錄到mp中
遍歷nums1，用陣列res儲存各元素的下個更大元素
回傳res，即為所求

　　這樣的時間與空間複雜度皆為O(n)。

from typing import List


class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # 輔助找出nums2中各元素的下個更大元素
        stack = []
        # 儲存每個元素的下個更大元素
        mp = {}

        for num in nums2:
            # 找到之前所存元素的下個更大元素
            while stack and num > stack[-1]:
                # 記錄元素的下個更大元素，並將其從堆疊中移除
                mp[stack.pop()] = num
            stack.append(num)

        # 此時堆疊內的元素皆沒有下個更大元素
        while stack:
            mp[stack.pop()] = -1

        # 使用nums1的元素順序，放入對應答案
        res = []
        for num in nums1:
            res.append(mp[num])

        return res

😐523. Continuous Subarray Sum

Description

　　給予一整數陣列nums和整數k，請判斷nums是否有好（good）的子陣列。好的特徵是：

長度≥2
子陣列的元素和是k的倍數（0也算）

Example 1:

Input: nums = [23,2,4,6,7], k = 6
Output: true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.

Example 2:

Input: nums = [23,2,6,4,7], k = 6
Output: true
Explanation: [23, 2, 6, 4, 7] is an continuous subarray of size 5 whose elements sum up to 42.
42 is a multiple of 6 because 42 = 7 * 6 and 7 is an integer.

Example 3:

Input: nums = [23,2,6,4,7], k = 13
Output: false

Solutions

⭐Approach #1: HashMap

　　此題需要的主要觀念是對餘數的了解：

使用雜湊表mp，記錄在索引元素當下總和（total）的餘數
遍歷陣列nums，若餘數值再次出現，代表這中間有子陣列的元素和可被k整除

　　這樣的時間複雜度為O(N)，空間複雜度為O(min(N, k))，N為元素數量。

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        # 如果0再次出現，那可確保即便是前兩個元素也滿足後面的判斷式
        mp = {0: -1}
        total = 0
        for i, j in enumerate(nums):
            total += j
            remainder = total % k
            # 若再度出現相同餘數，代表中間有個子陣列的和為k的倍數
            if remainder in mp:
                # 確認此子陣列相隔超過2
                if i - mp[remainder] >= 2:
                    return True
                else:
                    continue
            mp[remainder] = i
        return False

😐535. Encode and Decode TinyURL

Description

　　短網址服務（TinyURL）能將一個長網址（e.g. https://leetcode.com/problems/design-tinyurl）轉換成短網址（e.g.　http://tinyurl.com/4e9iAk），請設計一個類別來完成此功能。

Example 1:

Input: url = "https://leetcode.com/problems/design-tinyurl"
Output: "https://leetcode.com/problems/design-tinyurl"

Explanation:
Solution obj = new Solution();
string tiny = obj.encode(url); // returns the encoded tiny url.
string ans = obj.decode(tiny); // returns the original url after decoding it.

Solutions

⭐Approach #1 Using Simple Counter

　　轉換長網址為短網址的關鍵在於一對一映射，我們使用遞增數字來完成。

class Codec:
    def __init__(self):
        self.encodeMap = {}
        self.decodeMap = {}
        self.base = "http://tinyurl.com/"

    def encode(self, longUrl: str) -> str:
        if longUrl not in self.encodeMap:
            # 用遞增數字為編號
            shortUrl = self.base + str(len(self.encodeMap) + 1)
            self.encodeMap[longUrl] = shortUrl
            self.decodeMap[shortUrl] = longUrl
        return self.encodeMap[longUrl]

    def decode(self, shortUrl: str) -> str:
        return self.decodeMap[shortUrl]

😐554. Brick Wall

Description

　　在你面前有面n列矩形牆，我們以二維陣列wall表達裡面磚頭的寬度（高度皆相同），每列總寬度皆同。

　　請從頂到尾劃一條垂直線，請回傳可以劃過最少塊的磚頭數量（擦邊狀態不需計算）。

Example 1:

Input: wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
Output: 2

Example 2:

Input: wall = [[1],[1],[1]]
Output: 3

Solutions

Approach #1 HashMap

　　我們可用個雜湊表，記錄每個x座標所沒切到的磚頭數。遍歷完後就能知道哪個座標所切到的磚頭數最少。

　　這樣的時間複雜度為O(n)，空間複雜度為O(m)，n為牆內磚頭總數，m為牆寬。

from collections import defaultdict


class Solution:
    def leastBricks(self, wall):
        map = defaultdict(int)

        for bricks in wall:
            # 磚頭間隙的座標
            xCord = 0
            for i in range(len(bricks) - 1):
                xCord += bricks[i]
                map[xCord] += 1

        # 以每層都會切到來更新
        res = len(wall)
        for key in map:
            res = min(res, len(wall) - map[key])

        return res

😐560. Subarray Sum Equals K

Description

　　給予一個整數陣列nums和一個整數k，請回傳和為k的子陣列數量。

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2

Example 2:

Input: nums = [1,2,3], k = 3
Output: 2

Solutions

❌Approach #1: Brute Force

　　我們可以直觀找出所有子陣列後，判斷和是否為k。

　　這樣的時間複雜度為O(N³)，空間複雜度為O(1)。

class Solution:
    def subarraySum(self, nums, k):
        count = 0
        for start in range(len(nums)):
            for end in range(start + 1, len(nums) + 1):
                total = sum(nums[start:end])
                if total == k:
                    count += 1
        return count

❌Approach #2: Without Space

　　我們也可以遍歷並讓每個元素作為子陣列起點來判斷。

　　這樣的時間複雜度為O(N²)，空間複雜度為O(1)。

class Solution:
    def subarraySum(self, nums, k):
        count = 0
        for start in range(len(nums)):
            total = 0
            for end in range(start, len(nums)):
                total += nums[end]
                if total == k:
                    count += 1
        return count

⭐Approach #3: Using Hashmap

　　子陣列是一段位置連續的元素，若記錄每段和，就能在遍歷一趟後完成所求：

用count紀錄所求子陣列數量，total紀錄元素和，hashmap紀錄和值與出現次數
遍歷陣列nums：
- 更新total
- 若total - k已出現過（首次對到的為0，即total = k，後續對到的則會是k的倍數），則將出現次數加到count中
遍歷完時，count即為所求

　　這樣的時間複雜度為O(N)，空間複雜度為O(N)。

class Solution:
    def subarraySum(self, nums, k):
        count = 0
        total = 0
        hashmap = {0: 1}
        for i in range(len(nums)):
            total += nums[i]
            if total - k in hashmap:
                count += hashmap[total - k]
            hashmap[total] = hashmap.get(total, 0) + 1
        return count

🧰: LeetCode: Array & Hashing (2/3)

🤔

💡

😎303. Range Sum Query – Immutable

Description

Example 1:

Solutions

Approach #1: Brute Force

⭐Approach #2: Caching

😐304. Range Sum Query 2D -Immutable

Description

Example 1:

Solutions

❌Approach #1: Brute Force

⭐Approach #2: Caching Smarter

😐307. Range Sum Query – Mutable

Description

Example 1:

Solutions

❌Approach #1: Naive

⭐Approach #2: Segment Tree

😐347. Top K Frequent Elements

Description

Solutions

Approach #1 使用堆積（Heap）

⭐Approach #2 用陣列索引值分類出現次數不同的元素

😎392. Is Subsequence

Description

Example 1:

Example 2:

Solutions

⭐Approach #1: Two-Pointers

😐438. Find All Anagrams in a String

Description

Example 1:

Example 2:

Solutions

⭐Approach #1: Sliding Window

😎485. Max Consecutive Ones

Description

Example 1:

Example 2:

Solutions

⭐Approach #1: One pass

😎448. Find All Numbers Disappeared in an Array

Description

Example 1:

Example 2:

Solutions

Approach #1: Using Hash Map

⭐Approach #2: O(1) Space InPlace Modification Solution

😐487. Max Consecutive Ones II

Description

Example 1:

Example 2:

Solutions

⭐Approach #1: Sliding Window

😎496. Next Greater Element I

Description

Example 1:

Example 2:

Solutions

Approach #1: Brute Force

⭐Approach #2: Using Stack

😐523. Continuous Subarray Sum

Description

Example 1:

Example 2:

Example 3:

Solutions

⭐Approach #1: HashMap

😐535. Encode and Decode TinyURL

Description

Example 1:

Solutions

⭐Approach #1 Using Simple Counter

😐554. Brick Wall

Description

Example 1:

Example 2: