大廠面試真題詳解：和大于S的最小子數組

給定一個由 n 個正整數組成的數組和一個正整數 s ，請找出該數組中滿足其和 ≥ s 的最小長度子數組。如果無解，則傳回 -1。

線上評測位址：

領扣題庫官網 樣例 1:

輸入: [2,3,1,2,4,3], s = 7
輸出: 2
解釋: 子數組 [4,3] 是該條件下的最小長度子數組。           

樣例 2:

輸入: [1, 2, 3, 4, 5], s = 100
輸出: -1           

解題思路

• 如果采用暴力解法，用變量i從左到右周遊數組，變量j從i到數組尾部周遊，将i到j内的元素周遊求和，找到和大于s的最短數組。時間複雜度為O(n^3)。
• 對暴力法進行優化，使用累加器來進行求和，那麼求和這步隻需要O(1)。總的時間複雜度為O(n^2)。
• 使用二分法來繼續優化，對于左端點i，我們用二分法來尋找j。首先建立字首和數組sum，對于每個i，在i到尾部這段區間上二分查找，找到滿足sum[j] - sum[i] > S的最小的j。總的時間複雜度為O(nlog(n))。
• 最優解法是采用滑窗。我們用 2 個指針，一個指向子數組開始的位置，一個指向數子組最後的位置，并維護區間内的和 curr_sum大于等于s 同時數組長度最小，實時更新最短的數組長度res。時間複雜度為O(n)。

算法流程

• 初始化左指針left和右指針right指向0，子數組和curr_sum為0。
• 右指針right周遊nums數組，即不斷移動滑窗右端
  • 更新子數組的和，curr_sum += nums[right]
  • 當子數組和滿足條件，即curr_cum >= s時
    • 更新res = min(res, right - left + 1)，其中right - left + 1是目前子數組的長度
    • curr_sum -= nums[left]，然後左指針右移，繼續判斷目前數組和是否滿足條件
• 傳回res

複雜度分析

• 時間複雜度：O(n) 。每個指針移動都需要O(n)的時間。每個元素至多被通路兩次，一次被右端點通路，一次被左端點通路。
• 空間複雜度：O(1)。變量隻需要常數空間。

public class Solution {
    /**
     * @param nums: an array of integers
     * @param s: An integer
     * @return: an integer representing the minimum size of subarray
     */
    public int minimumSize(int[] nums, int s) {
        int left = 0, currSum = 0, res = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right ++) {
            // 滑窗右邊界擴張
            currSum += nums[right];
            // 滿足條件
            while (currSum >= s) {
                // 更新res
                res = Math.min(res, right - left + 1);
                // 滑窗左邊界收縮
                currSum -= nums[left];
                left ++;
            }
        }
        return res == Integer.MAX_VALUE ? -1: res;
    }
}           

更多題解參考：

九章官網solution