刷题笔记

刷题笔记 数组 数组理论基础

​ **数组是存放在联系内存空间上的相同类型数据的集合。**数组可以方便的通过下标索引的方式获取到下标下对应的数据。

注意：

数组下标都是从0开始。

数组内存空间的地址是连续的。

  因为数组在内存空间的地址是连续的，所以我们在增加或删除元素的时候，就难免要移动其他元素的地址。

​ 数组的元素是不能直接删除，只能对其覆盖。

在java中二维数组不是连续的。

二分查找

​ 二分查找(Binary Search)，也叫折半查找。二分查找两个要求：1.数组有序 ，2.数列是采用顺序存储结构(数组)

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

输入：nums = [1,0,3,5,9,12] target = 9
输出：4
解释：9在 nums 中的下标为4

输入：nums = [1,0,3,5,9,12] target = 2
输出：-1
解释：2在 nums 中不存在

思路：

​ **有序数组，无重复。**因为一旦有重复元素，二分查找的元素下标可能不唯一。根据折半查找定义一步一步做就好了，考虑好边界条件。

代码示例：

class Solution {
    //闭合区间
    public int  search(int [] nums , int target){
        //首先判断是否在本数组内
        if(target < nums[0] || target > nums[nums.length-1]){
            return -1;
        }
        int left = 0,right = nums.length-1;
        while (left <= right){
            int mid = (left + right) >> 1;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] > target){
                right = mid - 1;
            }else if (nums[mid] < target){
                left = mid + 1;
            }
        }
        return -1;
    }
}

总结：

​ 二分查找是重要的基础算法，只要是对区间定义理解清楚，在循环中要坚持根据查找区间的定义来做边界处理。

​ 理解好二分查找的定义即可。

移除元素

​

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

​		不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

​		元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

- 示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。

- 示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

你不需要考虑数组中超出新长度后面的元素。

思路：

​ 数组的元素在内存地址中是连续的，不能单独删除数组中某个元素，只能覆盖。

方法一：

​ 暴力解法：两层for循环，第一个for循环遍历数组元素，第二个for循环更新数组。

代码示例：

时间复杂度O(n^2)

//暴力破解
public int removeElement(int []nums , int val ){
        int size = nums.length;
        for(int i = 0 ; i < size ; i ++){
            if(nums[i] == val){
                for(int j = i + 1 ; j < size ; j ++){
                    nums[j-1] = nums[j];
                }
                i -- ;
                size -- ;
            }
        }
        return size ;
    }

方法二：快慢指针

​ 快指针先和val相比较，如果不相等就往下走。慢指针同时往下走。

时间复杂度O(n) 代码示例：

public int removeElement(int [] nums , int val){
    //快慢指针
    int fastIndex = 0;
    int slowIndex;
    for(slowIndex = 0 ; fastIndex < nums.length ; fastIndex++){
        if(nums[fastIndex] != val){
            nums[slowIndex] = nums[fastIndex];
            slowIndex++;
        }
    }
    return slowIndex;
}

有序数组的平方

给你一个按 非递减顺序 排序的整数数组 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循环，逐个求平方，然后利用Arrays.sort()方法排序。

代码示例：

//暴力破解
public int [] sortedSquares(int [] nums){
    for(int i = 0 ; i < nums.length ; i ++){
        nums[i] *= nums[i];
    }
    Arrays.sort(nums);
    return nums;
}

时间复杂度O（n） 方法二：

​ 双指针法：

数组其实是有序的， 只不过负数平方之后可能成为最大数了。

那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

此时可以考虑双指针法了，left指向起始位置，right指向终止位置。

定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。

如果A[left] * A[left] < A[right] * A[right] 那么result[k--] = A[right] * A[right]; 。

如果A[left] * A[left] >= A[right] * A[right] 那么result[k--] = A[left] * A[left]; 。

代码示例：

public int [] sortedSquares01(int [] nums){
    int left = 0 , right = nums.length -1 ;
    int k = nums.length - 1;
    int [] result = new int [nums.length];
    while(left <= right){
        if(nums[left] *nums[left] < nums[right] * nums[right]){
            result[k] = nums[right] * nums[right];
            k -- ;right --;
        }else {
            result[k] = nums[left] *nums[left];
            k --; left ++;
        }
    }
    return result;
}

时间复杂度：O(n) 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：
输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

思路： 方法一：

暴力破解：

​ 根据两重for循环，不断寻找符合条件的子序列

代码示例：

public static int minSubArrayLen(int [] nums , int s){
    //最终结果
     int result = Integer.MAX_VALUE;
     //sum  数组加和  ， subLength  子数组的长度
     int sum = 0 , subLength = 0;
    for (int i = 0; i < nums.length; i++) {
        sum = 0;
        for (int j = i; j < nums.length; j++) {
            sum += nums[j];
            if(sum >= s){
                subLength =  j - i + 1;
                result = result < subLength ? result : subLength;
                break;
            }
        }
    }
    return result == Integer.MAX_VALUE ? 0 : result;
}

时间复杂度O(n^2) 方法二：

滑动窗口法：不断调节子序列的起始位置和终止位置，从而得出想要的结果

首先int 一个快指针int right 然后int 一个慢指针 left 计算left–right之间的元素的和是否大于s。再将left指针向前移动。最后得出结果

滑动窗口实现过程

窗口内容如何确定窗口的起始位置如何确定窗口的终止位置

窗口就是满足 窗口内部元素的和 >= s 的最小长度的连续子数组。

窗口起始位置移动: 如果当前窗口的值大于 s ，窗口则需要向前移动（窗口给减小）

窗口终止位置移动：窗口终止位置就是数组遍历的指针，窗口起始位置设置为数组的起始位置就可以了。

滑动窗口的精妙之处在于根据当前子序列中和的大小情况，不断调节子序列的起始位置。从而将O(n^2)的暴力破解法降为O(n)的滑动窗口法

代码示例：

//最终结果
int result = Integer.MAX_VALUE;
int left = 0 ;
//滑动窗口之和
int sum = 0;
for(int right = 0 ; right < nums.length ; right++){
    //sum 加所有nums[right]的值
    sum += nums[right];
    while(sum >= target){
        result = Math.min(result,right - left + 1);
        sum -= nums[left++];
        //left ++ ;
    }
}
return result == Integer.MAX_VALUE ? 0 : result;

时间复杂度O(n)