和为K的连续子数组

[编程题]和为K的连续子数组

热度指数：19104 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个无序数组 arr , 其中元素可正、可负、可0。给定一个整数 k ，求 arr 所有连续子数组中累加和为k的最长连续子数组长度。保证至少存在一个合法的连续子数组。

[1,2,3]的连续子数组有[1,2]，[2,3]，[1,2,3] ，但是[1,3]不是

数据范围： $1 \le n \le 10^5$ ， $|val| \le 100$ ， $|k| \le 10^9$
要求：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

示例1

输入

[1,-2,1,1,1],0

输出

示例2

输入

[0,1,2,3],3

输出

备注:

算法知识视频讲解

Java

玄鉴

import java.util.*;


public class Solution {
    /**
     * max length of the subarray sum = k
     * @param arr int整型一维数组 the array
     * @param k int整型 target
     * @return int整型
     */
    public int maxlenEqualK (int[] nums, int k) {
       //连续子数组问题
        //前缀和
        int n=nums.length;

        Map<Integer,Integer> map=new HashMap<>();
        int[]pre=new int[n+1];
        for(int i=1;i<=n;i++) pre[i]=pre[i-1]+nums[i-1];
        // a-b=k  
        map.put(0,0);
        int res=1;
        for(int i=1;i<=n;i++){
            if(map.containsKey(pre[i]-k)){
                int j=map.get(pre[i]-k);
                res=Math.max(res,i-j);//i表示个数 
            }
            if(!map.containsKey(pre[i])) map.put(pre[i],i);
        }
        return res;
    }
}

发表于 2022-01-01 16:13:35 回复(0)

Java

花落梦里

public int maxlenEqualK (int[] arr, int k) {
        if(arr==null||arr.length==0) return 0;
        int sum=0;//记录从开头到第i个位置的总和
        HashMap<Integer,Integer>map=new HashMap<>();//记录每一个sum以及它出现的位置
        //基本思想是：如果第i个位置总和为a,第j个位置总和为b,那么在j位置时若发现b-a=k,则a-b之间就是总和为k的子数组
        map.put(0,-1);//初始化总和为0出现的位置
        int len=0;//最大长度
        for(int i=0;i<arr.length;i++){
            sum+=arr[i];
            if(map.containsKey(sum-k)) len=Math.max(len,i-map.get(sum-k));
            if(!map.containsKey(sum)) map.put(sum,i);
        }
        return len;
    }

发表于 2021-03-28 16:48:28 回复(0)

Java

牛客915296776号

public class Solution {
    public int maxlenEqualK (int[] arr, int k) {
        // 前缀和 + 哈希表登记
        int res = 0;
        int preSum = 0;
        Map<Integer, Integer> cache = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            preSum += arr[i];
            if (preSum == k) {
                res = Math.max(res, i + 1);
            }
            if (cache.containsKey(preSum - k)) {
                res = Math.max(res, i - cache.get(preSum - k));
            }
            if (!cache.containsKey(preSum)) {
                cache.put(preSum, i);
            }
        }
        
        return res;
    }
}

发表于 2020-12-17 21:29:25 回复(0)

Java

六娃lw

public class Solution {
    /**
     * max length of the subarray sum = k
     * @param arr int整型一维数组 the array
     * @param k int整型 target
     * @return int整型
     */
    public int maxlenEqualK (int[] arr, int k) {
        // write code here
        if(arr == null){return 0;}
        int len = arr.length;
        int res = 0;
        int sum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);    // 下标-1对应的和为0；
        for(int i = 0; i < len; ++i){
            sum += arr[i];
            int delta = sum - k;
            if(map.containsKey(delta)){
                res = Math.max(res, i - map.get(delta));
            }
            if(!map.containsKey(sum)){
                map.put(sum, i);    // 当map不存在delta时才将sum->i插入哈希表。
            }
        }
        return res;
    }
}

发表于 2020-12-15 16:01:37 回复(1)

Java

牛客196305255号

public int maxlenEqualK (int[] arr, int k) {
         int sum=0;
	 int count=0;
	 for(int j=0;j<arr.length;j++) {
	    sum=0;
	    int tmp=0;
	    for(int i=j;i<arr.length;i++) {
		sum+=arr[i];
		tmp++;
		if(sum==k) {
		    if(count<tmp)
		        count=tmp;
		}
	    }
	    if(count>arr.length-j)
		break;
	 }
	return count;
    }

发表于 2020-12-13 17:21:27 回复(1)

Java

callmejacky

import java.util.*;


public class Solution {
    /**
     * max length of the subarray sum = k
     * @param arr int整型一维数组 the array
     * @param k int整型 target
     * @return int整型
     */
    public int maxlenEqualK (int[] arr, int k) {
        // write code here
        int len = Integer.MIN_VALUE;
        int sum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);// 处理边界值

        // arr[i + 1, ..., j] = k
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            // 只记录第一次的位置，因为要求最长数组
            if (!map.containsKey(sum)) {
                map.put(sum, i);
            }
            // 判断是否需要更新len
            if(map.containsKey(sum - k) && i - map.get(sum - k) > len){
                len = i - map.get(sum - k);
            }
        }

        return len;
    }
}

占个楼，具体原理请参考：https://blog.csdn.net/weixin_43982698/article/details/107135036

编辑于 2020-09-29 14:30:41 回复(0)