Algorithm(7) hash table and two pointers(1)

整理一下leetcode里面关于 2sum 3sum 的几个问题,后面还补充了几个two pointer的其他问题,主要是longest sub str with at most K distinct characters的问题。关于 hanshtable 以及 two pointer的应用,由于在实现上不像树、图那些在结构上比较复杂,大多是灵光一闪,或者是绕一两个弯就能想到的,面试也是各种常考,应该是要掌握好的一类基本问题。

two sum (1)

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

解法一

由于要先定义好结构体,把index和value的值都存入进去,相比解法二直接使用map代码要稍微多一些,时间复杂度要稍微高一些。

  • 定义Node接口体 对生成vectorvnode对其进行初始化赋值
  • 对vnode 根据每个元素的value值 进行vector排序
  • 采用左右两个指针 向中间靠 发现符合 node1.v+node2.v=target 的两个元素
  • 和大于target则右指针左移 和小于target则左指针右移
  • 取出其index值,index1=min(node1.index,node2.index) index2=max(node1.index,node2.index)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
typedef struct Node{
int index;
int value;
}Node;

bool cmp(Node a, Node b){
return a.value<b.value;
}

class Solution {
int min(int a,int b){
if (a<=b){
return a;
}else{
return b;
}
}
int max(int a,int b){
if (a>=b){
return a;
}else{
return b;
}
}

public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<Node>vnode;
int i,len=nums.size();
for (i=0;i<len;i++){
Node n;
n.index=i+1;
n.value=nums[i];
vnode.push_back(n);
}
sort(vnode.begin(), vnode.end(), cmp);
vector<int>v;
i=0;
int j=nums.size()-1;
while(i<j){
if (vnode[i].value+vnode[j].value==target){
int index1=min(vnode[i].index,vnode[j].index);
int index2=max(vnode[i].index,vnode[j].index);
v.push_back(index1);
v.push_back(index2);
//printf("index1=%d, index2=%d",index1,index2);
break;
}else if (vnode[i].value+vnode[j].value>target){
j--;
}else{
i++;
}
}
return v;
}
};

解法二
利用map的特性,代码简单不少,实质上是很好地利用了map的空间和时间特性。

  • create map < int,int > the lenth of vector is len 其中key值为array中的数字,value值为该数字在序列中的下标
  • 遍历 vector 每次 keyb= nums[i] keya = target - keyb
  • 如果keya不在map中,map[keya]=i
  • 否则,返回 index1=map[keya] index2=map[keyb]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 class Solution {                                                            
public:
vector<int> twoSum(vector<int>& nums, int target) {
int len=nums.size();
int i;
map<int,int>m;
vector<int>v;
i=0;
map<int,int>::iterator it;
for(i=0;i<len;i++){
int keyb=nums[i];
int keya=target-keyb;

if (m.find(keya)!=m.end()){
v.push_back(m[keya]+1);
v.push_back(i+1);
printf("index1=%d, index2=%d",m[keya]+1,i+1);
break;
}else{
m[keyb]=i;
}
}
return v;
}
};

注意特殊用例,就是可能出现像 [ {0,4,1,0},0 ] 这种情况,所以不能在开始的时候就把vector中的元素全部放到map中再对vector遍历,要一边遍历vector一边把其中的元素存到map中。

3Sum(15)

基本上是上一题目的基本升级版

解法一

采用两指针的思路,a+b+c=0实际上就是求,a+b=-c , 比上一个2sum的问题多需要考虑的一个地方就是,需要考虑多组不同的解,以及去掉重复的解。大致思路都是基于排序,之后再遍历,在每个元素后面的序列中找两个数字的和为-current的组合。如果不进行优化,肯定会超时的,优化的方面参考了这个

  • 一个是在遍历的时候 元素重复了就直接跳过
  • 还有一个是 发现一组解之后 指针left right就要向两边移动 把相同的元素都跳过 就是函数中的那两个while循环 但还是要保证 left < right的
    其他的细节问题,vector嵌套以及声明的时候在vc6.0中注意空格 ,比如 vector<vector > , vector temp 否则会编译错误,虽然老生常谈的了,还是被坑了。每次temp vector存数据的时候,先clear一下,貌似之前的记录还在。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
