一道有意思的面试题

发布时间:2019-07-24 22:00:23发布者:Mr.Zhang阅读(316)

题目

  • 给定一个数组,值全是正数,请返回累加和为给定值k的最长子数组长度。

  • 给定一个数组,值可以为正、负和0,请返回累加和为给定值k的最长子数组长度。


思路:
对于题目一,要求出数组中累加和为k的最长子数组长度,注意是子数组,不是子序列,子数组必须连续。
举个栗子,数组为:1 2 1 4 5 3 2 1,给定k值为8,所以该题的解为4,即子数组 1 2 1 4
应该怎么来做呢?暴力枚举所有的子数组显然不是最优解,所以此时我们可以采用一个套路,套路名为:滑动窗口,具体是什么意思呢?

先建立两个指针变量left和right,和一个整数sum用于计算两个两个指针变量之间的元素和,一个整数max_length用来记录当sum等于target时窗口的长度。

这两个指针变量首先指向数组第0号元素,sum计算元素和,并与target比较,若小于target,则right++,若大于target,则left++(想想为什么),当sum==target时,记录窗口的长度,并更新max_length

循环的条件时left <= right && left < length && right < length

这样就可以找到所有和为k的子数组且记录最长的子数组的长度

代码如下:

int theLengthOfLongestSubArray(int s[], int length, int target) 
{
    if (length==0||target==0)
    {
        return 0;
    }
    int left = 0, right = 0;
    int sum = 0;
    int max_length = 0;
    while (left<=right&&right<length&&left<length)
    {
        for (int i = left; i <= right; i++)
        {
            sum += s[i];
        }
        if (sum < target)
        {
            right++;
        }
        else if(sum > target)
        {
            left++;
        }
        else
        {
            max_length = max_length > (right - left + 1) ? max_length : (right - left + 1);
            right++;
        }
        sum = 0;
    }
    return max_length;
}

思路
对于题目二,此时数组中存在负数和零,所有题一的方法就不适用了,因为Right向右走不一定会使Sum增加,而Left向右走也不一定能够使Sum减少,所以我们要使用新的方法来解决这个问题。

还记得我们上一题leetcode32关于求解一个由‘(’和‘)’组成的字符串求解最长有效字串长度的题吗?那道题使用的是动态规划的思路,即以字符串每个字符结尾来计算此时最长有效长度,我们或许可以借鉴这个思路

举个栗子,如果我们以一个数组中的每个数结尾,求其之前的所有数到该数的累加和记为sum,同时准备一张map表,将第一次出现和为sum的数组的下标连同sum记录到这张表中,(仔细想想为什么是第一次),即map[sum] = index,再查询这张表是否存在key = sum-k的情况,如果有,则数组从map[sum-k]+1到index的所有数加起来就等于k(仔细想想为什么)。

即题目要我们求和为k的数组,我们可以去求sum-k的数组,之后从sum-k到sum的数组的和就为k了,此时既可以更新最长数组长度。

代码如下:

int theLengthOfLongestSubArray_2(int s[], int length, int target) 
{
    if (s==nullptr||length==0)
    {
        return 0;
    }
    map<int, int>mymap;
    mymap[0] = -1;//很关键的一点
    int len = 0;
    int sum = 0;
    for (int i = 0; i < length; i++)
    {
        sum += s[i];
        if (mymap.count(sum-target)) //如果存在sum-target的值,即找到一段数组和为k,更新len的值
        {
            len = len > (i - mymap[sum - target]) ? len : (i - mymap[sum - target]);
        }
        if (mymap.count(sum)==0)//如果sum是第一次出现,便将它记录下来
        {
            mymap[sum] = i;
        }
    }

    return len;
}

等等,代码里面好像有什么奇怪的东西混进来了??

mymap[0] = -1;

这是个什么鬼?为什么要给-1位置的累加和设置为0。
这就要我们从上述算法的原理入手,比如:
Σarr(0……i) = sum(i>=0)

而 Σarr(0……j) = sum-k(j>=0)

所以 Σarr(j+1……i) = k

而此时j+1总是大于或等于1的,即忽略了从0位置开始的那些子数组,而如果我们向map中插入一条记录即-1位置的累加和为0,此时j+1>=0了,补充了从0开始的那些子数组。





本文转自博客园,原文地址:https://www.cnblogs.com/MrSecond/p/11239251.html