מריה בוטוסוב

יש למצוא כמות תת מערכים שסכום שלהם שווה ל k. nums = [1,1,1], k = 2 תשובה: 2 יכולים להיות מספרים שליליים במערך.

//Solution 1 (with dictionary - see image)
public int SubarraySum(int[] nums, int k) {
    int count = 0, sum = 0;
    Dictionary<int, int> map = new Dictionary<int, int> {
        [0] = 1
    };
    for (int i = 0; i<nums.Length;i++) {
        sum+=nums[i];
        if(map.ContainsKey(sum-k))
            count+=map[sum-k];
        if(map.ContainsKey(sum))
            map[sum]++;
        else
            map.Add(sum, 1);
    }
    return count;
}
 
//Solution 2 (Sliding Window)
public int SubarraySum(int[] nums, int k) {
    int count = 0;
    for(int i=0;i<nums.Length;i++) {
        int sum = nums[i];
        if(sum == k)
            count++;
        for(int j = i+1; j<nums.Length;j++){
            sum+=nums[j];
            if(sum==k)
                count++;
        }
    }
    return count;
}