100_Days_of_LeetCode/Day_37.java at main · vanshcoder99/100_Days_of_LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
// Contiguous Array
class Solution {
    public int findMaxLength(int[] nums) {
        int n = nums.length;
        int maxlen = 0, presum = 0;
        Map<Integer,Integer> mpp = new HashMap<>();
        for(int i=0;i<n;i++){
            presum = (nums[i] == 0) ? presum-1 : presum+1;
            if(presum == 0) maxlen = Math.max(maxlen,i+1);
            else{
                if(mpp.containsKey(presum)){
                    int idx = mpp.get(presum);
                    maxlen = Math.max(maxlen,i-idx);
                }
                else mpp.put(presum,i);
            }
        }
        return maxlen;ā
    }
}


// Subarray Sums Divisible by K
class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        int n = nums.length;
        int cnt = 0,presum=0;
        Map<Integer,Integer> mpp = new HashMap<>();
        mpp.put(0,1);
        for(int i=0;i<n;i++){
            presum+=nums[i];
            int rem = presum%k;
            if(rem<0) rem+=k;
            if(mpp.containsKey(rem)){
                cnt+=mpp.get(rem);
            }
            mpp.put(rem,mpp.getOrDefault(rem,0)+1);
        }
        return cnt;
    }
}


// Continuous Subarray Sum
class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        int n = nums.length;
        int presum = 0;
        Map<Integer,Integer> mpp = new HashMap<>();
        for(int i=0;i<n;i++){
            presum+=nums[i];
            int rem = presum % k;
            if(rem == 0){
                if(i+1 >= 2) return true;
            }
            if(mpp.containsKey(rem)){
                int idx = mpp.get(rem);
                if(i-idx>=2) return true;
            }
            else mpp.put(rem,i);
        }
        return false;
    }
}