和为K的子数组&长度最小的子数组

和为K的子数组

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k的连续的子数组的个数。

示例 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;
}

时间复杂度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) { //注意下标偏移
                ans++;
            }
        }
    }
    return ans;
}

时间复杂度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;
}

时间复杂度O(n)

长度最小的子数组

给定一个含有 n个正整数的数组和一个正整数 target** 。**

找出该数组中满足其和≥ target的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：
">输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

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

示例 3：

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

方法一：前缀和+二分查找
由于都是整数，所以前缀和递增，所以可以使用二分查找，如果题目条件是等于target直接判断是否存在

public int minSubArrayLen(int target, int[] nums) {
    // +1是为了map[0] = 0,预先存和为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++) {
        // 在前缀和中找到最后一个小于等于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;
}

方法二：滑动窗口

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;
}

最后编辑于：2022.02.18 03:05:58