1.拿到本题后首先想到的是滑动窗口法设置左右指针l和r右指针一直前进当前子数组和大于等于k时左指针也前进和为k的时候结果计数值1。完整代码如下1. int subarraySum(int* nums, int numsSize, int k) { 2. int l 0, r 0; 3. int cnt 0; 4. int sum 0; 5. 6. while (r numsSize){ 7. sum nums[r]; 8. while (l r sum k){ 9. if (sum k) cnt; 10. sum - nums[l]; 11. } 12. } 13. 14. return cnt; 15. }2.需要注意两点1当子数组和大于k时左指针只前进一步不一定能将和重新变成小于k所以判断代码应该用while而不是if。2内部while循环需要记得加l r边界条件防止越界且一定不能有等于号因为当执行完sum nums[r]后r可能就已经越界了但此时仍在while循环内部此时若允许l r就会导致l越界。3.滑动窗口方法在本题是不正确的因为本题的数组中出现了负数这样就不满足“右指针前进子数组和一定变大左指针前进子数组和一定变小”的核心逻辑。本题正确的方法是使用“前缀和”前缀和sum[i]的含义为数组从0到i所有元素的和。设和为k的子数组为[i, i1,… j]则可以得出sum[j] - sum[i – 1] k经过移项可得sum[i – 1] sum[j] – k所以只需要设置一个哈希表将所有前缀和统计进去每次寻找sum[i – 1]并将它的次数加到结果中即可。4.基于以上思想可写出完整代码如下1. // uthash哈希节点key保存前缀和cnt保存该前缀和出现的次数 2. typedef struct { 3. int key; 4. int cnt; 5. UT_hash_handle hh; 6. } HashEntry; 7. 8. // 子数组和为k的数量前缀和哈希表优化 9. int subarraySum(int* nums, int numsSize, int k) { 10. // 哈希表头初始化为空 11. HashEntry* hashTable NULL; 12. HashEntry* entry NULL; 13. // 初始化前缀和0出现次数为1对应前缀和从0开始的基准 14. entry (HashEntry*)malloc(sizeof(HashEntry)); 15. entry-key 0; 16. entry-cnt 1; 17. HASH_ADD_INT(hashTable, key, entry); 18. // res记录符合条件子数组总数 19. int res 0; 20. // sum记录当前前缀和 21. int sum 0; 22. // 遍历数组计算前缀和 23. for (int i 0; i numsSize; i){ 24. sum nums[i]; 25. // 需要查找的前缀和sum - k 26. int target sum - k; 27. HashEntry* tmp NULL; 28. // 在哈希表查找target前缀和 29. HASH_FIND_INT(hashTable, target, tmp); 30. // 如果存在累加它出现的次数到结果 31. if (tmp) res tmp-cnt; 32. // 查找当前前缀和sum准备更新哈希表 33. HASH_FIND_INT(hashTable, sum, tmp); 34. if (tmp NULL){ 35. // 不存在该前缀和新建节点加入哈希表次数初始化为1 36. tmp (HashEntry*)malloc(sizeof(HashEntry)); 37. tmp-key sum; 38. tmp-cnt 1; 39. HASH_ADD_INT(hashTable, key, tmp); 40. } else { 41. // 已存在次数1 42. tmp-cnt; 43. } 44. } 45. return res; 46. }该算法时间复杂度和空间复杂度均为O(n)。5.需要注意在一开始需要将“前缀和为0”直接放进哈希表中出现次数为1。这样才能保证“当前前缀和正好等于k”时能正确地将结果1。6.本题核心代码中一定要保证“先查找前缀和再添加当前前缀和”。因为当k 0时如果先添加了当前前缀和就会在后续查到自己导致结果错误地多加了1。在本题要做到“用现在的状态去匹配过去的历史记录”每次查找的都是历史记录所以一定要坚守“先查后存”原则。
