和为K的连续子数组

class Solution {
public:
    int maxlenEqualK(vector<int>& arr, int k) {
        int ans = 0;
        unordered_map<int, int>m;
        m[0] = -1;//为了解决//如果整个数组和刚好为k，也满足
        int temp = 0;
        for(int i = 0; i < arr.size(); i++) {
            temp += arr[i];
            if(m.find(temp - k) != m.end()) {
                ans = max(ans, i - m[temp - k]);
            }
            if(m.find(temp) == m.end()) {
                m[temp] = i;
            }
        }
        return ans;
    }
};
//全部满足的时候i = n - 1, 那么m[0] = -1, 所以长度为n - 1 + 1 = n

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

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

function maxlenEqualK( arr ,  k ) {
    // write code here
    let sum = 0
    let res = 0
    const map = new Map()
    let len = arr.length
    map.set(0,-1)   //应该从-1位置开始累加,也就是如果任何一个数都不加时，累加和为0, 
    for(let i=0;i<len;i++){
        sum += arr[i]
        let num = sum -k
        if(!map.has(sum)) map.set(sum,i)
        if( map.has(sum -k)) res = Math.max(res, i - map.get(sum -k)) 
    }
    return res
}

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

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 = arr.length;
        Map<Integer, Integer> map = new HashMap<>();
        int[] preSum = new int[len + 1];
        for(int i = 1; i <= len; i++) {
            preSum[i] = preSum[i - 1] + arr[i - 1];
            map.put(preSum[i], i);
        }
        int res = 0;
        // k = pre[j] - pre[i] -> pre[j] = pre[i] + k
        for(int i = 0; i <= len; i++) {
            if(map.containsKey(preSum[i] + k)) {
                res = Math.max(res, map.get(preSum[i] + k) - i);
            }
        }
        return res;
    }
}

对于每个arr[i],将前缀和arr[0]+......+arr[i]，以及i存入字典的key，value中
如果两个前缀和的差值为k，说明它们中间那段子数组的和为k。我们可以通过两个index的差值得到子数组长度
class Solution:
    def maxlenEqualK(self , arr: List[int], k: int) -> int:
        # write code here
        d = {0:-1} # d记录前缀和，以及该前缀和对应的最小index
        total, maxlen = 0, 0 # total记录前缀和，maxlen记录最大长度
        for i in range(len(arr)):
            total += arr[i] # 更新前缀和
            if total-k in d:# 如果有前缀和等于total-k，说明中间连续子串之和为k
                if maxlen < i-d[total-k]: maxlen = i-d[total-k] # 子数组长度为index的差值，并更新maxlen
            if total not in d: # 如果该前缀和已存在，则只保留之前最小的index
                d[total] = i # 如果不存在，将前缀和及其index计入d，
        return maxlen

class Solution:
    def maxlenEqualK(self , nums: List[int], k: int) -> int:
        # write code here
        dic={}
        max_len,sum_v=0,0
        dic[0]=-1
        for i in range(len(nums)):
            sum_v+=nums[i]
            if (sum_v-k in dic.keys()):
                max_len=max(i-dic[sum_v-k],max_len)
            if sum_v not in dic.keys():
                #重复也保留最小的那一个
                dic[sum_v]=i
        return max_len

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

此答案超时
class Solution {
public:
    /**
     * max length of the subarray sum = k
     * @param arr int整型vector the array
     * @param k int整型 target
     * @return int整型
     */
    int maxlenEqualK(vector<int>& arr, int k) {
        // write code here
        int n = arr.size(), ans = 0;
        for (int i = 0; i < n; i++) {
            int sum = 0;
            vector<int> tmp;
            for (int j = i; j < n; j++) {
                sum += arr[j];
                tmp.push_back(arr[j]);
                if (sum == k) {
                    ans = ans > tmp.size() ? ans : tmp.size();
                }
            }
        }
        return ans;
    }
};