MENU

LeetCode325.最大子数组之和为k

August 22, 2018 • Read: 1925 • LeetCode

题目链接:LeetCode325


这道题暴力很好做,但是找技巧确实不好想,首先假设这么一个场景,从下标为0到下标为100,和sum = 2000,假设我们要求的目标k=800,那么我们只要知道从0开始,最早出现的下标i,使得0到i之间的和为1200,这样就能保证i+1到1000的和为800,同时还能保证这个长度是以1000结尾的最大的长度

建立一个Map,key存放的是和,value存放的是第一次出现该和的下标,后面如果再出现直接跳过。

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

总结

很多类似的变形题,比方说,一个数组中有奇数有偶数,求奇数和偶数个数相等的最长子数组的长度,这个就把奇数看作1,把偶数看作-1,求和为0的最长子数组的长度;再比方说,一个数组中有0,1,2,求0,1,2个数相等的最长子数组的长度,也是一样的,0还是0,把1看成1,2看成-1,最终叶转换为求和为0的最长子数组的长度。

Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment

已有 1 条评论
  1. 子数组累加和为aim(小于等于aim)的三个问题 - 算法网

    [...]子数组累加和为aim(小于等于aim)的三个问题 - 算法网 算法网首页精品教程数据结构时间复杂度空间复杂度树二叉查找树满二叉树完全二叉树平衡二叉树红黑树B树图队列散列表链表算法基础算法排序算法贪心算法递归算法动态规划分治算法回溯法分支限界法拓扑排序字符串相关算法数组相关算法链表相关算法树相关算法二叉树相关算法LeetCodeOnline Judge剑指offer架构设计设计模式创建型单例模式[...]