- 数组元素不能删除，只能覆盖
- vector的底层实现是array，严格来讲vector是容器，不是数组
二分法的第一种写法
定义 target 在一个左闭右闭的区间里，也就是[left, right] （这个很重要非常重要）
- while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
- if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int middle = left + ((right - left) / 2);
if (nums[middle] > target) {
right = middle - 1;
} else if (nums[middle] < target) {
left = middle + 1;
} else {
return middle;
}
}
return -1;
}
};
|
二分法的第二种写法
定义 target 是在一个在左闭右开的区间里，也就是[left, right) ，那么二分法的边界处理方式则截然不同
- while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的
- if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size();
while (left < right) {
int middle = left + ((right - left) >> 1);
if (nums[middle] > target) {
right = middle;
} else if (nums[middle] < target) {
left = middle + 1;
} else {
return middle;
}
}
return -1;
}
};
|
双指针法
双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
定义快慢指针
- 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
- 慢指针：指向更新 新数组下标的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slowIndex = 0;
for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
if (val != nums[fastIndex]) {
nums[slowIndex++] = nums[fastIndex];
}
}
return slowIndex;
}
};
|
注意这些实现方法并没有改变元素的相对位置！
双指针法
数组其实是有序的， 只不过负数平方之后可能成为最大数了。
那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。
此时可以考虑双指针法了，i指向起始位置，j指向终止位置。
定义一个新数组result，和nums数组一样的大小，让k指向result数组终止位置。
如果nums[i] * nums[i] < nums[j] * nums[j] 那么result[k--] = nums[j] * nums[j];
如果nums[i] * nums[i] >= nums[j] * nums[j] 那么result[k--] = nums[i] * nums[i];
不难写出如下代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int k = nums.size() - 1;
vector<int> result(nums.size(), 0);
for (int i = 0, j = nums.size() - 1; i <= j;) {
if (nums[i] * nums[i] < nums[j] * nums[j]) {
result[k--] = nums[j] * nums[j];
j--;
}
else {
result[k--] = nums[i] * nums[i];
i++;
}
}
return result;
}
};
|
此时的时间复杂度为O(n)
209. 长度最小的子数组
滑动窗口
在本题中实现滑动窗口，主要确定如下三点：
- 窗口内是什么？
- 如何移动窗口的起始位置？
- 如何移动窗口的结束位置？
窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了（也就是该缩小了）。
窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。
解题的关键在于 窗口的起始位置如何移动，如图所示：
可以发现滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。
C++代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int result = INT32_MAX;
int sum = 0;
int i = 0;
int subLength = 0;
for (int j = 0; j < nums.size(); j++) {
sum += nums[j];
while (sum >= s) {
subLength = (j - i + 1);
result = result < subLength ? result : subLength;
sum -= nums[i++];
}
}
return result == INT32_MAX ? 0 : result;
}
};
|
Wechat
Alipay
