算法日记 - Day4

和为 K 的子数组一般遇到整数数组的子数组有关和的可以考虑前缀和这个题数组不是排好序的也不能排序所以你想利用双指针是不可能的考虑前缀和加入我们设定j i那么s[j] - s[i]就可以表示一个子数组的和如果s[j] - s[i] k那就是我们想要的答案。如果我们固定j的下标是不是就是找i j符合s[i] s[j] - k的个数实现如下先计算前缀和然后使用 mp 统计s[i]的值的个数这里我们在找符合i j符合s[i] s[j] - k的个数所以我们不能在计算前缀和的时候统计进去我们在遍历j的时候把前j个的s[i]统计进去方便我们查找。publicintsubarraySum(int[]nums,intk){intans0;int[]snewint[nums.length1];MapInteger,IntegermpnewHashMap(nums.length1,1);for(inti0;inums.length;i){s[i1]s[i]nums[i];// 前缀和}mp.put(s[0],1);// 很关键和为 0 的 i 有一个即 0for(intj0;jnums.length;j){// 统计 s[i] s[j] - k 的个数, 如果 mp 没有那就是 0 呗ansmp.getOrDefault(s[j1]-k,0);// 把当前的 s[j] 放入 mp方便后面使用if(mp.containsKey(s[j1])){mp.put(s[j1],mp.get(s[j1])1);}else{mp.put(s[j1],1);}}returnans;}代码能优化吗能有两点mp.containsKey这个判断含义是如果存在就加 1不存在就设置 1但是这么写啰嗦了有一个函数可以替代mp.merge(s[j1],1,Integer::sum);// 含义是如果 s[j 1] 存在就把它和 1 进行加和不存在就赋值 1// 也等价于mp.put(s[j1],mp.getOrDefault(s[j1],0)1);前缀和这里我们是先计算出来的但是你看我们每次循环实际上只用到了s[j 1]也就是说我们不用提前计算用的时候算出来s[j 1]即可最终代码可以写为publicintsubarraySum(int[]nums,intk){intans0;ints0;MapInteger,IntegermpnewHashMap(nums.length1,1);mp.put(s,1);for(intj0;jnums.length;j){snums[j];ansmp.getOrDefault(s-k,0);mp.merge(s,1,Integer::sum);}returnans;}最大子数组和前缀和还是考虑前缀和因为是子数组 和的方式同理我们假设j i是不是要找的是s[j] - s[i]的最大值如果j固定是不是就是找s[i]的最小值publicintmaxSubArray(int[]nums){// s[j] - s[i] 最大s[j] 固定找最小的 s[i]int[]snewint[nums.length1];intansInteger.MIN_VALUE;intminInteger.MAX_VALUE;for(inti0;inums.length;i){s[i1]s[i]nums[i];minMath.min(min,s[i]);ansMath.max(ans,s[i1]-min);}returnans;}能小优化一下空间复杂度publicintmaxSubArray(int[]nums){// s[j] - s[i] 最大s[j] 固定找最小的 s[i]ints0;intansInteger.MIN_VALUE;intminInteger.MAX_VALUE;for(inti0;inums.length;i){minMath.min(min,s);ansMath.max(ans,snums[i]-min);snums[i];}returnans;}贪心这里用贪心的思路是什么比如前面的和l r j是不是如果[l, r]的和小于0那我的最大和子序列[l, j]一定是不包含[l, r]的因为以后任何想从l开始一路延伸到更右边的位置的方案都不如直接丢掉[l, r]所以左边界就需要从r 1开始了。这里还得稍微留意一下哈我们在这里说是[l, r]小于 0直接扔了实际上如果存在l x r但是[x, r]大于 0 呢是不是还得保留。但实际算法设计上不会出现这个问题的因为如果有[x, r]大于 0 了就说明[l, x]一定小于 0在判断到x到时候就已经丢弃了。举例[-2, 1, 3]虽然-2 1 0但是我们并不是抛弃了-2, 1而是在发现-2 0时抛弃了-21还是保留了。所以有两种情况一是刚开始计算前面和的时候就都是负数这直接就抛弃了比如[-1, -1, -2, 0]判断第一个数你就知道不该要第二个也是不该要第三个也是。另一种是[2, 3, -1, -5]第一个数要第二个数要第三个也得要因为2 3 -1 4为了要前面的 2、3-1 也得拿着因为总的算下来还是值的但是到 -5 的时候算下来就不值了为了要 2、3还得拿着 -1、-5是亏的所以整块就丢弃了。贪心实现如下publicintmaxSubArray(int[]nums){ints0;intansInteger.MIN_VALUE;intpreSum0;intcurSum0;for(inti0;inums.length;i){curSumnums[i];if(preSum0){curSum-preSum;}ansMath.max(ans,curSum);preSumcurSum;}returnans;}合并区间思路是排序为什么会想到排序呢如果不排序当我们看到[1, 3]时我们并不知道完整的集合里面谁是和它重叠的以及后续我们往后继续看数组元素的时候也不知道它前面有没有区间是重叠的后面有没有。发生重叠的条件是什么呢start j ≤ end i and start j ≥ start i \text{start}_j \le \text{end}_i \ \text{and} \ \text{start}_j \ge \text{start}_istartj​≤endi​andstartj​≥starti​也就是start j \text{start}_jstartj​在[ start i , end i ] [\text{start}_i, \text{end}_i][starti​,endi​]中。如果我们按照起始位置排序之后我们只需要判断紧邻的区间是否和前面的这个区间重叠如果重叠就合并依次往后判断即可。publicint[][]merge(int[][]intervals){// 排序Arrays.sort(intervals,(a,b)-Integer.compare(a[0],b[0]));Listint[]ansnewArrayList();// 初始区间ans.add(newint[]{intervals[0][0],intervals[0][1]});for(int[]interval:intervals){intLinterval[0];intRinterval[1];if(Lans.get(ans.size()-1)[1]){// 出现一个不重叠的区间则是一个新的区间ans.add(newint[]{L,R});}ans.get(ans.size()-1)[1]Math.max(R,ans.get(ans.size()-1)[1]);// 发生合并时更新 end 即可}returnans.toArray(newint[ans.size()][]);}