//attention!! the " " in the declaration of vector<vector<int> >
void findsolution(int left,int right,int sum,vector<int> &v, vector<vector<int> > &solution){
int i=left;
int j=right;
vector<int> temp;
while(i<j){
if (v[i]+v[j]==sum){
//attention to clear before store the number
temp.clear();
temp.push_back(-sum);
temp.push_back(v[i]);
temp.push_back(v[j]);
solution.push_back(temp);
the negtive number exist maybe not uniq
while(v[i+1]==v[i] && i<j){
i++;
}
while(v[j-1]==v[j] && i<j){
j--;
}
i++;
j--;
}else if(v[i]+v[j]<sum){
i++;
}else{
j--;
}
}
}
public:
vector<vector <int> > threeSum(vector<int>& nums) {
vector<int> consider;
vector<vector<int> > solution;
int i=0;
int len=nums.size();
sort(nums.begin(),nums.end());

for(i=0;i<len;i++){
consider.push_back(0);
}
//traverse
int current;
for(i=0;i<len-2;i++){
current=nums[i];
if(i!=0 && current==nums[i-1]){
continue;
}
int inputsum=-current;
if (current==0){
inputsum=0;
}
findsolution(i+1,len-1,inputsum,nums,solution);
}
return solution;
}
};

解法二

使用map也是可以的,只不过key value的值与上题不同,value不是存储元素所在的位置。这个算法写出来比较容易,理解上有点困难。

比如 序列{-4,-1,-1,0,1,2} 遍历到-4的时候 , 从后面的元素开始看,需要在后面的元素中找两个元素,使得 a[i]+a[j]=4 才符合,-1+5=4所以map[5]=4 同理 ,map中依次存入 map[4]=0 map[3]=1 map[2]=2 遍历所有的key值 若同时存在 map[a]=b 以及 map[b]=a 说明 a b 两元素同时都在这个序列中,并且a+b=4。

对于去重的话,第一次遍历的时候,后面一个不等于前面一个,第二次存入map的时候,如果key值已经存在,并且 key==value 就是三个元素中,有两个是相等的。类似 (2,-1,-1)这种

还有个问题没解决,如果不对原始序列排序的化,去重的问题要怎么考虑?这里还没解决,排序的话有超时了

这个是超时的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class Solution {

int min(int a,int b){
if (a<b){
return a;
}else{
return b;
}
}

int max(int a,int b){
if (a>b){
return a;
}else{
return b;
}
}

void findsolutionbymap(int left,int right,int localindex,int sum,vector<int> &v, vector<vector<int> > &solution){
int i=0;
int key,value;
vector<int> temp;
map<int,int>m;
m.clear();
for(i=left;i<=right;i++){
key=sum-v[i];
value=v[i];
if(m.find(key)!=m.end()&&key==value&&m[key]==key)
{
temp.clear();
temp.push_back(-sum);
temp.push_back(min(key,value));
temp.push_back(max(key,value));
solution.push_back(temp);
continue;
}

if(m.find(value)!=m.end()&&m[value]==key&&key!=value){
temp.clear();
temp.push_back(-sum);
temp.push_back(min(key,value));
temp.push_back(max(key,value));
solution.push_back(temp);
continue;

}
m[key]=value;
}
}


public:
vector<vector <int> > threeSum(vector<int>& nums) {
vector<vector<int> > solution;
int i=0;
int len=nums.size();
sort(nums.begin(),nums.end());

int current;
for(i=0;i<len-2;i++){
current=nums[i];
if(i!=0 && current==nums[i-1]){
continue;
}
int inputsum=-current;
if (current==0){
inputsum=0;
}
findsolutionbymap(i+1,len-1,i,inputsum,nums,solution);

}
return solution;
}
};

3Sum closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

1
2
3
For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

