Link : https://leetcode.com/problems/find-the-duplicate-number/

Problem :
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

Thoughts :
1. 用collections.Counter來計算每個數字出現的次數。
2. 如果 count > 1，直接 return。

Solution :

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        count = collections.Counter(nums)
        for i,j in count.items():
            if j > 1:
                return i

time complexity, space complexity

Link : https://leetcode.com/problems/longest-consecutive-sequence/

Problem :
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Thoughts :
1. 先把 nums 放進去 set中，排除重複的數字。
2. 跑 nums迴圈，假設 nums-1 數字有在 set 中，那 nums 就不能當開頭。
3. 如果 nums-1沒有在 set 中，那就可以當開頭，計算值為1，如果 nums+1有在 set中，計算值+1，num+1。
4. 回傳最大的 curr值

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        # result
        res = 0
        # 轉成set存，拿掉重複的數字
        nums_set = set(nums)
        # go over the array = nums
        for num in nums:
            # 如果 nums-1 存在 nums_set中，num不能作為起始點，跳過
            if num-1 not in nums_set:
                # 沒有在nums_set中，就可以開始計算長度
                curr = 1
                # 假設 nums+1有在nums_set中
                while num+1 in nums_set:
                    # num +1，長度cur +1
                    num += 1
                    curr += 1
                # 檢查有沒有比之前的result還要大
                res = max(res,curr)
        return res

Link : https://leetcode.com/problems/increasing-triplet-subsequence/

Problem:
Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.

Thoughts：
1. 直接跑array內的值(nums[i] < nums[j] < nums[k])做比較，i<j<k這個照迴圈跑就可以達成。
2. first, second先設為 infinity，然後比較小的值取代掉 first, second
3. 假設 nums =[2,1,5,0,4,6]
num, first, second = [2, 2, inf]
num, first, second = [1, 1, inf]
num, first, second = [5, 1, 5]
num, first, second = [0, 0, 5]
num, first, second = [4, 0, 4]
num = 6, [0, 4, 6]

Solution:

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        first = float('inf')
        second = float('inf')
        for num in nums:
            if num <= first:
                first = num
            elif num <= second:
                second = num
            else:
                return True
        return False

time complexity = O(n)

Link :https://leetcode.com/problems/container-with-most-water/

Problem :
Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant the container.
找到最大長方形面積。使用兩個pointer來實作，計算每次的長方形面積大小，將比較矮的邊長往下一個位置移動(盡量保留較大的值)。

Thoughts:
1. 使用兩個指針(right, left)來檢查哪裡是max_area。
2. 每次都先計算出當下的area，放到max裡面進行比較。
3. 計算完後完後開始移動指針，將較小的值往中間靠近。

Solution:

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

Link : https://leetcode.com/problems/pascals-triangle-ii/

Problem :
Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

Thoughts :
1. 只 return 該行的結果。
2. 先計算該行會有幾個數字。
(Note : rowIndex從0開始)
3. 每一行的結果都是上一行的兩個數字、兩個數字加起來的。並且每一行的第一個數字都是1。
ex:
第二行為 0, 1, 1, 0
第三行為 0+1, 1+1, 0+1 = 1, 2, 1
(Note：從後面開始加，第四位跟第三位開始加，第三位跟第二位，第二位跟第一位)
如果從前面開始加會變成：
第二行為 0, 1, 1, 0
第三行為 0+1, 1+1, (1+1)+1 = 1, 2, 3 ->會出現問題，所以從後面開始加3. 4. return 結果。

Solution :

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        result = [1] + [0]*rowIndex
        for i in range(rowIndex):
            result[0] = 1
            for j in range(i+1,0,-1):
                result[j] = result[j] + result[j-1]
        return result

time complexity = O(n²)？, space complexity

Link : https://leetcode.com/problems/pascals-triangle/

Problem :
Given an integer numRows, return the first numRows of Pascal's triangle.