和为K的连续子数组

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

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

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
}

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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# max length of the subarray sum = k
# @param arr int整型一维数组 the array
# @param k int整型 target
# @return int整型
#
class Solution:
    def maxlenEqualK(self , arr: List[int], k: int) -> int:
        # write code here
        count_length = 0
        for i in range(len(arr)):
            res = arr[i]
            for j in range(i + 1, len(arr)):
                res += arr[j]
                if res == k:
                    if j >= count_length:
                        count_length = j - i + 1
        return count_length

class Solution:
    def maxlenEqualK(self , arr: List[int], k: int) -> int:
        sum_index_map = {0:-1}
        sum = 0
        max = 0
        for i in range(0,len(arr)):
            sum = sum + arr[i]
            if (sum - k) in sum_index_map:
                l = i - sum_index_map[sum - k]
                if max < l:
                    max = l
            else:
                if sum not in sum_index_map:
                    sum_index_map[sum] = i
        return max

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# max length of the subarray sum = k
# @param arr int整型一维数组 the array
# @param k int整型 target
# @return int整型
#
class Solution:
    def maxlenEqualK(self , arr: List[int], k: int) -> int:
        # write code here
        if len(arr) == 0:
            return 0
             
        dp = [0 for i in range(len(arr))]
        dp[0] = arr[0]

        # 初始化一个前缀和数列
        for i in range(1, len(dp)):
            dp[i] = dp[i-1] + arr[i]

        m = {}
        m[0] = [-1]
        # 记录前缀和出现的位置
        for i in range(len(dp)):
            if dp[i] in m:
                m[dp[i]].append(i)
            else:
                m[dp[i]] = [i]
        
        # 寻找前缀和减去目标值，得到需要寻找的前缀和
        max_n = 0
        for i in range(len(dp)):
            target_n = dp[i] - k

            if target_n not in m:
                continue

            target_arr = m[target_n]
            for target_index in target_arr:
                if target_index > i:
                    continue
                
                max_n = max(max_n, i-target_index)
        return max_n

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