首先是 1. Two Sum (easy)
https://leetcode.com/problems/two-sum/

題目會給予一個無序的整數串列nums，並且給一個正整數target；他想要從nums裡面找出兩個數字(n1,n2)加起來可以變成target。輸出這兩個數字的索引值，只有唯一解。

想法1：超級暴力解

1. 準備一個變數儲存答案
2. 利用 for 讀取整個串列，並用target減掉n1，得到n2
3. 檢查n2是否在這個串列裡面，以及是否跟n1在同個位置(同個位置不算數)
4. 因未必有答案，所以找到後馬上就可以return

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        ans = []
        for i in range(len(nums)):
            n2 = target - nums[i]
            if n2 in nums and nums.index(n2) != i:
                ans.append(nums.index(n2))
                ans.append(i)
                return ans

這樣的寫法乍看之下是對的，實際上也是對的，但老實說跑起來超級慢，時間複雜度直接被.index()拖垮。
因此我稍微換了一下寫法，改成如下：

1. 利用dict儲存答案，key存n2，value存n1
2. 檢查n1是否已經被當成key了，是的話return n1索引值跟n2索引值

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        ans = {}
        for i in range(len(nums)):
            n = target - nums[i]
            if nums[i] in ans:
                return [nums.index(ans[nums[i]]),i]
            ans[n] = nums[i]

以上這樣就少使用了.index()，時間複雜度應該是從O(n^2)變成O(n)

接下來是 28. Find the Index of the First Occurrence in a String (medium)
https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/

會有兩段字串 haystack 跟 needle ，要查找 needle 在 haystack第一次出現的位置的索引值，若沒出現就return -1。
感覺這道題目對於C++很不友善，對於Python而言可以直接call str 的 methond 解決。

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:#find
        return haystack.find(needle)
        
    def strStr(self, haystack: str, needle: str) -> int:#index
        if needle in haystack:
            return haystack.index(needle)
        return -1

這題對於Python而言應該沒什麼好修正的姑且就這樣吧

接下來是 33. Search in Rotated Sorted Array (medium)

題目會給予一個絕對升序排列的整數串列nums，但中間有部分的順序會進行所謂的rotated
像是[0,1,2,3,4,5,6,7] -> [4,5,6,7,1,2,3]，但具體位置在哪不會告訴你
(不知道為啥看到時會想到古老一個叫做大金剛的遊戲ww)
圖形上的感覺像是這樣吧

老實說Python用久了看到這種題目真的很想偷懶，直接這樣寫就好了。

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if target in nums:
            return nums.index(target)
        return -1

但如果要這樣寫乾脆不要刷題好了，所以我還是回歸題目的本意，乖乖用Binary Search解決
當題目題到是有序串列時，大概就知道這題要用Binary Search只是看要怎麼改而已。
主要是說，他有把部分內容進行rotate，但這其實不會影響運行，只需要注意nums[mid]有沒有跟原本一樣比nums[l]大，若沒有的話代表該區域有遭受到rotate，此時裡面的比較方式就要進行變動。
想法：

1. 寫好Binary Search基本款
2. 確認nums[mid]的位置是否正常
3. 若發現該區域經過rotate，則r,l的變化要剛好相反過來。

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums)-1
        while l <= r:
            mid = (l+r)//2
            if nums[mid] == target:
                return mid
            elif nums[l] <= nums[mid]:#正常狀況
                if target >= nums[l] and target < nums[mid]:
                    r = mid - 1
                else:
                    l = mid + 1
            else:#不正常
                if target > nums[mid] and target <= nums[r]:
                    l = mid + 1
                else:
                    r = mid - 1          
        return -1

以上就是今天的練習，感謝觀看~