day7 题目：53. 最大子数组和、152. 乘积最大子数组、41. 缺失的第一个正数
学习计划链接：冲刺春招 - 精选笔面试 66 题大通关
今日知识点：数组、动态规划、哈希，难度为简单、中等、困难
# 53. 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
# 思路
经典做法就是，每次如果加上去之后当前和 < 0 了，那么这个只会让后面的变小所以直接将 nowsum 置为 0。
# 代码
class Solution { | |
public: | |
int maxSubArray(vector<int>& nums) { | |
int ans = -100000; | |
int nowsum = 0; | |
int n = nums.size(); | |
for(int i = 0; i < n; ++i) { | |
nowsum += nums[i]; | |
if(nowsum > ans) ans = nowsum; | |
if(nowsum < 0) nowsum = 0; | |
} | |
return ans; | |
} | |
}; |
# 152. 乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32 - 位 整数。
子数组 是数组的连续子序列。
示例 1:
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
# 思路
当前位置如果是一个负数的话，那么我们希望以它前一个位置结尾的某个段的积也是个负数，这样就可以负负得正，并且我们希望这个积尽可能「负得更多」，即尽可能小。如果当前位置是一个正数的话，我们更希望以它前一个位置结尾的某个段的积也是个正数，并且希望它尽可能地大。
好，我觉得官方题解说的很清楚，主要就这一句话
# 代码
/** | |
* @param {number[]} nums | |
* @return {number} | |
*/ | |
var maxProduct = function(nums) { | |
let minp, maxp, ans; | |
minp = maxp = ans = nums[0]; | |
let n = nums.length; | |
for(let i = 1; i < n; ++i) { | |
let [tmax, tmin] = [maxp, minp]; | |
maxp = Math.max(tmax*nums[i], tmin*nums[i], nums[i]); | |
minp = Math.min(tmax*nums[i], tmin*nums[i], nums[i]); | |
ans = Math.max(ans, maxp) | |
} | |
return ans; | |
}; |
# 41. 缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0]
输出：3
示例 2：
输入：nums = [3,4,-1,1]
输出：2
提示：
- 1 <= nums.length <= 5 * 105
- -231 <= nums[i] <= 231 - 1
# 思路
一开始的思路，就是非常暴力的 hash 存，遇到不在的就直接返回... 这就很不困难题，也不满足题意（
/** | |
* @param {number[]} nums | |
* @return {number} | |
*/ | |
var firstMissingPositive = function(nums) { | |
let m = new Map(); | |
for(let i of nums) | |
m.set(i, 1); | |
let len = nums.length; | |
for(let i = 1; i <= 1000005; ++i) { | |
if(!m.has(i)) return i; | |
} | |
}; |
看完题解：哦～由于我们只在意 [1, N] 中的数，因此我们可以先对数组进行遍历，把不在 [1, N][1,N] 范围内的数修改成任意一个大于 N 的数（例如 N+1）。这样一来，数组中的所有数就都是正数了，因此我们就可以将「标记」表示为「负号」，这样一来，每次遇到的有可能是负数但是其绝对值就是原来的数，遍历完后，若数组中每一个数都为负数则答案为 N+1，否则就是第一个正数的位置。
# 代码
/** | |
* @param {number[]} nums | |
* @return {number} | |
*/ | |
var firstMissingPositive = function(nums) { | |
let n = nums.length; | |
for(let i = 0; i < n; ++i) { | |
if(nums[i] <= 0) | |
nums[i] = n+1; | |
} | |
for(let i = 0; i < n; ++i) { | |
let nowp = Math.abs(nums[i]); | |
if(nowp <= n) { | |
nums[nowp-1] = -Math.abs(nums[nowp-1]); | |
} | |
} | |
for(let i = 0; i < n; ++i) { | |
if(nums[i] > 0) | |
return i+1; | |
} | |
return n+1; | |
}; |
