Is it possible to solve this using two pointers?


  • 0
    D

    I was trying to solve this using 2 pointers but my solution fails to pass some solutions. The idea is to have a sliding window and track the window using start and end pointers which are the indices of the start of the subarray and the end of the subarray respectively.

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

        if(nums.length == 1)
            return (nums[0] == k) ? 1 : 0;
        
        int start = 0, end = 1;
        int sum = nums[0], ways = 0;
    
        while(start <= end){ //end < nums.length && start < nums.length){
            if(sum == k){
                ways++;
                if(start < nums.length){
                    sum -= nums[start];
                }
                start++;
                
                if(end < nums.length){
                    sum += nums[end];
                    end++;
                }
            }
            else if(sum < k && end < nums.length){
                sum += nums[end];
                end++;
            }
            else if(start < nums.length){
                sum -= nums[start];
                start++;
            }
        }
        return ways;
    }
    

    }
    It does not pass all scenarios currently. But I am curious to know if anyone has solved it using the approach of two pointers and sliding window.
    Thanks.


  • 0
    B

    It may become quite difficult to use sliding window, as the elements of the array are not all positives, so, making end increase doesn't mean the sum increase, and making start doesn't mean the sum decrease.


  • 0
    T

    The reason why your solution cannot be correct and do O(n): ways++ this is a clear indicator. You need to find each subarray. And there can be n * (n + 1) / 2, e.g.: num=[0, 0, 0, 0], k=0 .

    Two pointers was my first idea for this task as well. The reason, why i discarded it is that for straightforward application of TP there should be no more than 1 sub-array per beginning or end. It's not the case for this problem.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.