總算來到我們寫題目的環節了，首先第一天我們來學習Array類型的題目吧！

Array技巧整理

Array類型的題目在我的經驗裡有幾個小技巧，大家可以參考看看。

• 1.String的問題通常都可以轉換成Array的問題。
• 2.如果可以排序，那或許會是一個好主意。
• 3.利用Two Pointer技巧解題。
• 4.計算「次數」，或是「有沒有出現」的基本上都可以用HashMap跟Set。

例題1-Two Sum

1. Brute Force: 看到這個題目的時候，我們最直接想到的就是，我用兩個迴圈，第一個迴圈指向我當前的數字，第二個迴圈去找看看有沒有我要的數字，這樣的時間複雜度是O(n^2)。
   

2. 我們來想看看我們實際上要做甚麼，假設現在我的target=9, num=2 那我就是要找7有沒有在這個陣列裡，「有沒有在」這個關鍵字出現了！我們就要想到Hash Map或是Set，依這個題目要求，因為我們還要回傳index所以用Hash Map，key是num, val是index。
   所以我可以先跑過一遍迴圈，把每個數字的位置記錄下來，第二次在用in去找我們要的數字，這樣時間複雜度就是O(2n)也就是O(n)拉！空間複雜度的話，因為我們需要HashMap去紀錄每一個元素出現的地方跟值，所以我們會再多耗費O(n)的空間去保存，空間複雜度就是O(n)囉。
   

ps. 因為題目說index不一定要照著順序，所以其實可以邊遍歷就邊紀錄然後邊看有沒有在HashMap裡面了，但是我覺得用這樣講解比較好懂，大家可以自行去看看別人的寫法喔。
ps2. and position[target-num] != index 如果沒有這個條件 nums = [3,2,4], target = 6 這個test case會有問題。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        
        position = {}
        
        for index, num in enumerate(nums):
            position[num] = index
        
        for index, num in enumerate(nums):
            if (target - num in position
                and position[target-num] != index):
                return [index, position[target - num]]

例題2-Two Sum II-Input Array Is Sorted

我們接著來看下一題類似的題目，這邊可以發現，他給的是一個已經排序好的Array，這樣有沒有其他的解法呢？答案是有的！我們先來想看看，排序後的Array有甚麼特性？我們可以發現，以任意index為例，右邊的數字都會比我大，左邊的數字都會比我小，所以我的所有數字可能都會在index[0]+index[1]到index[-2]+index[-1]之間(在python裡-1就是最後一個，-2就是倒數第二個)，那我就先把左指針指向index[0]右指針指向index[-1]，如果我兩個數字加起來太大，那就代表我右指針要往左移，想想看因為我都拿我「最大」的數字去加上「最小」都還是太大，那就是我要改變我的最大拉，反過來說，兩個數字加起來太小，那我的左指針就往左移，一直到找到答案後就完成了。

因為我們最多只會遍歷每個元素一次，所以時間複雜度是O(n)，另外我們不管input Array多大，始終只需要用到兩個pointer，所以空間複雜度是O(1)。

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        
        left, right = 0, len(numbers)-1
        
        while left < right:

            num_sum = (numbers[left] + numbers[right])
            
            if target == num_sum:
                return [left+1, right+1]
            elif target < num_sum:
                right-=1
            else:
                left+=1

例題3-Container With Most Water

1. Brute Force: 這題最直觀的想法也是利用兩個迴圈把所有可能的組合都算一遍，這樣的時間複雜度是O(n^2)。

2. 我們一樣來想看看有沒有其他作法，這邊我們會發現面積是「高」乘以「寬」，寬就是index的差，而「高」就會是由值最短的那一個決定的。這個告訴我們甚麼訊息呢？假設今天我在算這個的面積。
   

我們可以發現左邊的柱子比較矮，右邊比較高，如果我把右邊往內移，有可能算到比我現在還大的值嗎？很明顯是不可能的！因為往右邊的柱子往內移的話，我的柱子高度就算比現在高，我還是會被左邊的柱子限制住，但我的寬更小，所以面積一定更小。

如果右邊的柱子高度比現在低，面積一定又會在更小。所以更大的面積只有可能發生在，把左邊，也就是比較小的那一邊的柱子往內移的情況下發生。

這種情況我們就可以使用two pointer，如果左邊比較小，就把左邊往內移，右邊比較小，就把右邊往內移，然後每次做動都去計算我們的面積接著更新result值，這樣的時間複雜度就是O(n)囉。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        
        left, right = 0, len(height) - 1
        res = 0
        
        while left <= right:
            
            if height[left] > height[right]:
                res = max(res, height[right] * (right-left))
                right -= 1
            else:
                res = max(res, height[left] * (right-left))
                left += 1

        return res

例題4-Valid Anagram

最後我們來看一下這一題，這一題怎麼解呢？我不賣關子了，就是標準的利用HashMap來計算字母出現的次數，然後在比較就可以啦。

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        
        if len(s) != len(t):
            return False
        
        char_dict = {}
        
        for char in t:
            if char not in char_dict:
                char_dict[char] = 1
            else:
                char_dict[char] += 1
                
        for char in s:
            
            if char not in char_dict:
                return False
            
            elif char_dict[char] == 0:
                return False
    
            else:
                char_dict[char] -= 1
                
        return True