系列文章
https://blog.csdn.net/handsomethefirst/article/details/138226266?spm=1001.2014.3001.55021.数组基本知识点
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(vector<int> &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, numsl+1, ..., 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
思路：
首先需要查找子数组，所以不能排序此数组。因为需要找到子数组的头和尾部，思路可以靠近双指针。
第一次滑动：
第一次滑动达到目标 2+3+1+2=8
2 3 1 2 4 3
s q第一次尝试收缩发现 8-2< 7,则无法收缩。此时的长度为4，代表nums[0]满足条件的最小区间范围。
第2次滑动：快指针继续向前，第二次达到目标 2+3+1+2+4=12
2 3 1 2 4 3
s q第二次尝试收缩发现 10>7,可以收缩。
2 3 1 2 4 3
s q此时的长度也是4，代表nums[1]满足条件的最小区间范围。
再次尝试收缩， 7=7,可以收缩。
2 3 1 2 4 3
s q此时的长度是3，代表nums[2]满足条件的最小区间范围。
然后无法再次收缩了，此时nums[0]，nums[1]，nums[2]满足的最小区间范围。
第三次滑动：
快指针继续向前，第三次达到目标， 1+2+4+3>=7
2 3 1 2 4 3
s q然后尝试收缩，收缩成功， 10-1>=7
2 3 1 2 4 3
s q此时的长度是3，代表nums[3]满足条件的最小区间范围。
然后继续尝试收缩，收缩成功，9-2=7
2 3 1 2 4 3
s q此时的长度是2，代表nums[4]满足条件的最小区间范围。
此时quick走到了末尾，然后能收缩的都收缩了，代表nums[4]以后的都无法满足大于等于目标值的最小区间范围的条件。
代码案例
class Solution
{
public:
int minSubArrayLen(int target, vector<int> &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(vector<int> &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指向末尾的位置。
第二步：计算此时长方型的最大面积，那么此时长是x=quick -slow，y的值是min(height[quick], height[slow])。
第三步：移动指针，那么如何移动呢？假设，此时数组长度是5，height[quick]是6，height[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[slow+1]<=height[slow],则此时长从5变为4，则最大面积变小。
2.如果height[slow+1]>height[slow],则此时有可能新的长方形面积更大。
所以我们只能移动较小的那个边界值。
第四步：每次移动获取的值和最大值作比较，保留最大值。
第五步：当左边界和右边界重合时，说明所有可能比之前的长方形面积更大的都计算完了。
法二代码案例：
class Solution
{
public:
int maxArea(vector<int> &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:
vector<vector<int>> threeSum(vector<int> &nums)
{
vector<vector<int>> 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(vector<int> &nums, int target)
{
int sum = 0;
int closevalue = INT32_MAX;//初始化为做大值，因为后面要取min
sort(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;
}
};
