刷题笔记:力扣第704、977、209题（数组相关）

力扣第704题-二分查找

1.练手题，简单的二分排序，完整代码如下：

1. int search(int* nums, int numsSize, int target) { 2. // 左边界l初始为数组起点下标0，右边界r初始为数组最后一个元素下标 3. int l = 0, r = numsSize - 1; 4. // 左边界<=右边界时区间内还有元素，持续二分查找 5. while (l <= r){ 6. // 计算中间下标 7. int mid = (l + r) / 2; 8. // 中间值小于目标值，目标在右半区间，更新左边界 9. if (nums[mid] < target){ 10. l = mid + 1; 11. } else if (nums[mid] > target){ 12. // 中间值大于目标值，目标在左半区间，更新右边界 13. r = mid - 1; 14. } else { 15. // 找到目标值，返回对应下标 16. return mid; 17. } 18. } 19. 20. // 循环结束未找到目标，返回-1 21. return -1; 22. }

时间复杂度O(logn)，空间复杂度O(1)，标准写法。

力扣第977题-有序数组的平方

1.直接算出平方后暴力排序肯定是不可取的，那样的算法时间复杂度为O(nlogn)，题目要求时间复杂度为O(n)，即遍历一遍数组便能得出答案。

2.初步想法为寻找非正数与正数的分界点，使用左右两个指针来进行比较和排序，完整代码如下：

1. int* sortedSquares(int* nums, int numsSize, int* returnSize) { 2. // 分配和原数组长度相同的内存，存放平方后的结果 3. int* res = (int*)malloc(sizeof(int) * numsSize); 4. // cur 标记结果数组当前存放元素的位置 5. int cur = 0; 6. // r 右指针，寻找第一个非负数下标 7. int r = 0; 8. 9. // 右指针向右移动，找到第一个不小于0的数字 10. while (r < numsSize && nums[r] < 0){ 11. r++; 12. } 13. 14. // l 左指针指向最后一个负数的下标 15. int l = r - 1; 16. 17. // 左右指针都未越界，比较绝对值大小，小的平方先放入结果 18. while (l >= 0 && r < numsSize){ 19. // 左边负数绝对值更小，先存左边平方 20. if (-nums[l] < nums[r]){ 21. res[cur++] = nums[l] * nums[l]; 22. l--; 23. } else { 24. // 右边数字更小或相等，存右边平方 25. res[cur++] = nums[r] * nums[r]; 26. r++; 27. } 28. } 29. 30. // 若左指针还有剩余负数，依次放入结果 31. while (l >= 0){ 32. res[cur++] = nums[l] * nums[l]; 33. l--; 34. } 35. 36. // 若右指针还有剩余非负数，依次放入结果 37. while (r < numsSize){ 38. res[cur++] = nums[r] * nums[r]; 39. r++; 40. } 41. 42. // 给外部参数赋值结果数组长度 43. *returnSize = cur; 44. return res; 45. }

该算法时间复杂度为O(nlogn)，满足题目要求。

3.答案提供了另外一种思路，原数组的平方一定是从两端向中间依次递减，所以可以不用排序，将左右指针放置于数组两端，比较平方后更大的那一个逆序放入结果数组。完整代码如下：

1. int* sortedSquares(int* nums, int numsSize, int* returnSize) { 2. // 开辟结果数组，空间大小与原数组一致 3. int* res = (int*)malloc(sizeof(int) * numsSize); 4. // cur 从结果数组末尾开始填充，大数放后面 5. int cur = numsSize - 1; 6. // l 左指针指向数组最左端（负数区），r 右指针指向数组最右端（正数区） 7. int l = 0, r = numsSize - 1; 8. 9. // 左右指针未相遇时循环 10. while (l <= r){ 11. // 左侧数字平方更大 12. if (nums[l] * nums[l] > nums[r] * nums[r]){ 13. // 将大的平方值放入结果数组尾部，游标前移，左指针右移 14. res[cur--] = nums[l] * nums[l]; 15. l++; 16. } else { 17. // 右侧数字平方更大或相等，存入尾部，游标前移，右指针左移 18. res[cur--] = nums[r] * nums[r]; 19. r--; 20. } 21. } 22. 23. // 返回数组长度等于原数组长度 24. *returnSize = numsSize; 25. return res; 26. }

该算法时间复杂度为O(nlogn)，满足题目要求。

力扣第209题-长度最小的子数组

1.这道题肯定是使用滑动窗口，初步写出的代码如下：

1. int minSubArrayLen(int target, int* nums, int numsSize) { 2. int l = 0, r = 0; 3. int tmp = 0; 4. int res = 100001; 5. 6. while (r < numsSize && l <= r){ 7. int cnt = r - l; 8. if (tmp < target){ 9. tmp += nums[r++]; 10. } else { 11. res = fmin(res, cnt); 12. tmp -= nums[l++]; 13. } 14. } 15. 16. return res == 100001 ? 0 : res; 17. }

2.初步写的代码连本地算例都没通过，询问ai后得知滑动窗口的处理逻辑有些问题。正确的滑动窗口处理方式应该是右指针一直无条件向前，左指针根据条件向前回退吐出元素。这种错误在力扣第3题犯过，属于时间久了忘记该知识点了，正好通过本题来回忆一下。

3.基于以上思想，写出的完整代码如下：

1. int minSubArrayLen(int target, int* nums, int numsSize) { 2. // 记录满足条件的最小子数组长度，初始值设为大于数组最大可能长度的数 3. int res = 100001; 4. // 滑动窗口内元素累加和 5. int tmp = 0; 6. 7. // 滑动窗口，l窗口左边界，r窗口右边界，右边界不断向右扩张 8. for (int l = 0, r = 0; r < numsSize; r++){ 9. // 将当前右边界数值加入窗口和 10. tmp += nums[r]; 11. // 窗口和大于等于目标值时，尝试收缩左边界，寻找更短合法子数组 12. while (tmp >= target){ 13. // 计算当前窗口长度 14. int cnt = r - l + 1; 15. // 更新最小长度 16. res = fmin(res, cnt); 17. // 左边界右移，窗口缩小，减去移出窗口的数值 18. tmp -= nums[l++]; 19. } 20. } 21. 22. // 如果res未更新说明无满足条件子数组返回0，否则返回最小长度 23. return res == 100001 ? 0 : res; 24. }

时间复杂度为O(n)，满足题目要求。