代码随想录day2
有序数组的平方
题目
给你一个按 非递减顺序 排序的整数数组 nums
,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
示例 1:
1 2 3 4
| 输入:nums = [-4,-1,0,3,10] 输出:[0,1,9,16,100] 解释:平方后,数组变为 [16,1,0,9,100] 排序后,数组变为 [0,1,9,16,100]
|
示例 2:
1 2
| 输入:nums = [-7,-3,2,3,11] 输出:[4,9,9,49,121]
|
提示:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums
已按 非递减顺序 排序
进阶:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| 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; } private: int sort(vector<int>& nums); };
|
主要解题思路和笔记
双指针法,双指一个从前往后一个从后往前,对比谁找到的大就把谁放进数组里
题目
给定一个含有 n
个正整数的数组和一个正整数 target
。
找出该数组中满足其总和大于等于 target
的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr]
,并返回其长度。如果不存在符合条件的子数组,返回 0
。
示例 1:
1 2 3
| 输入:target = 7, nums = [2,3,1,2,4,3] 输出:2 解释:子数组 [4,3] 是该条件下的长度最小的子数组。
|
示例 2:
1 2
| 输入:target = 4, nums = [1,4,4] 输出:1
|
示例 3:
1 2
| 输入:target = 11, nums = [1,1,1,1,1,1,1,1] 输出:0
|
提示:
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105
进阶:
- 如果你已经实现
O(n)
时间复杂度的解法, 请尝试设计一个 O(n log(n))
时间复杂度的解法。
常规暴力解
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| class Solution { public: int minSubArrayLen(int s, vector<int>& nums) { int result = INT32_MAX; int sum = 0; int subLength = 0; for (int i = 0; i < nums.size(); i++) { sum = 0; for (int j = i; j < nums.size(); j++) { sum += nums[j]; if (sum >= s) { subLength = j - i + 1; result = result < subLength ? result : subLength; break; } } } return result == INT32_MAX ? 0 : result; } };
|
滑动窗口双指针法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int i =0,j=0; int ret =0; int sum =0; while(j<nums.size()){ sum+=nums[j]; ++j; while(sum>=target){ ret=ret==0?j:min(ret,j-i); sum-=nums[i]; i+=1; } } return ret; } };
|
笔记
滑动窗口相比常规暴力解省略了重复的工作,在窗口到头之后立即挪动前方的起始位置,这样能够把时间复杂度降低到2*n。