双指针方法

数组类

整体印象

此类问题一般涉及几种情形:in place 的更新数组,需要一个index记录更新之后的数组,另一个index跑遍原来的数组; 还有就是找到数组里面的N个数使得这几个数满足一定的条件(如几个数之和必须为某一个特定的数);还有就是一类特殊的问题雨水储存问题。
这里有几个关键问题需要理解:
首先数组是否排序,根据信息论的看法或者能量守恒的原理,数组是否排序与墒有关,墒的本质就是描述事物有序程度的度量,换句话说事物越有序墒的值越低,并且本质是墒会自然的会增大在无外力干扰的状况下,也就是事物总是向着无序发展的。而怎样让事物变的有序呢,那么就需要外力能量的输入来使得墒变小或者变的有序。那么在数组是否有序的问题上,我们希望它是有序的,如果不是那么就需要花费“能量”让他的墒变小,这样复杂度O(nlogn)就上去了,这里复杂度可以看作为外作用力的体现。
其次双指针问题的本质其实是由于有两个或者多个元素有相互作用或者相关联,因此在改变其中一个元素的同时其他几个元素也需要跟着改变,因此双指针问题一般是在满足几个元素关系不变的情况之下,改变一个元素的同时,寻找其他几个元素满足现有的关系情况。

实时更新数组

例题:Remove Element
分析: 这道题有几个关键字需要注意: in place, the order of elements can be changed.所以我们可以尝试用two pointers,一个记录remove过后的数组最后一个元素位置,一个用来遍历整个数组,判断条件就是比较该元素和target的值,如果不相等就把它copy给另一个pointer.因为题目只需要求最后的数组长度,所以返回最后记录位置就可以了。
复杂度: 时间复杂度O(n),空间复杂度O(1).

class Solution {
public:
int removeElement(int A[], int n, int elem) {
    if(A == nullptr || n == 0) return 0;
    int index = 0;
    
    for(int i = 0; i < n ; ++i){
        if(A[i] != elem){
            A[index++] = A[i];
        }
    }        
    return index;
   }
};

接下来我们看一看这道题的一个变形:
例题: Remove Duplicates from Sorted Array
分析:这道题几乎和上一题一样,这里注意数组是排序的, 关键词: in place with constant memory. 有一个地方值得注意第二个pointer的起始点应该从第二个元素开始,因为实际上第二个指针是用来比较和前一个元素的值,如果相等就skip.
复杂度: 时间复杂度O(n), 空间复杂度O(1).

class Solution {
public:
int removeDuplicates(int A[], int n) {
    if(A == nullptr || n == 0) return 0;
    int index = 0;

    for(int i = 1; i < n ; ++i){
        if(A[index] != A[i]){
            A[++index] = A[i];
        }
    }            
  return index + 1;
 }
};

