建什么网站比较好,建自己网址的免费网页,网页设计一单多少钱,龙采做网站要多少钱今天#xff0c;带来数组相关算法的讲解。文中不足错漏之处望请斧正#xff01;
理论基础点这里 有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums#xff0c;返回 每个数字的平方 组成的新数组#xff0c;要求也按 非递减顺序 排序。
示例 1#xff1a;
输…今天带来数组相关算法的讲解。文中不足错漏之处望请斧正
理论基础点这里 有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums返回 每个数字的平方 组成的新数组要求也按 非递减顺序 排序。
示例 1
输入nums [-4,-1,0,3,10] 输出[0,1,9,16,100] 解释平方后数组变为 [16,1,0,9,100] 排序后数组变为 [0,1,9,16,100] 示例 2
输入nums [-7,-3,2,3,11] 输出[4,9,9,49,121]
提示
1 nums.length 104 -104 nums[i] 104 nums 已按 非递减顺序 排序
进阶
请你设计时间复杂度为 O(n) 的算法解决本问题
1. 思路
只有正数时平方的大小就是从头到尾即由小到大。 那顺序遍历升序数组作平方就能得到升序结果。
但有负数时该怎么办最小的平方应该是从两端趋向中间的最接近0的那个值。
从这个值往两边走谁的平方大谁就先插入结果集。题目要求升序那我们就从结果集的尾部到结果集的头部放入结果。
要“往两边走”我们用双指针从两边遍历就好啦谁大谁先插入结果数组。
2. 参考代码
class Solution {
public:// 找0, 双指针从两头向中间找, 平方和大的插入结果集的后面vectorint sortedSquares(vectorint nums) {vectorint result(nums.size());int left 0;int right nums.size() - 1;int insertIndex result.size() - 1;while (left right) { // leftrighrt时, nums[left]的平方和也要插入结果集long long squre1 pow(nums[left], 2);long long squre2 pow(nums[right], 2);if (squre1 squre2) {result[insertIndex--] squre1;left;} else {result[insertIndex--] squre2;--right;}}return result;}
};长度最小的子数组
1. 思路
理解题意
分析如何满足需求
1.1 暴力遍历
两层for一个指针确定当前想遍历的区间的起始位置另一个指针遍历来确定终止位置把所有可能的区间都遍历一遍一旦区间和大于target就对比并取最小的长度。
参考代码如下
class Solution {
public:int minSubArrayLen(int s, vectorint nums) {int minLen INT_MAX;int sum 0; // 子序列的数值之和int subLength 0; // 子序列的长度for (int i 0; i nums.size(); i) { // 设置子序列起点为isum 0;for (int j i; j nums.size(); j) { // 设置子序列终止位置为jsum nums[j];if (sum s) { // 一旦发现子序列和超过了s更新resultsubLength j - i 1; // 取子序列的长度result result subLength ? result : subLength;break; // 因为我们是找符合条件最短的子序列所以一旦符合条件就break不要再累加元素了}}}return result INT_MAX ? 0 : result;}
};
1.2 滑动窗口
暴力的方法比较死板直接把所有可能得区间都遍历一遍。每一次都是静态确认好一个区间 [i, j] 再累加求结果有没有办法更灵活地确认这个连续子数组地区间呢有的。
我们可以维护一个连续子数组的区间右边的指针固定走左边的指针能跟就跟保证长度最小——滑动窗口。
什么是滑动窗口其实是双指针的一种应用两个指针动态移动维护一个区间像滑动的窗口一样。
滑动窗口在本题中怎么用呢 为什么是end固定往后走begin根据策略走
首先end必须把整个数组遍历一遍其次begin作为起始位置不一定需要固定走如果区间和不大于等于target走了有什么意义呢。
end遍历给定数组nums当区间和大于target的时候就得到了当前最小的连续子序列但不是最终的。所以在end往后移动的时候begin也要根据一定策略追赶end保证得到最终的最小连续子序列。
begin到底是怎样移动的呢
如果当前区间是连续子数组begin就要移动如果当前区间不是连续子数组那么begin就不能移动
这样子移动每次begin移动完[begin, end]的和都会小于target不再是连续子数组但这不影响因为在它最后还是连续子数组的时候我们已经用minLen记录了它的长度。这样走下去就能获取到最短的长度。
2. 参考代码
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int begin 0; // [begin, end] 就是期望的最短子数组区间int end 0;int curLen 0;int minLen INT_MAX;long long sum 0;while (end nums.size()) {sum nums[end];while (sum target) { // 已经是子数组, 开始缩减长度curLen end - begin 1;minLen min(curLen, minLen);sum - nums[begin]; // 缩减长度}end;}return minLen INT_MAX ? 0 : minLen;}
};今天的分享就到这里了感谢您能看到这里。
这里是培根的blog期待与你共同进步