就是三个数相加,和不断接近目标数,其实和上一个题目的思路有点类似,在求和的过程中,不断更新,由于题目中已经保证了有唯一的一组解,就保留最接近的那种就可以了。貌似很容易,代码页很简单,但是最后还是参考了别人写的。问题实质是转化为,如何在一个有序序列中找到a[i]+a[j]=sum 使得 abs(sum-target)的值最小,这个还是基于两个指针的策略,但是要好好整理一下。

  • 设置left right两个指针 temp=a[left]+a[right] closet=temp
  • while (left<right) 更新 temp
  • if temp == target 返回 temp a[left] a[right] 是所需寻找的值
  • if temp < target left ++ 如果 abs(temp-target)<abs(closet-target) closet=temp
  • if temp > target right– 如果 abs(temp-target)<abs(closet-target) closet=temp
    最后返回closet
    注意closet的持续更新,每次都要用temp-target和closet-target来进行比较,之后更新closet,有需要的化,还需要及时记录当时的left和right的位置,因为不可能靠移动一边的指针找到距离target最近的sum,总之这里要好好体会体会并且记会,属于基本套路了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
int findsolution(int left,int right,int nowindex,int sum,vector<int> &v){
int i=left;
int j=right;
int closet=v[nowindex]+v[i]+v[j];
int temp;
while(i<j){
temp=v[nowindex]+v[i]+v[j];

if (temp==sum){
return temp;
}else if(temp<sum){

if (abs(temp-sum)<abs(closet-sum)){
closet=temp;
}
while(i<j&&v[i]==v[i+1]) i++;
i++;

}else{

if (abs(temp-sum)<abs(closet-sum)){
closet=temp;
}
while(i<j&&v[j]==v[j-1]) j--;
j--;

}

}
return closet;

}

public:
int threeSumClosest(vector<int>& nums, int target) {

int i=0;
int len=nums.size();
sort(nums.begin(),nums.end());

int current;
int lastmin=9999999;
for(i=0;i<len-2;i++){
current=nums[i];
if(i!=0 && current==nums[i-1]){
continue;
}
int min=findsolution(i+1,len-1,i,target,nums);
//printf(" (%d %d)",min,min-target);
if (abs(min-target)<abs(lastmin-target)){
lastmin=min;
}


}
return lastmin;
}
};

3Sum smaller

这个题目开始收费了,参考了这里(http://likesky3.iteye.com/blog/2236385):
Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

For example, given nums = [-2, 0, 1, 3], and target = 2.

Return 2. Because there are two triplets which sums are less than 2:

[-2, 0, 1]
[-2, 0, 3]

大致分析一下,要求多组解,大致框架应该与上面的相同,先排序,再遍历(主要目的是固定一个数),再两指针选择。关键是两指针选择时候的技巧性:

  • while (i<j)
  • sum3=nums[i]+nums[j]+num[now]
  • if (sum3<target) ,由于序列已经是有序的,这个时候 nums[now]+nums[i]+nuns[j-1] 、nums[now]+nums[i]+nuns[j-2]… nums[now]+nums[i]+nums[i+1]这些组合都是符合要求的,所以符合要求的组合数目要加上 j-i 。之后让i后移一位。
  • if (sum3>=target) 这个时候就是往小移动,即 j– 还要处理下重复的情况 如果 num[j]=nums[j-1]的时候 也前移一下 放在一个while循环中 始终保持 i<j

4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:
Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
The solution set must not contain duplicate quadruplets.
For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

1
2
3
4
A solution set is:
(-1, 0, 0, 1)
(-2, -1, 1, 2)
(-2, 0, 0, 2)

背景与2Sum的形式一样,只不过由两个数变为4个数。最容易想到的一种就是转化为3Sum最后再转化为2Sum来解决。就是把外面的一重循环变成了两重循环。其实就是注意几个核心的操作,基本的框架是两指针,去重的操作怎么来,第一次循环的时候去重,用两指针寻找的时候也去重,一组解的时候怎么弄,多组解的时候怎么弄,还有vector的基本操作,比如排序这些,这些都弄好了,解决起来就比较容易了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
void findsolution(int left,int right,int index1,int index2,vector<int> &v, int target,vector<vector<int> > &solution){
int i=left;
int j=right;
vector<int> temp;
int sum;
while(i<j){
sum=v[index1]+v[index2]+v[i]+v[j];
if (sum==target){
temp.clear();
temp.push_back(v[index1]);
temp.push_back(v[index2]);
temp.push_back(v[i]);
temp.push_back(v[j]);
solution.push_back(temp);
while(i<j&&v[i]==v[i+1]){
i++;
}
while(i<j&&v[j]==v[j-1]){
j--;
}
i++;
j--;
}else if(sum<target){
i++;

}else{
j--;

}

}
}
public:
vector<vector<int> > fourSum(vector<int> &nums, int target) {
vector<vector<int> > solution;
int i=0,j=0;
int len=nums.size();
sort(nums.begin(),nums.end());

//注意循环的时候两次去重
for(i=0;i<len-3;i++){
if (i!=0&&nums[i]==nums[i-1]){
continue;
}

for(j=i+1;j<len-2;j++){
if(j!=i+1&&nums[j]==nums[j-1]){
continue;
}

findsolution(j+1,len-1,i,j,nums,target,solution);
}


}
return solution;
}
};

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

