和為K的子數(shù)組

給定一個(gè)整數(shù)數(shù)組和一個(gè)整數(shù) k，你需要找到該數(shù)組中和為 k的連續(xù)的子數(shù)組的個(gè)數(shù)。

示例 1 :

輸入:nums = [1,1,1], k = 2
輸出: 2 , [1,1] 與 [1,1] 為兩種不同的情況

方法一：暴力

public int subarraySum(int[] nums, int k) {
    int ans = 0;
    for (int i = 0; i < nums.length; i++) {
        int sum = 0;
        for (int j = i; j < nums.length; j++) { //中間可能有抵消的元素，所以要加要尾
            sum += nums[j];
            if (sum == k) {
                ans++;  
            }
        }
    }
    return ans;
}

時(shí)間復(fù)雜度O(n²)

方法二：前綴和

public int subarraySum(int[] nums, int k) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int ans = 0;
    int[] leftSum = new int[nums.length + 1];//leftSum[0] = 0
    for (int i = 0; i < nums.length; i++) {
        leftSum[i + 1] = leftSum[i] + nums[i];
    }
    for (int i = 0; i < nums.length; i++) {
        for (int j = i; j < nums.length; j++) {
            if (leftSum[j + 1] - leftSum[i] == k) { //注意下標(biāo)偏移
                ans++;
            }
        }
    }
    return ans;
}

時(shí)間復(fù)雜度O(n²)

方法三：前綴和+HashMap

public int subarraySum(int[] nums, int k) {
    int ans = 0;
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);
    int sum = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        if (map.containsKey(sum - k)) {
            ans += map.get(sum - k);
        }
        map.put(sum, map.getOrDefault(sum, 0) + 1);
    }
    return ans;
}

時(shí)間復(fù)雜度O(n)

長度最小的子數(shù)組

給定一個(gè)含有 n個(gè)正整數(shù)的數(shù)組和一個(gè)正整數(shù) target** 。**

找出該數(shù)組中滿足其和≥ target的長度最小的 連續(xù)子數(shù)組 [nums<sub>l</sub>, nums<sub>l+1</sub>, ..., nums<sub>r-1</sub>, nums<sub>r</sub>] ，并返回其長度。如果不存在符合條件的子數(shù)組，返回 0 。

示例 1：
">輸入：target = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數(shù)組 [4,3] 是該條件下的長度最小的子數(shù)組。

示例 2：

輸入：target = 4, nums = [1,4,4]
輸出：1

示例 3：

輸入：target = 11, nums = [1,1,1,1,1,1,1,1]
輸出：0

方法一：前綴和+二分查找
由于都是整數(shù)，所以前綴和遞增，所以可以使用二分查找，如果題目條件是等于target直接判斷是否存在

public int minSubArrayLen(int target, int[] nums) {
    // +1是為了map[0] = 0,預(yù)先存和為0
    int[] map = new int[nums.length + 1];
    int sum = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        map[i + 1] = sum;
    }
    int minLen = Integer.MAX_VALUE;
    for (int i = 0; i < nums.length; i++) {
        // 在前綴和中找到最后一個(gè)小于等于s的位置
        int s = map[i + 1] - target;
        // +2是右開+1，map的index偏移+1
        int left = 0, right = i + 2;
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (map[mid] <= s) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        // 如果沒找到，則考慮從頭開始是否滿足target
        if (map[i + 1] >= target) {
            minLen = Math.min(minLen, i - (left - 1));
        }
    }
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

方法二：滑動(dòng)窗口

public int minSubArrayLen(int target, int[] nums) {
    int left = 0, right = 0;
    int sum = 0;
    int minLen = Integer.MAX_VALUE;
    while (right < nums.length) {
        sum += nums[right];
        while (sum >= target) {
            minLen = Math.min(minLen, right - left + 1);
            sum -= nums[left];
            left++;
        }
        right++;
    }
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}