Subarray with given sum

We have to find total number of Subarray with given sum k from array nums .

Array of integers दे रखा हमे वो sub-array निकालना है जिनके elements का total sum(योग) given sum के बराबर हो I

For example:

Input:

A[] = { 3, 4, -7, 1, 3, 3, 1, -4 }
Sum = 7

Output:

Subarrays with given sum are :

{ 3, 4 } ,

{ 3, 4, -7, 1, 3, 3 } , { 1, 3, 3 } ,{ 3, 3, 1 }

इसलिए आउटपुट में हमे total sub-array return करना है ।

Constraints:

• 1 <= nums.length <= 2 * 104
• -1000 <= nums[i] <= 1000
• -107 <= k <= 107

हम आपको recommend करते हैं की अगर आपने ये question अभी तक try नहीं किया है तो पहले इसे try कर लें।फिर solution देखें।

सबसे सरल solution तो ये होगा की सारे sub-array का sum निकाले और जिन sub-array का sum == target sum हो वहां count को increase करते रहें। पर यहाँ problem ये है की Time of complexity इस algorithm का O(n²) हो जाएगा।

Subarray with given sum code – Approach 1:

class Solution {
    public int subarraySum(int[] nums, int k) {
        int total = 0;
        for (int i = 0; i < nums.length; i++) {
            int currentSum = 0;
            for (int j = i; j < nums.length; j++) {
                currentSum = currentSum + nums[j];
                if (currentSum == k) {
                    total++;
                }
            }
        }
        return total;
    }
}

Approach 2:

हम यहाँ Hashing का concept भी use कर सकते हैं । Solution 1 से, हम जानते हैं कि इस problem को solve करने की कुंजी SUM [i, j] है। इसलिए यदि हम SUM [0, i – 1] और SUM [0, j] को जानते हैं, तो हम आसानी से SUM [i, j] प्राप्त कर सकते हैं। इसे प्राप्त करने के लिए, हमें केवल array को iterate करने की आवश्यकता है, और current sum की calculation करें और सभी देखे गए PreSum की संख्या को एक HashMap में save कर ले।

Time of complexity: O(n)

Space complexity: O(n)

class Solution {
    public int subarraySum(int[] nums, int k) {
        int total = 0;
        Map<Integer,Integer> prefixSumMap= new HashMap<Integer,Integer>();
        int currentSum = 0;
        int n = nums.length;
        prefixSumMap.put(0,1); //initializing map for storing cumulative sum = 0 with count 1 because we are going to use this map for storing prefix sum
        for (int i=0; i<n; i++) {
            currentSum = currentSum + nums[i];
            if (prefixSumMap.containsKey(currentSum - k)) {
                total = total + prefixSumMap.get(currentSum - k);
            }
           prefixSumMap.put(currentSum, prefixSumMap.getOrDefault(currentSum, 0)+1);
        }
        return total;
    }
}

तो हम देख सकते हैं given constraints पर दोनों approach कितना टाइम ले रहें हैं ।

आपका सुझाव हमारे लिए प्रेरणादायी होगा ।

Next topic: