当前位置：首页 > article >正文

leetcode01——27. 移除元素（双指针）、977. 有序数组的平方（双指针）、209. 长度最小的子数组（双指针/滑动窗口）

article 2024/9/21 20:28:38

27. 移除元素

/**
定义快慢指针，均从0开始，fast向后移动，遇到不为删除值的就停下，将值赋值给slow,slow++
遇到等于目标值就直接跳过，不等于目标值就赋值，这样就能 过滤掉（也就是删除掉）目标值
 */
class Solution {
    public int removeElement(int[] nums, int val) {
        int fast = 0;
        int slow = 0;
        for (fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }
}

977. 有序数组的平方

/**
双指针
    因为非递减排序的数组中有负数，因此不能直接就平方然后排序
    但是平方后数组两端的数据一定是最大的（如：-5，1，3，6）
    因此定义左右两个指针，判断平方后的数的大小，将大的放在新数组的末尾
 */
class Solution {
    public int[] sortedSquares(int[] nums) {
        int left = 0;
        int len = nums.length;
        int right = len-1;
        int[] newNums = new int[len];

        // 类似二分查找的思路
        while (left <= right) {
            if (nums[left]*nums[left] < nums[right]*nums[right]) {
                newNums[len-1] = nums[right]*nums[right];
                right--;
            } else {
                newNums[len-1] = nums[left]*nums[left];
                left++;
            }
            len--;
        }
        return newNums;
    }
}

209. 长度最小的子数组

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int res = Integer.MAX_VALUE;
        int sum = 0; //滑动窗口数值之和
        int i = 0; //滑动窗口的起始位置
        int subLength = 0; //滑动窗口的长度

        for (int j = 0; j < nums.length; j++) {
            sum += nums[j];
            // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
            while (sum >= target) {
                subLength = (j - i + 1); //取子序列长度
                res = res < subLength ? res : subLength;
                sum -= nums[i++]; //这里体现出滑动窗口的精髓之处，不断变更i(子序列的起始位置）
            }
        }
        // 如果res0没有被赋值的话，就返回0，说明没有符合条件的子序列
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}