汇聚|LeetCode 数组篇（上）

ps：本篇内容是基于LeetCode题目进行分类总结而出的一些个人经验，希望对你有帮助！

简介：给定一个数组，围绕着子数组进行展开！
核心：子数组一定是连续的，子数组一定是连续的，子数组一定是连续的！

  如果题目是围绕子数组的最大和，积等展开的，那很大的概率是要用到++局部迭代++和++全程更新++（名字是我瞎起的）。
   此外，你要明确你在干什么，即在遍历过程中，你以什么做为出发点，如以当前元素作为最佳子数组的结束元素……（结合后面的代码你会理解的）
  先送你上述两把菜刀，方便你更好的去切下面的菜！

局部迭代

简介：在遍历数组的过程中，对满足一定条件的元素连接起来，如果不满足就另起门户！
形式：
for(int i=0;i 
全程更新 
简介：操作一次，更新一次（就是这么简单）
形式：
在上述for循环中，每执行完
【变量=条件函数（变量与nums[i],nums[i])】
就可以紧跟着更新操作。
如：ans=Math.max(变量,ans);
 
  拿好菜刀，来看看下面的“菜”吧！
 【53.最大子数组和】
 
 【前排】别看我，我是不会告诉你答案的！ 先好好想想如何使用上面的两把菜刀！
 
-----------------------------
【提示】以nums[i]元素作为结束元素，如果当前元素nums[i]加上上一个元素值会更大则进行连接；
 
【152. 乘积最大子数组】
 
 
【前排】别看我，我是不会告诉你答案的！ 将+改为了*，如果遇到了负数会有什么情况？
 
-----------------------------
【提示】以nums[i]元素作为结束元素,如果能够跟前面的值组合成更大的值，则进行连接，否则单独开始新的匹配。此题中由于是乘法，故最大值有两种情况：（1）正数*最大值；（2）负数*最小值
 
ANS：
 【53】(没做出来也别灰心~~）
 
public int maxSubArray(int[] nums) {
     int ans=nums[0];
     int len=nums.length;
     if(len==1){
         return ans;
     }
     // 贪心：以nums[i]元素作为结束元素，如果加上上一个元素值会更大则进行更新；
     for(int i=1;i 
【152】
 
public int maxProduct(int[] nums) {
        int len=nums.length;
        int maxn=nums[0];
        int preMax=nums[0];
        int preMin=nums[0];
        // 贪心：以nums[i]元素作为结束元素,如果能够跟前面的值组合成更大的值，则进行连接，否则单独开始新的匹配。此题中由于是乘法，故最大值有两种情况：（1）正数*最大值；（2）负数*最小值
        for(int i=1;i 
【小试牛刀】（不要死记，灵活应对）
   在152中，有最大值和最小值两种交替情况，下面这题也是有类似的情况，可以刺激一下思维！
 【978. 最长湍流子数组】
 
 
【提示】以nums[i]作为结尾元素（判断是升还是降），如果是升那就寻找前面的降；如果是降就寻找前面的升；如果相等，那就重置。
 【ans】
 
public int maxTurbulenceSize(int[] arr) {
      int up=1,down=1,ans=1,len=arr.length;
      for(int i=1;iarr[i-1]){
               up=down+1;
               // 当前是升，如果要是降的话，就只能以arr[i]作为降的起始点
               down=1;
           } else if(arr[i] 
指定条件收索子数组 
  在数组中搜索一定条件下关于子数组的一些属性，如子数组的个数。此时，大部分得采用哈希表以降低时间复杂度，如HashMap，HashSet，普通数组等。
 
  看题
 【560. 和为 K 的子数组】
 
 
 
【简述】一次遍历：维护一个累加和，通过哈希表对目标值进行查询，记录，再添加到哈希表中。
 【ans】
 
 public int subarraySum(int[] nums, int k) {
       int len=nums.length;
       HashMap record=new HashMap();
       record.put(0,1);
       int ans=0;
       int sum=0;
       // 通过hashMap记录过去的累计和，替换二重遍历。
       for(int i=0;i 
【974. 和可被 K 整除的子数组】
 
 【简述】与上述基本一样，只是查询目标值的方法不一样，采用余数方式进行收索。
 
可被整除一般会用到同余法。
如：两个整数相减，什么时候会得到一个整数？
   那肯定是对某一个数取余，且余数相等的情况下。
但是要注意负数的情况，可套用的公式：k=（num%mod+mod)%mod;
可以尝试-3与4相减是否可以被7整除。
 
【ans】
 
 public int subarraysDivByK(int[] nums, int k) {
       int len=nums.length;
       HashMap record=new HashMap();
       record.put(0,1);
       int ans=0;
       int sum=0;
       int mod=0;
       for(int i=0;i 
【1157. 子数组中占绝大多数的元素】
 
 
【简述】不要被困难吓到，此处可以采用哈希表暴力通过，嘻嘻嘻。通过一个数组记录该区间内元素的出现个数。
 【ans】
 
  private int []nums;
    private int []ans;
    private int max;
    public MajorityChecker(int[] arr) {
        nums=arr;
         max=arr[0];
        for(int n:arr){
            max=Math.max(n,max);
        }
    }
    
    public int query(int left, int right, int threshold) {
        ans=new int [max+1];
        for(int i=left;i<=right;i++){
            if(++ans[nums[i]]>=threshold){
                return nums[i];
            }
        }
        return -1;
    }
 
 
本文到此结束！希望对你有所帮助！