# NSum系列

## 1. 2Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

```Given nums = [2, 7, 11, 15], target = 9,

Because nums + nums = 2 + 7 = 9,
return [0, 1].```

Solution

1. 一边Dict

2. 排序，双指针，Onlogn

## 15. 3Sum

3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

```Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]```

## 18. 4Sum

Given an array `nums` of n integers and an integer `target`, are there elements a, b, c, and d in `nums` such that a + b + c + d = `target`? Find all unique quadruplets in the array which gives the sum of `target`.

Note:

The solution set must not contain duplicate quadruplets.

Example:

```Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
[-1,  0, 0, 1],
[-2, -1, 1, 2],
[-2,  0, 0, 2]
]```

Solution

# 股票系列

```// 第i天的没有股票的状态 = Max(前一天就没有，前一天有但今天卖出了)
profit[i] = Math.max(profit[i - 1], profit[i - 1] + prices[i]);
// 第i天的有股票的状态 = Max(前一天就有了，前一天没有今天买了)
profit[i] = Math.max(profit[i - 1], profit[i - 1] - prices[i]);```

## 121. 买卖股票的最佳时机

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

```Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.```

Example 2:

```Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.```

Solution

```class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices: return 0

dp = *len(prices)
min_v = prices

for i in range(1, len(prices)):
min_v = min(min_v, prices[i])
dp[i] = prices[i] - min_v

return max(dp)```

## 122. 买卖股票的最佳时机 II

Say you have an array `prices` for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

```Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.```

Example 2:

```Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
engaging multiple transactions at the same time. You must sell before buying again.```

Solution

`ab`

## 123. 买卖股票的最佳时机 III

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

```Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.```

Example 2:

```Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
engaging multiple transactions at the same time. You must sell before buying again.```

Solution

dp[i][s]，i为天数，s为状态

`ab`

## 188. 买卖股票的最佳时机 IV

Say you have an array for which the i-th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Example 1:

```Input: [2,4,1], k = 2
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.```

Example 2:

```Input: [3,2,6,5,0,3], k = 2
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.```

Solution

dp[i][s]，i为天数，s为状态

`ab`

0 条评论

• ### 狗家算法面试高频题汇总

Google 面试题 | Data Stream Median - Python版

• ### [剑指offer][Java]旋转数组的最小数字

链接：https://www.nowcoder.com/questionTerminal/9f3231a991af4f55b95579b44b7a01ba ...

• ### Ubuntu 16.04 Install OpenCV

---- 安装opencv有很多种方式，我列出了两种方式。并针对第二种方式进行了详细的安装解释。 从Ubuntu源安装opencv sudo apt-get i...

• ### 用户管理下

第1章 批量添加3个用户stu01-stu03,设置密码为123456. 1.1 预备知识 前的产生的命令通过管道后可以交给bash运行 [root@znix ...

• ### 深度学习让人脸识别准确率不断提升

人脸识别、图像分类、语音识别是最早的深度学习取得突破的主要几个技术方向。在2014年前后，多家技术公司纷纷宣布其利用深度学习在LFW上取得的最新成果，此为深...

• ### CSS 侧边栏在小屏设备中进行隐藏

侧边栏的作用应该就不用多说了吧，能够很方便我们回到网页的指定位置，在大屏设备中，侧边栏往往是悬浮于屏幕右侧，很方便用户的使用，但在小屏设备中，屏幕空间有限，所以...

• ### 学界 | 我们还缺多少基础理论，才能在高中开设深度学习课程？

AI 科技评论按：这篇文章来自资深机器学习专家、NIPS 2017 「时间检验奖」( Test of Time Award ) 获得者 Ali Rahimi。上...

### 活动推荐 