思路
之前整理了一次,又弄没了。。。坑啊。根本上讲还是两指针的问题,只不过两个指针在开始的时候是在同一个位置上的。需要额外的空间就是exist数组,用来存储该元素是否存在过。以及position,用来存储上一次出现的位置。注意还有可能是其他的字符,所以要0-128的存储空间,主要流程如下:

  • 一个while循环中 两个指针l,r初始位置都是0
  • 当前字符没有出现过 ,r指针右移,更新position。
  • 当前字符已经出现过 ,更新长度 ,记录position的位置,l指针移动到上次出现位置的下一个。注意限制条件,要上次的位置大于l的位置才能更新,比如 “ eccebaad ” 当遍历到第二个e的时候,position中记录的last位置为1,这个时候不要更新。
  • 最后r指针都向后移动一位。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    class Solution {
    public:
    int lengthOfLongestSubstring(string s) {
    int l=0,r=0;
    int start=0,end=0;
    int len=s.length();
    int position[130];
    int exist[130];
    int max=0;
    int templen,last;
    memset(position,0,sizeof(position));
    memset(exist,0,sizeof(exist));
    char temp;
    while(l<=r&&r<len){
    temp=s[r];
    last=position[temp]+1;
    //注意这里 有可能旧的位置比当前的位置小 这时就不再更换位置
    if (exist[temp]==1&&last>=l){
    l=last;
    }else{
    templen=r-l+1;
    if (templen>max){
    max=templen;
    }
    }
    position[temp]=r;
    exist[temp]=1;
    r++;
    }
    return max;
    }
    };

Longest Substring with At Most Two Distinct Characters

Total Accepted: 1167 Total Submissions: 3961
Given a string, find the length of the longest substring T that contains at most 2 distinct characters.
For example,Given s = “eceba”,
T is “ece” which its length is 3.

大致思路
这个题目改收费的了,从网上看到了别人的解答,这个问题最一般的情况是 at most K Distinct Characters。整个框架还是一样的,说白了就是,两指针从头遍历,有点滑动窗口的意思,不断调整两个窗口的边界。此外还需要一个存储出现次数的count数组,关键是存储position的策略,比如”ececebad”这种,当k=2的时候,当第三次到e的时候,l指针应该到第一个e后面的一个位置。这里就不太好存储位置了,因为如果有第四个e的时候,此时l要到第二个e的后一个位置,所以可以参考这个(http://www.cnblogs.com/x1957/p/4123301.html),对于k个位置的时候,要注意对k进行适当的分类。比如比如k<0,以及s.size()<k 这些情况要怎么处理。具体可以参考这个(http://blog.csdn.net/martin_liang/article/details/45648985)

当count数目大于K的时候,l就向右移动,一直到对应的元素出现位置,之后count-1,之后l移动到这个元素的下一个位置就更新完成了,不用一个专门的position来存储位置信息。

推荐文章