一,简单

1.1题目

图片.png

1,2解法

两个指针变量left和right,相当于是滑动窗体,根据sum(累加和)来判断是left移动还是right移动,k为目标值
1,如果sum==k,这是记录下数组的长度(len变量表示),在right之后的结尾的子数组一定大于当前的sum,所有left+1,开始考察left以后的子数组,同时把left对应的值(arr[left])除去.
2,如果sum>k,说明加上以right结束的子数组大了,查考left+1的子数组
3,如果sum<k,则right继续移动,同时需要判断,是否有溢出的危险

图解为 图片.png

1.3代码实现

public static int getMaxLength(int[] arr,int k)
    {
        if(arr==null||arr.length==0 || k<=0)
        {
            return 0;
        }
        int L=0;
        int R=0;
        int sum=arr[0];
        int len=0;
        while(R<arr.length)
        {
            if(sum==k)//等于的话,锁,并记录
            {
                len=Math.max(len,R-L+1);
                sum-=arr[L++];
            }
            else if(sum<k)//小于的话,继续扩,但是有越界的风险
            {
                R++;
                if(R==arr.length)
                {
                    break;
                }
            }
            else //大于的话,缩
            {
                sum-=arr[L++];
            }
        }
        
        return len;
    }

二,中等

2.1题目

图片.png

2.2分析

sum[j...i]=sum[i]-sumj

图片.png
需要记录s(j)的的值和位置,我们定义一个hashmap,key存加到当前的sum值(0到当前下标),value存其下标
图片.png
通过图可以知道我们key记录值,value记录出现这个值的最早的index
图片.png

注:边界问题

图片.png

2.3 代码实现

public static int maxLength(int[] arr, int k) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        map.put(0, -1); // important
        int len = 0;
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            if (map.containsKey(sum - k)) {
                len = Math.max(i - map.get(sum - k), len);
            }
            if (!map.containsKey(sum)) {
                map.put(sum, i);
            }
        }
        return len;
    }

三,复杂