1

 1 package main
 2
 3import "fmt"
 4
 5func main() {
 6	fmt.Println(twoSum([]int{2, 7, 11, 15}, 9))
 7}
 8
 9func twoSum(nums []int, target int) []int {
10
11	maps := make(map[int]int)
12
13	for i, value := range nums {
14		mid := target - value
15
16		res, ok := maps[mid]
17		if ok {
18			return []int{res, i}
19		} else {
20			maps[value] = i
21		}
22	}
23	return []int{}
24}

120. 三角形最小路径和

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1：

1输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
2输出：11
3解释：如下面简图所示：
4  2
5 3 4
66 5 7
74 1 8 3
8自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

示例 2：

1输入：triangle = [[-10]]
2输出：-10

提示：

11 <= triangle.length <= 200
2triangle[0].length == 1
3triangle[i].length == triangle[i - 1].length + 1
4-104 <= triangle[i][j] <= 104

进阶：

你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？

方法一：动态规划

自底向上递推

状态定义： 当前位置到叶子节点的最小值 DP[i.j]

状态转移方程： DP[i,j] = min(DP[i+1,j], DP[i+1,j+1])+Triangle[i,j] ​

 1func minimumTotal(triangle [][]int) int {
 2
 3	// checkout input value
 4	if len(triangle) == 0 {
 5		return 0
 6	}
 7	if len(triangle) == 1 {
 8		return triangle[0][0]
 9	}
10	//  algorithm
11	raw := len(triangle)
12	status := make([][]int, raw+1)
13	status[raw] = make([]int, raw+1)
14	for i := raw; i > 0; i-- {
15		status[i-1] = make([]int, i)
16		for j := 0; j < i; j++ {
17			status[i-1][j] = getMin(status[i][j], status[i][j+1]) + triangle[i-1][j]
18		}
19	}
20	return status[0][0]
21}
22
23func getMin(a, b int) int {
24	if a > b {
25		return b
26	}
27	return a
28}
29
30func TestSolution(t *testing.T) {
31	println(minimumTotal([][]int{
32		{2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3},
33	}))
34}

上述解法的时间复杂度为O(mn), 空间复杂度为O(mn),nm为行列数

空间复杂度可优化，状态只需保存前一行的状态即可，优化后代码如下

 1func minimumTotal(triangle [][]int) int {
 2	//  algorithm
 3	raw := len(triangle)
 4	status := make([]int, raw+1)
 5	for i := raw; i > 0; i-- {
 6		for j := 0; j < i; j++ {
 7			status[j] = getMin(status[j], status[j+1]) + triangle[i-1][j]
 8		}
 9	}
10	return status[0]
11}