和为k的连续子数组系列题

2021-08-12

和为k的连续子数组系列题

整理了一下和为k的子数组的题单。

1. 和为k的连续子数组

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

题目链接：https://leetcode-cn.com/problems/subarray-sum-equals-k/

解法一：前缀和+暴力，时间复杂度：O(n^2)

class Solution {
    public int subarraySum(int[] nums, int k) {
        // 暴力
        int len = nums.length;
        int ans = 0;
        for(int i = 0; i < len; i++){
            int sum = 0;
            for(int j = i; j < len; j++){
                sum += nums[j];
                if(sum == k){
                    ans++;
                }
            }
        }
        return ans;
    }
}

解法二：哈希表+前缀和，时间复杂度：O(n)

class Solution {
    public int subarraySum(int[] nums, int k) {
        int len = nums.length, sum = 0, ans = 0;
        // map保存的是（前缀和，出现的次数）
        HashMap<Integer,Integer> map = new HashMap<>();
        // 利用前缀和的思想可知sum[i,j] = preSum[j] - preSum[i-1] == k => preSum[j] - k = preSum[i-1] i < j
        // 在知道preSum[j]的情况下，只需要判断preSum[i-1]即preSum[j] - k出现了多少次
        // 由于我们的sum是累加的，可以保证连续。
        map.put(0,1);
        for(int j = 0; j < len; j++){
            sum += nums[j];
            if(map.containsKey(sum - k)){
                ans += map.get(sum - k);
            }
            map.put(sum, map.getOrDefault(sum,0) + 1);
        }
        return ans;
    }
}

2. 连续数组

题目描述：给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

题目链接：https://leetcode-cn.com/problems/contiguous-array/

题目思路：我们可以将0视为-1，这样的话就转化为和为0的最长子数组。而且如果从第i 个数开始，第j 个数为止，前缀和恰好相同，就表明子数组(i,j]内包含的0与1个数相同。注意本题求的是长度，所以哈希表存储的键值对是前缀和:索引，因为要求最长的，因此如果某个前缀和之前出现过，那么就不需要更新他的位置了，之前出现过表明更靠前。

看上图可以帮助我们更好的理解。上图中A-C中（不包含A，包含C）有3个0、3个1。

class Solution {
    public int findMaxLength(int[] nums) {
        int len = nums.length, sum = 0, ret = 0;
        // map用来保存 （前缀和，位置）
        HashMap<Integer,Integer> map = new HashMap<>();
        map.put(0, -1);
        for(int i = 0; i < len; i++){
            if(nums[i] == 0){
                sum += -1;
            }else{
                sum += nums[i];    
            }
            if(map.containsKey(sum)){
                ret = Math.max(ret, i -  map.get(sum));
            }else
                map.put(sum, i);
        }
        return ret;
    }
}

3. 最大子数组之和为k

题目描述：给一个数组nums和目标值k，找到数组中最长的子数组，使其中的元素和为k。如果没有，则返回0。

题目链接：https://www.lintcode.com/problem/911/

题目思路：基本和以上第2题思路相同。

public class Solution {
    /**
     * @param nums: an array
     * @param k: a target value
     * @return: the maximum length of a subarray that sums to k
     */
    public int maxSubArrayLen(int[] nums, int k) {
        // Write your code here
        int len = nums.length,sum = 0, ret = 0;
        HashMap<Integer,Integer> map = new HashMap<>();
        map.put(0, -1);
        for(int i = 0; i < len; i++){
            sum += nums[i];
            if(map.containsKey(sum - k)){
                ret = Math.max(ret, i - map.get(sum - k));
            }
            // 注意更新sum的位置
            if(!map.containsKey(sum))
                map.put(sum,i);
        }
        return ret;
    }
}

4. 最小子数组和为k

题目描述：给定一个整数数组和一个整数k，你需要找到和为k的最短非空子数组，并返回它的长度。如果没有这样的子数组，返回-1.

题目链接：https://www.lintcode.com/problem/1844/

public class Solution {
   
    public int subarraySumEqualsKII(int[] nums, int k) {
        // write your code here
        int len = nums.length, sum = 0, ret = Integer.MAX_VALUE;
        HashMap<Integer,Integer> map = new HashMap<>();
        map.put(0, -1);
        for(int i = 0; i < len; i++){
            sum += nums[i];

            if(map.containsKey(sum - k)){
                ret = Math.min(ret, i - map.get(sum - k));
            }
            // 遇到sum就更新，这样能保证最短
            map.put(sum, i);
        }
        return ret == Integer.MAX_VALUE ? -1 : ret;
    }
}