下面增加了一点难度,如果同一个元素允许出现两次。
例题: [Remove Duplicates from Sorted Array II](https://oj.leetcode.com/problems/remove-duplicates-from-sorted-array-ii/)
分析: 首先想到的是hashtable储存每个元素的个数,仔细观察题目可以发现其实不需要hashtable,因为数组是排序的,重复的元素应该会连在一起,这样遍历的时候多加一个判断就可以解决。
复杂度: 时间复杂度O(n),空间复杂度O(1).

先看一个解法建立在上一题的基础上,其中判断了前后元素是否相等,这样保证最多只有两个相同的元素:

class Solution {
public:
int removeDuplicates(int A[], int n) {
    if(A == nullptr || n == 0) return 0;
    
    int index = 0;
    for(int i = 1; i < n ; ++i){
        if(A[index] == A[i] && (index == 0 || A[index-1] != A[index]))
            A[++index] = A[i];
            
        if(A[index] != A[i])
            A[++index] = A[i];
    }
    return index + 1;
  }
};

其实可以稍加改变,使得解法更有可扩展性,处理N个重复的元素的情形:

 class Solution {
public:
int removeDuplicates(int A[], int n) {
    if(A == nullptr || n == 0) return 0;
    if(n <= 2) return n;
    
    int index = 2;
    for(int i = 2; i < n ; ++i){
        if(A[i] != A[index - 2])
            A[index++] = A[i];
    }
    return index;
  }
};

这里直接从第三个元素开始比较,如果是允许N个重复元素,2可以改为N,代码比上个解法简洁也更具有可拓展性。

前面几道题都是删除元素,还有一类问题就是排序问题有时候也可以用Two Pointers的解法.
例题: [Sort Colors] (https://oj.leetcode.com/problems/sort-colors/)
分析:这里有三个指针,但是实际是两个在操作,一个存red的index,一个存blue的index, 然后两边往中间走。
复杂度: 时间复杂度O(n), 空间复杂度O(1).

  class Solution {
 public:
  void sortColors(int A[], int n) {
      int j = 0, k = n-1;
      int i = 0;
      while(i < k + 1){
          if(A[i] == 0){
              int t = A[j];
              A[j] = A[i];
              A[i] = t;
              j++;
              i++;
          }else if(A[i] == 2){
            int t = A[k];
            A[k] = A[i];
            A[i] = t;
            k--;
        }else{
            i++;
        }    
    }
 }
};

此外这道题还有个非常巧妙的解法,利用到了partition中的原理:

 class Solution {
public:
void sortColors(int A[], int n) {
    int j = 0; 
    int k = 0;
    int i = 0;
    for(int m = 0; m < n ; ++m){
        if(A[m] == 2){
            A[k++] = 2;
        }else if(A[m] == 1){
            A[k++] = 2;
            A[j++] = 1;
        }else if(A[m] == 0){
            A[k++] = 2;
            A[j++] = 1;
            A[i++] = 0;
        }
    }
}
};

雨水问题

此类问题表面上看跟双指针没有任何关系,但是经过仔细分析,会发现有很多共同之处。
例题: Container with Most water
分析:这道题可以先找几个数模拟一下,会发现如果想让容器储存的水多,需要左右两个数距离越远越好,并且两个数中较小的数值越大越好。首先考虑暴力解法,固定一边,然后找另一边越大越好,对每一个数都查找一下,就需要O(n^2).仔细研究发现,这道题是可以用双指针的,因为最后的结果被决定于左右两个数,那么怎么进行遍历呢,如果固定一边,永远希望找比这一边大的数,因此如果比这一边小可以skip掉。于是left 和right两边左右夹逼,遇到较小的数就skip掉直到重合。
复杂度: 时间复杂度O(n), 空间复杂度O(1).

class Solution {
public:
int maxArea(vector<int> &height) {
    if(height.size() == 0) return 0;
    
    int i = 0;
    int j = height.size() -1;
    int maxA = INT_MIN;
    
    while(i < j){
        int area = min(height[j],height[i]) * (j-i);
        maxA = max(maxA, area);
        if(height[i] < height[j]){
            i++;
        }else {
            j--;
        }
    }
    
    return maxA;
}
};

再来看一个类似的题目,这里container不止一个了。
题目: Trapping Rain Water
分析:这里也是类似,对于每个柱子需要分别寻找它的左边和右边最高的柱子,这样该柱子能容纳的面积就是min(max_left, max_right) - height.因此解法自然变成了从左往右遍历,找到每个柱子左边最大值,然后从右向左遍历找到每个柱子右边最大值。最后一次遍历计算每个柱子可以容纳的面积。
复杂度:时间复杂度O(n), 空间复杂度O(n).

   class Solution {
public:
int trap(int A[], int n) {
    if(A == nullptr || n == 0) return 0;
    vector<int> right_height(n);
    vector<int> left_height(n);
    
    int height = 0, total = 0;
    
    for(int i = 0; i < n; ++i){
        if(A[i] > height) height = A[i];
        
        right_height[i] = height;
    }
    
    height = 0;
    
    for(int i = n -1; i >= 0; --i){
        if(A[i] > height) height = A[i];
        
        left_height[i] = height;
    }
    
    for(int i = 0; i < n; ++i){
        total += min(right_height[i], left_height[i]) - A[i];
    }
    
    return total;
}
};

这道题还有一个分而治之的方法,可以先遍历一边数组找到最大值,然后在最高柱子的左边和右边分别遍历就可以计算出最后的结果。
复杂度: 时间复杂度O(n), 空间复杂度O(1).

 class Solution {
public:
int trap(int A[], int n) {
    if(A == nullptr || n == 0) return 0;
    
    int result = 0;
    int max = -1, index = 0;
    for(int i = 0; i < n ; ++i){
        if(A[i] > max){
            max = A[i];
            index = i;
        }
    }
    
    int left = -1;
    for(int i = 0; i < index; ++i){
        if(A[i] > left)
            left = A[i];
        else
            result += left - A[i];
    }
    
    int right = -1;
    for(int i = n-1; i > index; --i){
        if(A[i] > right)
            right = A[i];
        else
            result += right - A[i];
    }
    
    return result;
}
};

求和问题

下面我们开始分析一下一系列关于元素求和的问题,这一系列问题特征如下,在一组任意排序数组中,寻找N个数使得它们的(积和差除)满足某一个条件,这里可以是它们经过一系列运算满足某一个值,或者求他们的最大值等等。处理此类问题的时候,首先看数组是否是有序的,根据之前的理论如果数组是无序的,那么需要额外的力使其有序,一般是排序或者hashtable来记录每个元素,复杂度会上升。然后在数组有序的情况下进行左右夹逼,找到满足条件的元素。

例题;Two Sum
分析: 一个经典的求和问题,首先看数组是否有序, 很遗憾,没有!因此需要排序,但是注意这样复杂度就变成O(nlgn)了,有没有更好的方法,hashtable!可以保持复杂度在O(n)又可以起到排序的效果。这里注意在循环里面的判断条件,首先看target - number[i]是否在hashtable里面存在,如果存在就输出结果,如果不存在,记录当前的数进入hashtable里面。
复杂度: 时间复杂度O(n),空间复杂度O(1).

 class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {
    vector<int> answer(2,0);
    unordered_map<int, int> record;
    for(int i = 0; i < numbers.size(); ++i){
        int x = numbers[i];
        if(record.find(target - x) != record.end()){
            answer[1] = i + 1;
            answer[0] = record[target - numbers[i]];
            break;
        }
        record[numbers[i]] = i + 1;
    }
    return answer;
}
};

例题: 3Sum Closest
分析:还是首先看是否数组是有序的,如果不是有序的就得排序,这道题涉及到三个元素(三体问题),原则上三体问题包含了一切三个元素及以上的问题,如果说两体问题可以通过一些技巧(如hashtable)解决的话,三体问题就是复杂度提高了一个台阶,一些普适于两体的技巧在三体问题这里行不通了。因此在这里首先要对数组排序, 此题涉及到三个元素,首先头尾各放一个元素,然后中间从第二个元素,左右夹逼,我们用一个gap来计算target和现在所有值的和之差,由于已经排好序,只要比较target和现在sum的值,如果target值较小,那么说明mid的值过小因此往中间靠拢,反之right的值过大因此向中间靠拢。就这样做两重遍历可以计算到最接近target的值,因为这道题只要找最接近的数因此没有3Sum那么限制条件多。
复杂度: 时间复杂度O(n^2),空间复杂度O(1).

 class Solution {
public:
 int threeSumClosest(vector<int> &num, int target) {
    int sum = 0;
    sort(num.begin(), num.end());
    
    int min_gap = INT_MAX;
    for(auto start = num.begin(); start != prev(num.end(), 2); ++start){
        auto mid = next(start);
        auto last = prev(num.end(), 1);
        while(mid < last){
            int sumup = *start + *mid + *last;
            int gap = abs(target -sumup);
            if(gap < min_gap){
                min_gap = gap;
                sum = sumup;
            }
            
            if(sumup < target){
                mid++;
            }else{
                last--;
            }
        }
    }
    
    return sum;
 }
};

例题:3Sum
分析:这道题是标准的求和问题,方法与前面类似,但是要注意重复数的出现也就是while(b < c)里面不断夹逼如果出现近邻的元素相同的情况,需要一个while语句来移动,这样得到的最后数组一定没有重复数。还有就是a的重复情况也需要考虑。
复杂度:时间复杂度O(n^2), 空间复杂度O(1).

Solution {
 public:
vector<vector<int> > threeSum(vector<int> &num) {
    vector<vector<int> > result;
    if(num.size() < 3) return result;
    sort(num.begin(), num.end());
    const int target = 0;
    
    for(auto a = 0; a < num.size()-2; ++a){
        if( a > 0 && num[a] == num[a-1]) continue;
        auto b = a + 1;
        auto c = num.size() - 1;
        
        while(b < c){
            if(num[a] + num[b] + num[c] < target){
                do{b++;}while(b < c&& num[b] == num[b-1]);
            }else if (num[a] + num[b] + num[c] > target){
                do{c--;}while(b < c && num[c] == num[c+1]);
            }else{
                result.push_back({num[a], num[b],num[c]});
                do{b++;} while(b < c && num[b] == num[b-1]);
                do{c--;} while(b < c && num[c] == num[c+1]);
            }
        }            
    }     
    return result;
    
}
};

例题: 4Sum
分析:如果使用上面类似的方法复杂度达到了O(N^3),有没有更省时间的方法呢?想到一共是四个数之和,自然想到可不可以两两配对,这样把问题可以简化为2Sum. 这里我们使用multimap来储存两个数的和,首先要弄清楚key是什么,因为不同的两个数可能有相同的和,因此key为两个数的和,value则是a pair of indexes记录两个数在数组的位置。这样遍历multimap的同时,找到另一组数使得两组数之后为target.
复杂度:时间复杂度O(N^2), 空间复杂度O(N^2).

  class Solution {
public:
vector<vector<int> > fourSum(vector<int> &num, int target) {
   vector<vector<int>> result;
   if (num.size() < 4) return result;
   sort(num.begin(), num.end());
   
   unordered_multimap<int, pair<int, int>> cache;
   for (int i = 0; i + 1 < num.size(); ++i)
       for (int j = i + 1; j < num.size(); ++j)
           cache.insert(make_pair(num[i] + num[j], make_pair(i, j)));

   for (auto i = cache.begin(); i != cache.end(); ++i) {
        int x = target - i->first;
          auto range = cache.equal_range(x);
        for (auto j = range.first; j != range.second; ++j) {
          auto a = i->second.first;
          auto b = i->second.second;
          auto c = j->second.first;
          auto d = j->second.second;
          if (a != c && a != d && b != c && b != d) {
             vector<int> vec = { num[a], num[b], num[c], num[d] };
             sort(vec.begin(), vec.end());
             result.push_back(vec);
            }
           }
        }
    sort(result.begin(), result.end());
    result.erase(unique(result.begin(), result.end()), result.end());
    return result;
   }
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 212,686评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,668评论 3 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 158,160评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,736评论 1 284
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,847评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,043评论 1 291
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,129评论 3 410
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,872评论 0 268
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,318评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,645评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,777评论 1 341
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,470评论 4 333
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,126评论 3 317
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,861评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,095评论 1 267
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,589评论 2 362
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,687评论 2 351

推荐阅读更多精彩内容

  • 一、 C/C++程序基础 面试例题1——分析代码写输出(一般赋值语句的概念和方法)。 面试例题2—...
    LuckTime阅读 1,970评论 2 42
  • 概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部...
    蚁前阅读 5,170评论 0 52
  • 亮亮是我的同学,一个女孩子,从小喜欢看西方故事,长大后便立志去国外见识一番,大学便一直在锲而不舍地学习英语,后来英...
    丰鸟阅读 550评论 0 2
  • 1.家务:能把自己的袜子洗干净,洗 自己冬天外套,饭盒袋,书包,有时 还帮爸爸妈妈洗袜子 ...
    Sunny阳光自信的巧克力阅读 517评论 2 3