刷题笔记:力扣第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)满足题目要求。