小编Jha*_*nia的帖子

Google编程面试中提到了这个问题.我想到了两种相同的方法:

1. 找到所有长度的子序列.这样做的同时计算两个元素的和,并检查它是否等于k.如果是的话,打印是,否则继续搜索.这是一种蛮力的方法.

2. 以非递减顺序对数组进行排序.然后从右端开始遍历数组.假设我们有排序数组{3,5,7,10},我们希望总和为17.我们将从元素10开始,索引= 3,让我们用'j'表示索引.然后包括当前元素并计算required_sum = sum - current_element.之后,我们可以在数组[0-(j-1)]中执行二进制或三进制搜索,以查找是否存在其值等于required_sum的元素.如果我们找到这样一个元素,我们可以打破,因为我们找到了长度为2的子序列,其总和是给定的总和.如果我们没有找到任何这样的元素,那么减小j的索引并重复上述步骤以得到长度=长度为1的子阵列,即在这种情况下通过排除索引3处的元素.

在这里,我们认为数组可能有负整数和正整数.

你能提出比这更好的解决方案吗？DP解决方案可能吗？一种可以进一步降低时间复杂度的解决方案.

换句话说，找到数组中不存在的最低正整数。该数组也可以包含重复项和负数。Stripe在编程采访中曾问过这个问题。我为以下设计了一种解决方案：

#include<bits/stdc++.h>
using namespace std;

int main(){
    int arr[]={1,-1,-5,-3,3,4,2,8};
    int size= sizeof(arr)/sizeof(arr[0]);
    sort(arr, arr+size);
    int min=1;

    for(int i=0; i<size; i++){
        if(arr[i]>min) break;
        if(arr[i]==min) min=min+1;
    }
    cout<<min;
    return 0;
}

在这里，我首先对数组进行排序，然后遍历数组一次。在遍历数组之前，我已将名为“ min”的变量初始化为1。现在，在遍历数组时，当我们获得等于min的整数时，我们只需增加min的值即可。这样可以确保min变量保存尚未出现的最新的最小正整数。您能想到更好的方法吗？提前致谢。

问题是找出给定DNA序列中出现不止一次的所有长度为k的序列.我找到了一种使用滚动散列函数的方法,其中对于每个长度为k的序列,计算散列并将其存储在映射中.要检查当前序列是否是重复,我们计算它的散列并检查哈希映射中是否已存在散列.如果是,那么我们在结果中包含此序列,否则将其添加到哈希映射中.

滚动哈希在这里表示,由一个滑动窗口移动到下一个序列的时候,我们使用之前序列的散列,我们删除以前的序列的第一个字符的贡献,并添加新添加的焦炭的贡献方式即新序列的最后一个字符.

Input: AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT
and k=10
Answer: {AAAAACCCCC, CCCCCAAAAA}

这个算法看起来很完美,但我不能去做一个完美的哈希函数,以避免碰撞.如果有人能够在任何情况下解释如何制作完美的哈希值,那将是一个很大的帮助,最重要的是在这种情况下.