4.有序数组的平方
给你一个按 非递减顺序 排序的整数数组 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]
双指针法
此时的时间复杂度为O ( n ) O(n)O(n)
package com.caq.array; import org.junit.Test; /** * 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。 * * @Date 2021/12/18 9:19 * @Version 1.0 */ public class SquaringAnOrderedArray { public static void main(String[] args) { int[] nums = {-4, -2, 0, 1, 2, 3}; SquaringAnOrderedArray soa = new SquaringAnOrderedArray(); int[] ints = soa.sortedSquares(nums); int[] ints1 = soa.sortArray(nums); for (int anInt : ints1) { System.out.println(anInt); } } /** * 思路分析： * 因为数组是有序的，数组元素平方后最大和最小的一定是在最前面或最后面不可能在中间 * 所以我们定义两个指针，一个指向最前面，一个指向最后面 * 我们将它们平方后的结果进行比较，结果大的放到一个新的数组里，这个新数组大小和老数组一样，但是我们把下标放到最后 * 这样比一次得到一个最大值，放到后面指针前移即可 * * @param nums * @return */ public int[] sortedSquares(int[] nums) { //注意这两个都是数组坐标,一个在最前面，一个在最后面 int left = 0; int right = nums.length - 1; //在定义一个放结果的数组,和指向新数组最后一个元素的索引 int[] result = new int[nums.length]; int index = nums.length - 1; while (left <= right) { if (nums[left] * nums[left] > nums[right] * nums[right]) { result[index--] = nums[left] * nums[left]; ++left; } else { result[index--] = nums[right] * nums[right]; --right; } } return result; } }
5.长度最小的子树组
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例：
输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
滑动窗口
在本题中实现滑动窗口，主要确定如下三点：
窗口内是什么？
如何移动窗口的起始位置？
如何移动窗口的结束位置？
窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了（也就是该缩小了）。
窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，窗口的起始位置设置为数组的起始位置就可以了。
可以发现滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O ( n 2 ) O(n^2)O(n
2
)的暴力解法降为O ( n ) O(n)O(n)。
package com.caq.array; /** * @Date 2021/12/18 22:58 * @Version 1.0 */ public class SlidingWindow { public static void main(String[] args) { int[] nums = {1, 3, 5, 5, 6, 4, 3}; SlidingWindow sw = new SlidingWindow(); int i = sw.minSubArrayLen(8, nums); System.out.println(i); } public int minSubArrayLen(int s, int[] nums) { int n = nums.length; //n是负责让end指针一直向右移动 if (n == 0) { //数组长度为0的话，直接退出 return 0; } int ans = Integer.MAX_VALUE; //定义一个最大的int值，和下面的Math.min（）方法做对比 int start = 0, end = 0; //定义开始指针和结束指针 int sum = 0; //定义数组中元素的和 while (end < n) { //第一层循环，如果结束指针没有指到最后那么一直循环，当然这里用for循环也是一样的效果for (int end = 0;end<nums.length;end++){} 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; //注意这里的ans == Interger.MAX_VALUE才是boolean } }
