leetcode 209/lintcode 406 二分法

这个题要注意的是题目要求是sum>=s就可以，没说非要找相等的子数列。我就是因为没看清题意浪费很多时间。
这个题首先想到的是O(n)方法，就是用左右指针控制判断区域。

方法二：二分法解题，虽然这样会比第一种方法慢很多，但是后面的follow up要求做了呀，所以你还是乖乖做把~~
通过这个题找到二分法的统用套路： while(left<right) 如果后面要用到相等的情况，在最后再加上一条判断就可以了，这样避免了不必要逻辑错误~

• code C++:

////O(n) my
//int minSubArrayLen(int s, vector<int>& nums) {
//  int left = 0, right = 0, sum = 0;
//  int n = nums.size();
//  int ans = INT_MAX;
//  while (right < n) {
//      while (sum < s&& right < n) {
//          sum += nums[right++];
//      }
//
//      while (sum >= s) {
//          ans = min(ans, right - left);
//          sum = sum - nums[left++];
//      }
//  }
//  return ans == INT_MAX ? 0 : ans;
//}

////O(n logn)
//my
int minSubArrayLen(int s, vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i - 1] + nums[i - 1];
    }

    int ans = INT_MAX;
    for (int i = 0; i <= n; i++) {
        int left = i; int right = n;
        int t = dp[i] + s;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (dp[mid] < t)
                left = mid + 1;
            else {
                ans = min(ans, mid - i);
                right = mid;
            }
        }
        if (dp[left] >= t)
            ans = min(ans, left - i);
    }
    return ans == INT_MAX ? 0 : ans;
}