leetcode

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/ pointer を2つ使う。 left が right より低い時点で売る可能性あり。 max_profit に最大の profit を格納。 right の pointer は右に移動し続け left の　pointer は prices[l] が prices[r] より大きい際に、 left の pointer を right の pointer の位置に移動する。 Time complexity: O(n) Mem complexity: O(1) class Solution(object): def maxProfit(self, prices): """ :type prices: List[int] :rtype: int """ l, r = 0, 1 max_profit = 0 while r < len(prices): if prices[l] < prices[r]: profit = prices[r] - prices[l] max_profit = max(max_profit, profit) else: l = r r += 1 return max_profit

https://leetcode.com/problems/two-sum/ | 2 | 7 | 11 | 15 | 　↑　↑ 全てのコンビネーションを確認しようと Brute Force で問題を解こうとすると ループの中でループをするのでo(n^2)となる。 | 2 | 7 | 11 | 15 | そのため HashMapを使う必要がある。 ループして array の中を確認する際に、 HashMap に val と key を持たせる。 ループ時に target - val の値が HashMap にあれば、 合計の値を持つ index が return できる。 | 2 | 7 | 11 | 15 | ↑ | HashMap | | val : index | | 2 : 1 | | HashMap | | val : index | | 2 : 1 | | 7 : 2 |← | 11 : 3 | | 15 : 4 | target は 9 なので val 7 を確認時に HashMap にすでに 2 が入っているので この時点で return できる。...