2015年7月17日星期五

LeetCode: Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.
For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.
click to show more practice.
More practice:
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

Initial codes:
check each element to get the length that sums to s.
Time complexity O(n*n) Space complexity O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int minLen = 0;
        for(int i = 0; i < nums.size(); i++){
            int len = 0;
            int sum = 0;
            int j = i;
            while(sum < s){
                if(j >= nums.size()) return minLen;
                sum += nums[j];
                len++;
                j++;
            }
            if(i == 0) minLen = len;
            else if(len < minLen) minLen = len;
        }
        return minLen;
    }
};

Sliding window
Set left and right. if sum > s, left++; if sum < s, right++;
O(n)  O(1)
Note:
1)The key is is the terminal condition of while loop.
if(sum < s){}  should run when right<nums.size()
else{} should run when right<nums.size()+1 ==> make sure that the left is able to move when right==nums.size(), right is larger by 1 than current real right.
2) Line 15 will compare current distance to previous distance. We can initiate distance to any value bigger than nums.size(). INT_MAX is also a great idea.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int left = 0;
        int right = 0;
        int sum = 0;
        int dist = nums.size()+1;
        while(1){
            if(sum < s) {
                if(right >= nums.size()) break;
                sum += nums[right];
                right++;
            }
            else {
                if(right - left < dist) dist = right - left;
                sum -= nums[left];
                left++;
            }
        }
        if(dist == nums.size() + 1) return 0;
        return dist;
    }
};

Here the right and left are bigger than the left and right of dist, which makes logics kind of messy.
If we put right++ before calculating sum, logics are easier to understand.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int left = 0;
        int right = 0;
        if(!nums.size()) return 0;
        int sum = nums[0];
        int dist = nums.size()+1;
        while(right < nums.size()){
            if(sum < s){
                right++;
                if(right >= nums.size()) continue;
                sum += nums[right];
            }
            else{
                if(right - left + 1 < dist) dist = right - left + 1;
                sum -= nums[left++];
            }
        }
        if(dist == nums.size() + 1) return 0;
        return dist;
    }
};

This version is easy to understand. However, Line 12 is necessary to make sure the index is within the vector range. Even though this code can pass leetcode test without line 12.

Binary search: O(nlogn)
Frame of binary search:
1
2
3
4
5
6
7
8
9
int bs(int val[], s){
    int left, right;
    while(left <= right){
          int mid = (left + right) / 2;
          if(val[mid] < s) left = mid + 1;
          else right = mid - 1;
    }
  return left;
}

s1: create a sums array, the size is 1 larger than nums array. 
      sums[i] means sum from nums[0] to nums[i-1]
      sums[n] - sums[i] means sum from nums[i] to nums[n-1]

      if the size equals to nums array, we are unable to represent sums starts 0 by sums[n]-sums[0] format.
In this case:
      sums[i] means sum from nums[0] to nums[i]
      sums[n] - sums[i] means sum from nums[i+1] to nums[n]
      Then we've to discuss sum starts from nums[0] separately.

s2: Iterate the sum array to get the minimum size subarray starts with each element.
      In each iteration, using binary search to look for the first element that makes sub sum larger or equal to s. We can get the minimum length with this index. This is my way.
      Actually, this way is not concise enough. Because we have to differentiate the final value is larger than s or just the while loop ends. It is possible that indexes from left to right are all not the answer, which is not satisfy an binary search assumption that there must be a answer between left and right.
     However, we can make things simple if we just return the index left. The while loop always stops when the left is 1 larger than right. If right = mid - 1 (Line 30) never run, left will be larger than the initial right. In other cases, the final left value is the minimum index that makes sum from start to left be more or equal to s. I didn't realize this way. Reference to http://www.cnblogs.com/grandyang/p/4501934.html

Note: Remember framework of binary search
   

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        //creating sum array
        //iterate each element to get the the shortest length with binary search
        vector<int> sums(nums.size()+1);
        sums[0] = 0;
        for(int i = 0; i < nums.size(); i++){
            sums[i+1] = sums[i] + nums[i];
        }
        int minLen = INT_MAX;
        for(int i = 0; i < nums.size(); i++){
            int curLen = getLen(sums, i, s);
            if(curLen == 0) continue;
            if(curLen < minLen) minLen = curLen;
        }
        if(minLen == INT_MAX) return 0;
        return minLen;
    }
    int getLen(vector<int>& sums, int start, int s){
        int left = start;
        int right = sums.size() - 1;
        int len = 0;
        while(left <= right){
            int mid = (left + right) / 2;
            if(sums[mid] - sums[start] < s){
                left = mid + 1;
            }else{
                len = mid -start;
                right = mid - 1;
            }
        }
        return left;
    }
};




Reference:
sliding window method
sliding window with three while loops
binary search method
Giving process of binary search solution

发帖者 时间：

没有评论:

发表评论

订阅： 博文评论 (Atom)