存在重复元素

给定一个整数数组，判断是否存在重复元素。如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false

  • 直接用map
1
2
3
4
5
6
7
8
9
10
11
12
func containsDuplicate(nums []int) bool {
    mp := make(map[int]bool)
    for _, n := range nums {
        _, ok := mp[n]
        if ok {
            return true
        }else {
            mp[n]=true
        }
    }
    return false
}

最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 func maxSubArray(nums []int) int {
    maxNum := -1000000
	sum := -1000000
	for _, n := range nums {
		if sum < 0  {
			sum = n
		}else {
			sum += n
		}
		if sum > maxNum {
			maxNum = sum
		}
	}
	if maxNum == -1000000 {
		return 0
	}else {
		return maxNum
	}
}

两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。

  • 直接暴力
1
2
3
4
5
6
7
8
9
10
11
12
13
func twoSum1(nums []int, target int) []int {
	var res []int = make([]int,2)
	for i:=0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			if nums[i] + nums[j] == target {
				res[0] = i
				res[1] = j
				return res
			}
		}
	}
	return res
}
  • 更简单的方式，复杂度小于平方
1
2
3
4
5
6
7
8
9
10
func twoSum(nums []int, target int) []int {
    var numsMap = make(map[int]int)
	for i, n := range nums{
		if k, ok := numsMap[target - n]; ok {
			return []int{k, i}
		}
		numsMap[nums[i]] = i
	}
	return nil
}

两个数组的交集 II

给定两个数组，编写一个函数来计算它们的交集。

  • 两个排序，简单遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 func intersect1(nums1 []int, nums2 []int) []int {
	sort.Ints(nums1)
	sort.Ints(nums2)
	res := make([]int, 0)
	for i, j := 0, 0; i < len(nums1) && j < len(nums2); {
		if nums1[i] > nums2[j] {
			j++
		}else if nums1[i] < nums2[j] {
			i++
		}else {
			res = append(res, nums1[i])
			i++
			j++
		}
	}
	return res
}
  • 如果 nums1 的大小比 nums2 小很多，哪种方法更优？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//使用哈希表,哈希表存的是数值与出现的次数
func intersect(nums1 []int, nums2 []int) []int {
	if len(nums1) > len(nums2){
		return intersect(nums2, nums1)
	}

	res := []int{}
	numsMap := make(map[int]int)
	for _, n := range nums1 {
		_, ok := numsMap[n]
		if ok {
			numsMap[n] += 1
		}else {
			numsMap[n] = 1
		}
	}

	for _, n := range nums2 {
		k, ok := numsMap[n]
		if ok && k > 0 {
			res = append(res, n)
			numsMap[n] = k-1
		}
	}

	return res
}

买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

  • 求取最大和最小值，然后相减看大小
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func maxNum(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func minNum(x, y int) int {
	if x > y {
		return y
	}
	return x
}

func maxProfit(prices []int) int {
	if len(prices) <= 1 {
		return 0
	}
	min := prices[0]
	max := 0
	for i := 1; i < len(prices); i++ {
		max = maxNum(max, prices[i]-min)
		min = minNum(min, prices[i])
	}
	return max
}

有效的数独

这里主要是二维数组操作

请你判断一个 9x9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

注意：一个有效的数独（部分已被填充）不一定是可解的。只需要根据以上规则，验证已经填入的数字是否有效即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
func isValidSudoku(board [][]byte) bool {
    for i := 0; i < 9; i++ {
		m1 := map[byte]bool{}
		m2 := map[byte]bool{}
		m3 := map[byte]bool{}
		for j := 0; j < 9; j ++ {
			//行
			if board[i][j] != '.' {
				if m1[board[i][j]] {
					return false
				}
				m1[board[i][j]] = true
			}
			//列
			if board[j][i] != '.' {
				if m2[board[j][i]] {
					return false
				}
				m2[board[j][i]] = true
			}
			//小格子
			row := (i%3)*3 + j%3
			col := (i/3)*3 + j/3
			if board[row][col] != '.' {
				if m3[board[row][col]] {
					return false
				}
				m3[board[row][col]] = true
			}
		}
	}
	
	return true
}