通用思想：

按照和是否等于k的情况，可以分为***++查找问题、搜索问题++***（本质上是一样的），因此可以用++特殊数据结构来存储和查找（哈希表、前缀数组）、暴力搜索、递归、分治，回溯法其实就是暴力法，进一步地记忆化搜索、动态规划来处理++。

先考虑该问题是否可以用特殊的数据结构来解决，再考虑算法。

更进一步地，按照题目给定数组的条件，使用滑动窗口、双指针、二分法都可以来解决，通常辅以前缀数组、后缀数组会大大简化。

通过前缀数组，区间和可以转换为两个前缀数组的差。

0-1背包问题就是动态规划的运用。

注意数组中是否有负数的情况又不一样，数组中均为正数的情况，会更简单些，往往可以直接用二分或者滑动窗口。

有负数时，可以考虑用单调栈、队列等辅助的数据结构，来进行滑动窗口。（leetcode862）

和为k的子数组：

相对于原问题更简单，附加了连续性，即缩小了范围，增加了遍历条件线索。

方法：

双层循环O(N2)

前缀和+map。这个表对应的映射项可以是最早出现这个sum的index（以此来求最长子数组的长度），也可以是对应这个sum出现的次数（对应求满足条件的子数组个数）。

变式：

在原问题基础上，增加了数组中的值均为正数的约束，因此数组和天然存在了递增的特性，可以采用滑动窗口的思想。

子数组和小于等于定值

子数组中均为正整数：

子数组中有负数：

这个题目应该是求和小于等于K的最长子数组。按理说，存在负数的话，是不能使用滑动窗口的，但是下面的解法借助两个辅助数组

使用两个辅助数组：min_value、min_index：min_value[i]表示以i位置开始往后加的最小累加和；min_index表示min_value对应的最小累加和的右边界；这两个辅助数组是能够在O(n)时间复杂内计算出来的：倒序遍历，min_value[i] 只需要判断min_value[i+1]的值是不是负数，如果是负数就加上，不是就到本身这里结尾。得到这样一个数组以后我们就可能轻易得到从某一个位置开始和最小的子数组。

有了这两个辅助数组以后，就可以采用滑动窗口的思想，左右两个指针都不回退，右指针以上面辅助数组进行累加，左指针正常遍历，使得总体的时间复杂度为O(n)，参考LeetCode总结——和为定值 | Sixzeroo (liuin.cn)