O(N) Two Pointers Solution with one loop


  • 0
    J

    Just another implementation. Easier to prove the run time is O(N) as there is only one loop.

    class Solution {
    public:
        int minSubArrayLen(int s, vector<int>& nums) {
            int i = 0;
            int j = 0;
            int minLen = INT_MAX;
            int sum = 0;
            while (i < nums.size() && j <= nums.size()) {
                if (sum >= s) {
                    minLen = min(minLen, j - i);
                    sum -= nums[i++];
                } else if (j == nums.size())
                    break;
                else if (sum < s)
                    sum += nums[j++];
            }
            return (minLen == INT_MAX) ? 0 : minLen;
        }
    };
    

Log in to reply
 

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