文章目录
有序数组的平方
写在前面
本人是一名在java后端寻路的小白，希望记录此博客来帮助自己理解和日后复习，希望也能够帮助到你。
题目
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
- 输入：nums = [-4,-1,0,3,10]
- 输出：[0,1,9,16,100]
- 解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]
示例 2：
- 输入：nums = [-7,-3,2,3,11]
- 输出：[4,9,9,49,121]
思路解析
暴力解法
这道题目给了一个数组，当中的元素是非递减的（非递减表示元素可能递增，也可能当中有重复值，不算严格的递增），要求把元素进行平方，并且也进行非递减排序。
最容易想到的方法，也就是暴力解法，就是将每个元素进行平方，然后对平方后得到的数组使用Arrays类当中的sort方法直接进行排序。
但是一瞬间竟不知如何返回数组的平方。。菜狗如我
双指针法
采用双指针是因为数组平方之后，最大值最有可能出现在数组两端，最不可能出现在数组中间。（因为数组是非递减的，而且存在负数，所以在平方之后最大值肯定出现在两端）。根据这个想法，我们可以采用双指针，一个指针start指向起始索引，一个指针end指向末尾索引，然后判断这两个指针指向的数哪一个的平方更大，指针指向的元素的平方更大的一者用倒序添加的方式添加到新数组的末尾，然后该指针向中间移动一位，另一个指针不动，继续进行下一次比较。
我的代码
暴力解法
class Solution {
public int[] sortedSquares(int[] nums) {
//先创建新的数组，长度等同于旧数组
int[] newArr = new int[nums.length];
//对旧数组中的元素进行平方，然后赋值给新数组的对应位置上的元素
for(int i = 0; i < nums.length; i++){
newArr[i] = nums[i]*nums[i];
}
//直接调用类Arrays中的sort方法对新数组进行排序
Arrays.sort(newArr);
//返回新数组
return newArr;
}
}
双指针法
class Solution {
public int[] sortedSquares(int[] nums) {
//双指针法，一个指针i指向数组的起始索引，一个指针j指向数组的末尾索引length-1
int i = 0;
int j = nums.length - 1;
int k = nums.length - 1;
//定义一个新数组，长度等于老数组
int[] newArr = new int[nums.length];
//指针移动的循环结束条件，两者相遇表示最后一个元素，此时这个元素是需要写入新数组中的
while(i <= j){
//比较两个指针指向的元素的平方
//假如i指针指向元素的平方更大，那么将其写进新数组的末尾元素，i指针向后移动，j指针不动
if(nums[i]*nums[i] > nums[j]*nums[j]){
newArr[k] = nums[i]*nums[i];
i++;
k--;
}
//假如j指针指向元素的平方更大或者相等，那么将其写进新数组的末尾元素，j指针向前移动，i指针不动
else{
newArr[k] = nums[j]*nums[j];
j--;
k--;
}
}
return newArr;
}
}
参考答案解法
暴力方法
class Solution {
public int[] sortedSquares(int[] nums) {
int[] ans = new int[nums.length];
for (int i = 0; i < nums.length; ++i) {
ans[i] = nums[i] * nums[i];
}
Arrays.sort(ans);
return ans;
}
}
双指针法
class Solution {
public int[] sortedSquares(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
for (int i = 0, j = n - 1, pos = n - 1; i <= j;) {
if (nums[i] * nums[i] > nums[j] * nums[j]) {
ans[pos] = nums[i] * nums[i];
++i;
} else {
ans[pos] = nums[j] * nums[j];
--j;
}
--pos;
}
return ans;
}
}
长度最小的子数组
原题
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
- 输入：nums = [-4,-1,0,3,10]
- 输出：[0,1,9,16,100]
- 解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]
示例 2：
- 输入：nums = [-7,-3,2,3,11]
- 输出：[4,9,9,49,121]
思路解析
暴力法
这题我没有采用暴力法，直接采用了滑动窗口（感觉滑动窗口的思想反而更直观一些）。暴力法是用两次for循环，初始化子数组的最小长度为无穷大，第一个for循环遍历数组 nums 中的每个下标作为子数组的开始下标，对于每个开始下标 i，需要找到大于或等于 i 的最小下标 j，使得从 nums[i] 到 nums[j]的元素和大于或等于 s，并更新子数组的最小长度（此时子数组的长度是 j−i+1）
滑动窗口法
滑动窗口其实就是双指针的变种。窗口其实就是一个连续的子数组，定义两个指针，一个指针start指向窗口的开始索引，一个指针end指向窗口的末尾索引，这两个指针最开始都指向数组的0索引。
滑动窗口法的过程就是，end指针通过一个for循环遍历逐步扩大窗口，start指针保持不动，end每扩大一次，就判断start~end窗口当中的元素总和是否大于目标值target。如果窗口的总和大于目标值，那么start指针就往前移动一位，目的是寻找是否存在潜在的长度更小的而且符合要求的子数组。
怎么求窗口的元素和，这里也是我当时临时想出来的。就是在一开始定义一个变量sum，表示窗口元素的总和。在end指针往前走、而start指针保持不动的时候，每当end向前走一位、窗口扩大一格的时候，窗口元素的总和就往前追加；而每次start往前走一位，窗口元素的总和就减去原来start指针指向的那个元素。
我的代码
我忘记考虑了数组长度为0的情况，这时候需要直接返回0。
class Solution {
public int minSubArrayLen(int target, int[] nums) {
//滑动窗口解法，定义窗口的起始指针和末尾指针
int i = 0;
int j = 0;
//定义一个变量来存储窗口的和
int sum = 0;
//定义一个变量记录最小的窗口长度
int shortest = nums.length + 1;
//用一个for循环中的i指针表示窗口的末尾索引，用j指针表示窗口的起始索引
for(i = 0; i < nums.length; i++){
sum = sum + nums[i];
//判断窗口当中所有元素的和是否大于等于目标值
while(sum >= target){
//窗口元素和大于目标值
//判断，如果窗口的长度=1，说明此时是最小长度，直接返回1
if(i-j+1 == 1){
return 1;
}
//如果子数组的长度不是1，说明还可能存在潜在的最小窗口长度，此时j++
else{
//如果此时窗口长度小于最小窗口长度，则将此时窗口的长度赋值给最小长度
if(i-j+1 < shortest){
shortest = i-j+1;
}
sum = sum - nums[j];
j++;
}
}
//如果窗口之和不符合条件，则i继续++，然后给窗口之和加上i指向的最新的值，随后继续判断
}
if(shortest == nums.length + 1){
return 0;
}
return shortest;
}
}
官方题解
滑动窗口法
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
int ans = Integer.MAX_VALUE;
int start = 0, end = 0;
int sum = 0;
while (end < n) {
sum += nums[end];
while (sum >= s) {
ans = Math.min(ans, end - start + 1);
sum -= nums[start];
start++;
}
end++;
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}
}
