Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
1.2 kB
2
Indexable
Never
/* we are storing the sum modulo k in a map/prefix.. if same number in our prefix shows up twice and they
are not consequtive then we have a true */
class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        unordered_map<int,int>map; //sum,index
        map[0]=-1; // when the sum of entire array is exactly equal to k
        int n=nums.size();
        int sum=0;
        for(int i=0;i<n;i++){
            sum+=nums[i];
            if(k!=0) sum=sum%k;
            if(map.find(sum)!=map.end()){
                if(i-map[sum]>1) return true; //not a single number k, if present then in prefix 2 same consequtive no will be there
            }else{
                map[sum]=i;
            }
        }
        return false;
    }
};


python
class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        map={0:-1}
        sum=0
        for i in range(len(nums)):
            sum+=nums[i]
            if k!=0:
                sum=sum % k
            if sum in map:
                if i-map[sum] >1:
                    return True
            else:
                map[sum]=i
        return False             
Leave a Comment