leetcode_325. 和等于 k 的最长子数组长度

给定一个数组 nums 和一个目标值 k，找到和等于 k 的最长连续子数组长度。如果不存在任意一个符合要求的子数组，则返回 0。

示例 1:

输入: nums = [1,-1,5,-2,3], k = 3
输出: 4
解释: 子数组 [1, -1, 5, -2] 和等于 3，且长度最长。
示例 2:

输入: nums = [-2,-1,2,1], k = 1
输出: 2
解释: 子数组 [-1, 2] 和等于 1，且长度最长。
 

提示：

1 <= nums.length <= 2 * 105
-104 <= nums[i] <= 104
-109 <= k <= 109

解题：

首先看到区间求和，很容易想到前缀和

注意：可能存在重复和的问题，只要保留最先出现的和即可，这样序列是最长的

注意： 1，2，3，4，5 -》前缀和-》 0 ， 1， 3， 6， 10， 15。

比如找出区间和为5且最长 ， 那么就是2,3 （6 - 1）

typedef struct{
    int key;
    int index;
    UT_hash_handle hh;
}Hash;



int maxSubArrayLen(int* nums, int numsSize, int k){
    Hash *head = NULL;
    int sum = 0;
    int i = 0;
    Hash *new = (Hash *)malloc(sizeof(Hash));
    new->key = 0;
    new->index = 0;
    HASH_ADD_INT(head, key, new);


    int len = 0;
    int lenmax = 0;
    for(int i = 1; i <= numsSize; i++) {
        sum+=nums[i - 1];
        int value = sum - k;
        Hash *tmp;
        HASH_FIND_INT(head, &value, tmp);
        if(tmp != NULL) {
            len = i - tmp->index;
            lenmax = (len > lenmax) ? len : lenmax;
        }

        //存hash
        HASH_FIND_INT(head, &sum, tmp);
        if(tmp == NULL) {
            Hash *new = (Hash *)malloc(sizeof(Hash));
            new->key = sum;
            new->index = i;
            HASH_ADD_INT(head, key, new);
        }
    }
    return lenmax;

}