# leetcode:287. Find the Duplicate Number

#### 找這個list中哪個字元重複
ex.

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

## algo
把整個list掃過一遍,
若該元素不在list裡就把它放到set裡
若該元素已在list,則該元素就是重複值,回傳即可

time complexity:O(n)
space complexity:O(n)

## code

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        ans=set()
        for i in range(len(nums)):
            if nums[i] not in ans:
                ans.add(nums[i])
            else:
                return nums[i]

## note:
蠻酷的,用list就會超出時間,但是set就不會,應該是set的操作複雜度低一點,（原本是ans=[]去做結果

靠邀,結果詳解自己用 nums.sort()阿不是說好without modifying the array nums的嗎？

# leetcode:11. Container With Most Water
#### 給一個array,裡面有數個柱子,選定其中兩根作為邊界形成1容器(底乘高),看哪一個選擇會最大。

ex

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented 
by array [1,8,6,2,5,4,8,3,7]. In this case, 
the max area of water (blue section) the container can contain is 49.

## algo1
brute force：
直接寫兩層for loop把每個狀況算出來找max

time complexity:O(n^2^)
space conplexity:O(1)

## code1

class Solution:
    def maxArea(self, height: List[int]) -> int:
        naive_solution
        ans=0
        for i in range(len(height)):
            for j in range(len(height)-1-i):
                ans=max(ans,min(height[i],height[j+i+1])*((j+i+1)-i))
        return ans

## algo2
greedy:
從最大寬度開始減少，
而每輪計算左右柱子哪一個比較低，比較低的往下走一格。

面積的計算是由長乘寬得出來的，而在寬不斷減少的狀況下，
只能用找到更高的柱子來使面積更大。

## code2

class Solution:
    def maxArea(self, height: List[int]) -> int:
        ans=0
        l=0
        r=len(height)-1
        while l<r:
            ans=max(ans,(r-l)*min(height[l],height[r]))
            if height[l]<height[r]:
                l+=1
            else:
                r-=1
        return ans

## note
但是其實我原本是用比較下一個位子(左＋1,右-1)看哪一個柱子比較高來挑選下一個。
而該algo是以(左,右)看哪一個比較低，低的往下走來找。
因為高度的選擇是取決於比較低的那根，因此要調整也是由比較低的改變，若找我原本的方法繼續往下做，就算換了一根比較高的，仍然回被低的那根bound住。