aspx网站配置服务器,四维码制作网站,天津专业网站设计报价,cpm广告联盟平台系列文章
本人系列文章-CSDN博客https://blog.csdn.net/handsomethefirst/article/details/138226266?spm1001.2014.3001.5502 1.数组基本知识点
1.1概念
数组就是一个集合。数组会用一些名为索引的数字来标识每项数据在数组中的位置#xff0c;且在大多数编程语言中…系列文章
本人系列文章-CSDN博客https://blog.csdn.net/handsomethefirst/article/details/138226266?spm1001.2014.3001.5502 1.数组基本知识点
1.1概念
数组就是一个集合。数组会用一些名为索引的数字来标识每项数据在数组中的位置且在大多数编程语言中索引是从 0 算起的。我们可以根据数组中的索引快速访问数组中的元素。
数组中的元素在内存中是连续存储的且每个元素占用相同大小的内存。
1.2 相关操作的时间复杂度和空间复杂度
访问元素时间复杂度都是O(1)空间复杂度O(1)因为对于固定大小的数组访问时间不随数组大小而变化。通过下标可直接访问。
修改元素时间复杂度O(1)空间复杂度O(1)与n无关通过下标可直接修改
插入元素和删除元素时间复杂度O(1)空间复杂度O(1)插入和删除元素都需要移动后面的元素因此随n变化。 题11 最大连续1的个数
给定一个二进制数组 nums 计算其中最大连续 1 的个数。 示例 1 输入nums [1,1,0,1,1,1] 输出3 解释开头的两位和最后的三位都是连续 1 所以最大连续 1 的个数是 3. 思路第一步遍历数组如果值等于1则number加1然后每次更新之前number中最大的那个第二步如果值不等于1则重置number开始重新计数。 代码案例
class Solution
{
public:int findMaxConsecutiveOnes(vectorint nums){int size nums.size();int number 0;int returnnumber 0;for (int first 0; first size; first){if (nums[first] ! 1) //如果值不是1则重新记录数量{number 0;}else 如果值是1则数量1{number;}returnnumber max(returnnumber, number);//每次更新最大连续数量的值}return returnnumber;}
};
题12 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl1, ..., numsr-1, numsr] 并返回其长度。如果不存在符合条件的子数组返回 0 。 示例 1 输入target 7, nums [2,3,1,2,4,3] 输出2 解释子数组 [4,3] 是该条件下的长度最小的子数组。 示例 2 输入target 4, nums [1,4,4] 输出1 思路 首先需要查找子数组所以不能排序此数组。因为需要找到子数组的头和尾部思路可以靠近双指针。 第一次滑动 第一次滑动达到目标 23128 2 3 1 2 4 3 s q 第一次尝试收缩发现 8-2 7,则无法收缩。此时的长度为4代表nums[0]满足条件的最小区间范围。 第2次滑动 快指针继续向前第二次达到目标 2312412 2 3 1 2 4 3 s q 第二次尝试收缩发现 107,可以收缩。 2 3 1 2 4 3 s q 此时的长度也是4代表nums[1]满足条件的最小区间范围。 再次尝试收缩 77,可以收缩。 2 3 1 2 4 3 s q 此时的长度是3代表nums[2]满足条件的最小区间范围。 然后无法再次收缩了此时nums[0]nums[1]nums[2]满足的最小区间范围。 第三次滑动 快指针继续向前第三次达到目标 12437 2 3 1 2 4 3 s q 然后尝试收缩收缩成功 10-17 2 3 1 2 4 3 s q 此时的长度是3代表nums[3]满足条件的最小区间范围。 然后继续尝试收缩收缩成功9-27 2 3 1 2 4 3 s q 此时的长度是2代表nums[4]满足条件的最小区间范围。 此时quick走到了末尾然后能收缩的都收缩了代表nums[4]以后的都无法满足大于等于目标值的最小区间范围的条件。 代码案例
class Solution
{
public:int minSubArrayLen(int target, vectorint nums){int size nums.size();int slow 0; // 初始化慢指针int quick 0; // 初始化快指针int sum 0; // 前缀和int returnlength size 1;for (; quick size; quick) {sum sum nums[quick]; // 对前面的子数组进行求和if (sum target) // 当前面的和小于目标值的时候无法收缩当和大于目标值的时候才能收缩。{while ((sum - nums[slow]) target)//尝试缩小字数组区间{sum sum - nums[slow];slow;}returnlength min(returnlength, quick - slow 1);}}return returnlength size 1 ? 0 : returnlength;//如果所有的和都小于target则返回0}
};
题13 盛最多的水
给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。 输入[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 作题思路 第一步首先分析最大的水的容量应该是Value 长*宽。那么长quick -slow宽min(height[quick],height[slow])所以很明显此题应该用双指针。通常双指针有两种用法。第一种是一个指向头一个指向尾部相反方向移动。第二种是两个都指向头同方向移动。因此此题也有两种做法。 法一 双指针同方向移动。 从height[0]开始遍历其后值和height[0]形成的大小然后求最大值。 然后继续从height[1]开始遍历其后值和height[0]形成的大小然后求最大值。 缺点 时间复杂度为N的平方。 法一代码案例
class Solution
{
public:int maxArea(vectorint height){int returnvalue 0;//返回的最大值int slow 0;//初始化慢指针int size height.size();for (; slow size - 1; slow)//慢指针遍历{for (int quick slow 1; quick size; quick)//快指针遍历{int x quick - slow;//获取长int y min(height[quick], height[slow]);//获取宽returnvalue max(returnvalue, x * y);//更新最大值}}return returnvalue;}
}; 法二思路 首先此题相当于找出任何两个y轴和x轴形成的长方形面积最大。那么双指针首先就需要包含所有的可以作为长方形边界的范围。即 第一步初始化慢指针slow指向头的位置初始化快指针quick指向末尾的位置。 第二步计算此时长方型的最大面积那么此时长是xquick -slowy的值是min(height[quick], height[slow])。 第三步移动指针那么如何移动呢假设此时数组长度是5height[quick]是6height[slow]是1首先如果移动较大的值即我们放弃较大的值作为长方形的边界, 那么有以下三种情况 1.如果height[quick-1]的值6那么新的长方形此时长是4宽仍然是height[slow]的,此时 新的长方形最大面积是必然小于前一个值的。 2.如果height[slow]height[quick-1]6,那么新的长方形此时长是4宽仍然是height[slow]的,此时新的长方形最大面积是必然小于前一个值的。 3.如果height[quick-1]height[slow],那么新的长方形此时长是4宽是height[quick-1],此时新的长方形最大面积是必然小于前一个值的。 那么此时我们就知道当我们移动较大的边界值时候。其值永远都是更小的。 此时我们再分析一下移动较小的值。有以下几种情况。 1.如果height[slow1]height[slow],则此时长从5变为4则最大面积变小。 2.如果height[slow1]height[slow],则此时有可能新的长方形面积更大。 所以我们只能移动较小的那个边界值。 第四步每次移动获取的值和最大值作比较保留最大值。 第五步当左边界和右边界重合时说明所有可能比之前的长方形面积更大的都计算完了。 法二代码案例
class Solution
{
public:int maxArea(vectorint height){int returnvalue 0; // 返回的最大值int slow 0; // 初始化慢指针指向头的位置int quick height.size() - 1; // 初始化快指针指向末尾的位置while (slow quick){returnvalue max(returnvalue, (quick - slow) * min(height[quick], height[slow]));if (height[quick] height[slow]){slow;//如果右边界值大于左边界值则移动左边界值}else{quick --;//如果右边界值小于左边界值则移动右边界值}}return returnvalue;}
};
题14 三数之和
给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请
你返回所有和为 0 且不重复的三元组。
注意答案中不可以包含重复的三元组。 示例 1 输入nums [-1,0,1,2,-1,-4]
输出[[-1,-1,2],[-1,0,1]]
解释
nums[0] nums[1] nums[2] (-1) 0 1 0 。
nums[1] nums[2] nums[4] 0 1 (-1) 0 。
nums[0] nums[3] nums[4] (-1) 2 (-1) 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意输出的顺序和三元组的顺序并不重要。示例 2 输入nums [0,1,1]
输出[]
解释唯一可能的三元组和不为 0 。示例 3 输入nums [0,0,0]
输出[[0,0,0]]
解释唯一可能的三元组和为 0 。思路 首先对于数组的操作能先排序就排序能双指针就双指针。 此题也可以理解为 遍历每一个值然后从剩下的所有值中找两个其他的值其三个的和等于0。 第一步对数组排序如果前三个最小的之和大于0因为数组此时是递增的那么后面不可能等于0则返回。 假设此时数组长度是5。 第二步固定第一个数字nums[0]此时我们的条件就变成了在剩下不包括nums[0]的数组中找到两个值这两个值的和是-nums[0]。而此时是已经排序的数组。 第三步让慢指针指向nums[1]的位置快指针指向nums数组的尾部nums[4]然后判断nums[1]nums[4] 和(0-nums[i])的大小。如果大于(0-nums[i])则尾指针向左移动如果小于则头指针向右移动。如果等于则满足条件此时如果没有重复值则头指针向右移动并且尾指针向左移动。如果有重复值则需要跳过。 想一想如果此时满足条件的值是(-1,0,1),而nums[3]也等于-1如果没跳过则出现两个(-1,0,1)不满足条件。 第四步然后遍历第二个元素如果第二个等于第一个则跳过遍历下一个。然后重复第二步到第四步。 代码案例
class Solution
{
public:vectorvectorint threeSum(vectorint nums){vectorvectorint returnvector;if (nums.size() 3){return returnvector;}sort(nums.begin(), nums.end());if (nums[0] nums[1] nums[2] 0){return returnvector;}for (int i 0; i nums.size() - 2; i){if (i 0 nums[i] nums[i - 1])continue;// 跳过重复的元素int slow i 1;//慢指针指向不要nums[i]的数组的头int quick nums.size() - 1;慢指针指向不要nums[i]的数组的尾while (slow quick){int sum nums[slow] nums[quick] nums[i];if (sum 0)//当值相等的时候则说明找到了{returnvector.push_back({nums[i], nums[slow], nums[quick]});while (slow quick nums[slow] nums[slow 1])slow; // 跳过重复的元素while (slow quick nums[quick] nums[quick - 1])quick--; // 跳过重复的元素slow;quick--;}else if (sum 0)//当值大于0的时候则说明我们我们需要移动数组尾端让值变小一点{quick--;}else if (sum 0)//当值小于0的时候则说明我们我们需要移动数组头端让值变大一点{slow;}}}return returnvector;}
};
题15 最接近的三数之和
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。 示例 1 输入nums [-1,2,1,-4], target 1
输出2
解释与 target 最接近的和是 2 (-1 2 1 2) 。示例 2 输入nums [0,0,0], target 1
输出0思路 首先对于数组的操作能先排序就排序能双指针就双指针。 此题也可以理解为 遍历每一个值然后从剩下的所有值中找两个其他的值其三个的和减去target的值的绝对值最小。 第一步对数组进行排序假如此时数组是nums[-1,2,1,-4]排序后是[-4,-1,1,2] 第二步因为要遍历所有值所以第一次循环先挑选nums[0],然后就变成了在[-1,1,2]中选择任意两个值判断三个的和减去target的值的绝对值最小。 第三步慢指针指向-1快指针指向2此时判断nums[0]nums[slow]nums[quick] -target的值。 1.如果A[0]A[slow]A[quick] -target 0则直接返回sum target。 2.如果A[0]A[slow]A[quick] -target 0 尾指针得向左移动 如果前三个和大于taraget则说明要找到下一个更小的。这样可能更靠近target。此时尾指针向左移动此时需要计算temp - target的绝对值和上一个绝对值的大小如果当前三个数和的绝对值小于之前的绝对值则更新sum。 3.如果前三个和小于taraget则说明要找到更大的。这样可能更靠近target。此时头指针向右移动此时需要计算temp - target的绝对值和上一个绝对值的大小如果当前三个数和的绝对值小于之前的绝对值则更新sum。 此时我们在第一次循环中就找到了以第一个元素为首的与target距离最近的三个数的和。 第二次循环继续重复第二步和第三步这样就找出了第二个数组为首的三个数与target距离最近的。依次遍历就找到了所有的子集中与与target距离最近的。 代码案例
class Solution
{
public:int threeSumClosest(vectorint nums, int target){int sum 0;int closevalue INT32_MAX;//初始化为做大值因为后面要取minsort(nums.begin(), nums.end()); //排序for (int first 0; first nums.size() - 2; first){int slow first 1;int quick nums.size() - 1;while (slow quick){int temp nums[first] nums[slow] nums[quick];//计算前三个的和if (temp - target 0)//如果等于taraget则直接返回{return temp;}else if (temp - target 0) //如果前三个和大于taraget则说明要找到下一个更小的。这样可能更靠近target。此时尾指针向左移动//此时需要计算temp - target的绝对值和上一个绝对值的大小如果当前三个数和的绝对值小于之前的绝对值则更新sum{if (abs(temp - target) closevalue){closevalue min(abs(temp - target), closevalue);sum temp;}quick--;}else if (temp - target 0){if (abs(temp - target) closevalue)//如果前三个和小于taraget则说明要找到更大的。这样可能更靠近target。此时头指针向右移动//此时需要计算temp - target的绝对值和上一个绝对值的大小如果当前三个数和的绝对值小于之前的绝对值则更新sum{closevalue min(abs(temp - target), closevalue);sum temp;}slow;}}}return sum;}
};
