关于数组的面试题（持续更新）

数组

子数组的最大和：

子数组要求是必须连续的（可以用动态规划）

通过逐渐推进，时间复杂度为O（N），用两个变量储存。

 

两个无重合部分的子数组的累加和：（时间是O（N），空间是O（N））

通过两个辅助数组L和R，储存正序和逆序的最大子数组的和，然后通过一次扫描在i位置的左边和右边的最大子数组的和的和，求出其最大值。

稍稍优化一下就是可以取消L数组，因为在最后遍历的时候本来就是从左往右，可以在遍历的时候求出即可。

 

未排序正数数组中累加和为定值的最长子数组的长度（双指针）：（时间是N，空间是1）：

 

面试中关于子数组问题的破题点：

必须以每个位置结尾的情况下，应该怎么做。当你得到以i结尾的情况下，通过复用i这个位置的结果，如何得到以i+1结尾的情况。

只关注两个指针L和R之间的累加和，像右边移动的策略：

如果和小于等于规定的值k，R向右移动；

如果和大于规定的值k，L向右移动。

当等于的时候记录最大的长度。

 

未排序数组中累加和不大于定值的最长子数组的长度（数组可正可负可为零）：

创建累加和数组：

1  2   -4  5  -1  2  -1  5

1  3   -1  4  3  5   4  9

1  3   3   4  4  5   5  9 （单调递增可以用二分查找）

必须以i结尾的子数组的长度，看他能够往左扩多远。

               0 1 2 3 4 5 6 7 8

  i   j

要求k>=Sum[i+1~j]，因为Sum[j] = Sum[i] + Sum[i+1~j]

只需要找出Sum[i]+k>=Sum[j]的最小的i，即k>=Sum[i+1~j]，证毕。

因此当处在j位置的时候，只需要找到Sum[i]>=Sum[j]-k,的最大长度即可。

当k=10时，Sum[j] = 4，只需要找到最先出现Sum[i]>=6的时候即可。