Leetcode模块训练3

给你一个整数数组 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

/*
前缀和
时间复杂度：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))
}

给定一个二维矩阵 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 方法

/*
方法一：一维前缀和
先把每一个行的前缀和都记录下来，当计算二维时遍历统计每一行的子数组总和
时间复杂度：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)
}

这里有 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

/*
方法：差分
差分其实是前缀和的概念，题目要求对区间[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))
}

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

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

示例 2：
输入：nums = [1]
输出：1

//动态规划
//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)
}

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

示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

//暴力解法
//时间复杂度：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)
}

给你一个下标从 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] 。

/*
二分查找
每次遍历数组固定左边的下标，然后在右边的下标中采用二分查找的方式寻找第二个下标
时间复杂度：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)
}

给你一个包含 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]
输出：[]

/*
排序+双指针
时间复杂度：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))
}

给定一个长度为 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

/*
对撞指针法
时间复杂度：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))
}

给你一个整数数组 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/

/*
暴力枚举法
时间复杂度：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))
}