1. 统计(优美子数组)(1048)
代码语言：javascript
复制给你一个整数数组 nums 和一个整数 k。如果某个连续子数组中恰好有 k 个奇数数字，
我们就认为这个子数组是「优美子数组」。
请返回这个数组中 「优美子数组」 的数目。
示例 1：
输入：nums = [1,1,2,1,1], k = 3
输出：2
解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。
示例 2：
输入：nums = [2,4,6], k = 1
输出：0
解释：数列中不包含任何奇数，所以不存在优美子数组。
示例 3：
输入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出：16
提示：
1 <= nums.length <= 50000
1 <= nums[i] <= 10^5
1 <= k <= nums.length
代码语言：javascript
复制/*
前缀和
时间复杂度：O(n)
空间复杂度：O(n)
*/
func numberOfSubarrays(nums []int, k int) int {
// cnt存放[优美子数组]出现的次数
// odd记录累计奇数的个数
// ans存放最终结果符合条件的[优美子数组]
cnt, odd, ans := make([]int, len(nums) 1), 0, 0
cnt[0] = 1
for _, v := range nums {
// 奇数&1为1，偶数&1为0
odd = v & 1
if odd-k >= 0 {
ans = cnt[odd-k]
}
cnt[odd] = 1
}
return ans
}
func main() {
nums := []int{2, 2, 2, 1, 2, 2, 1, 2, 2, 2}
k := 2
fmt.Println(numberOfSubarrays(nums, k))
}
2. 二维区域和检索(矩阵不可变)(304)
代码语言：javascript
复制给定一个二维矩阵 matrix，以下类型的多个请求：
计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。
实现 NumMatrix 类：
NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素 总和 。
示例1：
输入:
["NumMatrix","sumRegion","sumRegion","sumRegion"]
[[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
输出:
[null, 8, 11, 12]
解释:
NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)
提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
-105 <= matrix[i][j] <= 105
0 <= row1 <= row2 < m
0 <= col1 <= col2 < n
最多调用 104 次 sumRegion 方法
代码语言：javascript
复制/*
方法一：一维前缀和
先把每一个行的前缀和都记录下来，当计算二维时遍历统计每一行的子数组总和
时间复杂度：O(mn)
空间复杂度：O(mn)
*/
type NumMatrix struct {
nums [][]int
}
func Constructor(matrix [][]int) NumMatrix {
sums := make([][]int, len(matrix))
for i, row := range matrix {
sums[i] = make([]int, len(row) 1)
for j, v := range row {
sums[i][j 1] = sums[i][j] v
}
}
return NumMatrix{nums: sums}
}
func (m *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
var sum int
for i := row1; i <= row2; i {
sum = m.nums[i][col2 1] - m.nums[i][col1]
}
return sum
}
/*
方法二：二维前缀和
先把二维的前缀和都记录下来，即左上角的矩形总和，当计算二维时用右下角总和减去左上角的总和
和上面一维前缀和相比，少了一次对行的遍历
时间复杂度：O(mn)
空间复杂度：O(mn)
*/
func Constructor(matrix [][]int) NumMatrix {
m, n := len(matrix), len(matrix[0])
sums := make([][]int, m 1)
sums[0] = make([]int, n 1)
for i, row := range matrix {
sums[i 1] = make([]int, n 1)
for j, v := range row {
sums[i 1][j 1] = sums[i 1][j] v sums[i][j 1] - sums[i][j]
}
}
return NumMatrix{nums: sums}
}
func (m *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
return m.nums[row2 1][col2 1] - m.nums[row2 1][col1] - m.nums[row1][col2 1] m.nums[row1][col1]
}
func main() {
matrix := [][]int{
{3, 0, 1, 4, 2},
{5, 6, 3, 2, 1},
{1, 2, 0, 1, 5},
{4, 1, 0, 1, 7},
{1, 0, 3, 0, 5},
}
obj := Constructor(matrix)
param_1 := obj.SumRegion(2, 1, 4, 3)
param_2 := obj.SumRegion(1, 1, 2, 2)
param_3 := obj.SumRegion(1, 2, 2, 4)
fmt.Println(param_1)
fmt.Println(param_2)
fmt.Println(param_3)
}
3. 航班预订统计(1109)
代码语言：javascript
复制这里有 n 个航班，它们分别从 1 到 n 进行编号。
有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi]
意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。
请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。
示例 1：
输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]
解释：
航班编号 1 2 3 4 5
预订记录 1 ： 10 10
预订记录 2 ： 20 20
预订记录 3 ： 25 25 25 25
总座位数： 10 55 45 25 25
因此，answer = [10,55,45,25,25]
示例 2：
输入：bookings = [[1,2,10],[2,2,15]], n = 2
输出：[10,25]
解释：
航班编号 1 2
预订记录 1 ： 10 10
预订记录 2 ： 15
总座位数： 10 25
因此，answer = [10,25]
提示：
1 <= n <= 2 * 10^4
1 <= bookings.length <= 2 * 104
bookings[i].length == 3
1 <= firsti <= lasti <= n
1 <= seatsi <= 10^4
代码语言：javascript
复制/*
方法：差分
差分其实是前缀和的概念，题目要求对区间[l,r]内的值增量叠加，暴力的做法是直接遍历，
但是这样会增加n的复杂度，差分的方法就是对 >=l 的值全部增加增量v，因为只需要l-r之间，
所有 r 右边的增量是多余的，所以还需要对 >r 的值减去刚才加上的增量，最终就只是对[l,r]之间
进行增量叠加，整个过程只需对l个r进行上述两个操作，相比于遍历整个 r-l 的范围来说，降了一个量级的时间复杂度。
时间复杂度：O(m n)
空间复杂度：O(1)
*/
func corpFlightBookings(bookings [][]int, n int) []int {
sums := make([]int, n)
// 因为题目传进来的值是从1开始的，而我们数组是从0开始的，
// 所以要注意开闭区间
for _, v := range bookings {
sums[v[0]-1] = v[2] //对 v[0]-1 右侧(闭区间)全部增加
if v[1] < n { //如果是最后一个下标，不要进行减少，不然会数组越界
sums[v[1]] -= v[2] //对 v[1] 右侧(开区间)全部减少
}
}
for i := 1; i < n; i {
sums[i] = sums[i-1] //采用前缀和思想，直接相加
}
return sums
}
func main() {
bookings := [][]int{
{1, 2, 10},
{2, 3, 20},
{2, 5, 25},
}
n := 5
fmt.Println(corpFlightBookings(bookings, n))
}
4. 最大子数组和(53)
代码语言：javascript
复制给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6
示例 2：
输入：nums = [1]
输出：1
代码语言：javascript
复制//动态规划
//f(i)表示以第i个数结尾的最大连续和
//f(i)=max{f(i−1) nums[i],nums[i]}
//时间复杂度：O(n)，其中 n 为 nums 数组的长度，只需要遍历一遍数组即可求得答案
//空间复杂度：O(1)，只需要常数空间存放若干变量
func maxSubArray(nums []int) int {
max := nums[0]
for i := 1; i < len(nums); i {
/*
凡是会让总数变小的值，即<0的值，一律丢弃，
这里也可以写成：
if nums[i-1] > 0 {
nums[i] = nums[i-1]
}
*/
if nums[i-1] nums[i] > nums[i] {
nums[i] = nums[i-1]
}
if max < nums[i] {
max = nums[i]
}
}
return max
}
/*
前缀和解法
时间复杂度：O(n)
空间复杂度：O(1)
*/
func maxSubArray2(nums []int) int {
//记录最大子数组和，最小子数组和，当前前缀和
maxSum, minSum, sum := nums[0], 0, 0
for _, v := range nums {
sum = v
maxSum = max(maxSum, sum-minSum)
minSum = min(minSum, sum)
}
return maxSum
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
func min(x, y int) int {
if x > y {
return y
}
return x
}
func main() {
nums := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}
result1 := maxSubArray(nums)
fmt.Println(result1)
nums = []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}
result2 := maxSubArray2(nums)
fmt.Println(result2)
}
5. 两数之和(无序数组)(1)
代码语言：javascript
复制给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出
和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] nums[1] == 9 ，返回 [0, 1] 。
代码语言：javascript
复制//暴力解法
//时间复杂度：O(N²)
//空间复杂度：O(1)
func twoSum1(nums []int, target int) []int {
for i, v := range nums{
for j := i 1; j < len(nums); j {
sum := v nums[j]
if sum == target {
return []int{i, j}
}
}
}
return nil
}
//查找表法
//用map记录已经遍历过的数值和下标
//空间换时间
//时间复杂度：O(N)
//空间复杂度：O(N)
func twoSum2(nums []int, target int) []int {
//mapTemp := map[int]int{}
mapTemp := make(map[int]int, len(nums)) //初始化一定内存，内存消耗更少
for i, v := range nums {
if j, ok := mapTemp[target-v]; ok {
return []int{j, i}
}
mapTemp[v] = i
}
return nil
}
func main() {
nums := []int{2, 7, 11, 15}
target := 9
result1 := twoSum1(nums, target)
fmt.Println(result1)
result2 := twoSum2(nums, target)
fmt.Println(result2)
}
6. 两数之和2(有序数组)(167)
代码语言：javascript
复制给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列，
请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是
numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
和上一个两数之和题目是一样的，只是这个输入的数组是有顺序的，既然有顺序，那么可以得到时间空间复杂度更低的解法
示例 1：
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2：
输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3：
输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
代码语言：javascript
复制/*
二分查找
每次遍历数组固定左边的下标，然后在右边的下标中采用二分查找的方式寻找第二个下标
时间复杂度：O(nlog(n))
空间复杂度：O(1)
*/
func twoSum3(numbers []int, target int) []int {
for i, v := range numbers {
l, r := i 1, len(numbers)-1
for l <= r {
m := (l r) / 2
if v numbers[m] == target {
return []int{i 1, m 1}
} else if v numbers[m] < target {
l = m 1
} else {
r = m - 1
}
}
}
return []int{-1, -1}
}
/*
双指针
时间复杂度：O(n)
空间复杂度：O(1)
*/
func twoSum4(numbers []int, target int) []int {
l, r := 0, len(numbers)-1
for l < r {
sum := numbers[l] numbers[r]
if sum == target {
return []int{l 1, r 1}
} else if sum < target {
l
} else {
r--
}
}
return []int{-1, -1}
}
func main() {
nums := []int{2, 7, 11, 15}
target := 9
result3 := twoSum3(nums, target)
fmt.Println(result3)
nums = []int{2, 7, 11, 15}
result4 := twoSum4(nums, target)
fmt.Println(result4)
}
7. 三数之和(5)
代码语言：javascript
复制给你一个包含 n 个整数的数组nums，判断nums中是否存在三个元素 a，b，c ，
使得a b c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = []
输出：[]
示例 3：
输入：nums = [0]
输出：[]
代码语言：javascript
复制/*
排序 双指针
时间复杂度：O(n²)
空间复杂度：O(log(n))
*/
func threeSum(nums []int) [][]int {
n := len(nums)
sort.Ints(nums)
ans := make([][]int, 0)
// 枚举 a
for first := 0; first < n; first {
// 需要和上一次枚举的数不相同
if first > 0 && nums[first] == nums[first-1] {
continue
}
// c 对应的指针初始指向数组的最右端
third := n - 1
target := -1 * nums[first]
// 枚举 b
for second := first 1; second < n; second {
// 需要和上一次枚举的数不相同
if second > first 1 && nums[second] == nums[second-1] {
continue
}
// 需要保证 b 的指针在 c 的指针的左侧
for second < third && nums[second] nums[third] > target {
third--
}
// 如果指针重合，随着 b 后续的增加
// 就不会有满足 a b c=0 并且 b<c 的 c 了，可以退出循环
if second == third {
break
}
if nums[second] nums[third] == target {
ans = append(ans, []int{nums[first], nums[second], nums[third]})
}
}
}
return ans
}
func main() {
data := []int{-1, 0, 1, 2, -1, -4}
fmt.Println(threeSum(data))
}
8. 盛最多水的容器(8)
代码语言：javascript
复制给定一个长度为 n 的整数数组height。有n条垂线，第 i 条线的两个端点是(i, 0)和(i, height[i])。
找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为49。
示例 2：
输入：height = [1,1]
输出：1
代码语言：javascript
复制/*
对撞指针法
时间复杂度：O(n)
空间复杂度：O(1)
*/
func maxArea(height []int) int {
first, second := 0, len(height)-1
area := 0
h := 0
for first < second {
tempArea := 0
width := second - first
if height[first] < height[second] {
h = height[first]
first
} else {
h = height[second]
second--
}
tempArea = width * h
if tempArea > area {
area = tempArea
}
}
return area
}
func main() {
data := []int{1, 8, 6, 2, 5, 4, 8, 3, 7}
fmt.Println(maxArea(data))
}
9. 和为k的子数组(560)
代码语言：javascript
复制给你一个整数数组 nums 和一个整数k ，请你统计并返回 该数组中和为k的子数组的个数。
示例 1：
输入：nums = [1,1,1], k = 2
输出：2
示例 2：
输入：nums = [1,2,3], k = 3
输出：2
解法：https://leetcode.cn/problems/subarray-sum-equals-k/solution/he-wei-kde-zi-shu-zu-by-leetcode-solution/
代码语言：javascript
复制/*
暴力枚举法
时间复杂度：O(n^2)
空间复杂度：O(1)
*/
func subarraySum(nums []int, k int) int {
var ans int
for i := 0; i < len(nums); i {
sum := 0
j := i
for j < len(nums) {
sum = nums[j]
j
if sum == k {
ans
}
}
}
return ans
}
/*
前缀和 哈希表优化
时间复杂度：O(n)
空间复杂度：O(n)
*/
func subarraySum2(nums []int, k int) int {
count, pre := 0, 0
m := map[int]int{0: 1}
for i := 0; i < len(nums); i {
pre = nums[i]
if _, ok := m[pre-k]; ok {
count = m[pre-k]
}
m[pre]
}
return count
}
func main() {
nums := []int{1, 1, 1}
fmt.Println(subarraySum(nums, 2))
fmt.Println(subarraySum2(nums, 2))
}
