Leetcode 325) Maximum Size Subarray Sum Equals k

29 Sep 2021 in Algorithms

My Answer

class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        Map<Integer,Integer> m = new HashMap<>();        
        for(int i =1;i<nums.length;i++){
            nums[i]+=nums[i-1];
        }
        int max= Integer.MIN_VALUE;

        for(int i=0;i<nums.length;i++){
            //이부분 중요한듯?
            if(nums[i]==k){
                max =i+1;
            }

            if(m.containsKey(nums[i]-k)){
                max=Math.max(i-m.get(nums[i]-k),max);
            }
            if(!m.containsKey(nums[i])){
                m.put(nums[i],i);
            }
        }

        if(max==Integer.MIN_VALUE){
            return 0;
        }else{
            return max;
        }
    }
}

Other Answer

class Solution {
    public int maxSubArrayLen(int[] nums, int k) {

        final int n = nums.length;
        int sum = 0, max = 0;
        final Map<Integer, Integer> pos = new HashMap<>(n);
        pos.put(0, -1);
        for(int i = 0; i < n; ++i){
            sum += nums[i];
            final Integer lastPos = pos.get(sum - k);
            if(lastPos != null)
                max = Math.max(max, i - lastPos);
            pos.putIfAbsent(sum, i);
        }
        return max;
    }
}

오답

• O(N^2)라서 Time limit 뜸.

class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        int[] add = new int[nums.length];
        add[0]=nums[0];
        int max = Integer.MIN_VALUE;
        
        for(int  i=1;i<nums.length;i++){
            add[i]= add[i-1]+nums[i];
        }
        //int i=nums.length-1;i>=0;i--
        for(int i=nums.length-1;i>=Math.max(0,max);i--){
            int left=0;
            int sum= add[i];
            //while index out of bound check 
            //sum>=k 에서 아래와 같이 조건 바꿨다. 음수도 있으니까!
            while(left<=i && sum!=k){
                sum-=nums[left];
                left++;
            }
            //if(sum==k){return (i+1-left);}가장 큰거 반환하는거니까 이렇게 해도 된다. 어차피 더 작아짐.? 아 아니네! 
            if(sum==k){max=Math.max(i+1-left,max);}
        }
        
        if(max!=Integer.MIN_VALUE){
            return max;
        }else{
            return 0;
        }
    }
}