变量简洁正确完整思路 map<int左边界,int右边界>left2right map<Int右边界,int左边界>right2left 可以利用右边界查找左边界,可以利用左边界查找右边界 对于num,查找num-1作为右边界的左边界和num+1作为左边界的右边界 如果都有,新的左边界right2left[num-1] 新的右边界left2rightleft2right[num+1] 删掉原来的, 如果有左边界 如果有右边界 如果都没有 输出,因为map是排序的所以非常容易 class SummaryRanges { public: map<int,int>left2right,right2left; /** Initialize your data structure here. */ SummaryRanges() { } void addNum(int val) { auto iter=right2left.lower_bound(val); if(iter!=right2left.end()&&iter->second<=val)return; int hasLeft=right2left.count(val-1); int hasRight=left2right.count(val+1); if(hasLeft==1&&hasRight==1){ int left=right2left[val-1]; int right=left2right[val+1]; //cout<<left<<‘ ‘<<right<<‘ ‘<<val<<endl; right2left.erase(val-1); left2right.erase(val+1); right2left[right]=left; left2right[left]=right; //cout<<right2left[val+1]<<‘ ‘<<val+1<<endl; //cout<<left<<‘ ‘<<left2right[val-1]<<endl; } else if(hasLeft==1&&hasRight==0){ int left=right2left[val-1]; //cout<<left<<‘ ‘<<val<<endl; right2left.erase(val-1); left2right.erase(left); right2left[val]=left; left2right[left]=val; } else if(hasLeft==0&&hasRight==1){ int right=left2right[val+1]; right2left.erase(right); left2right.erase(val+1); right2left[right]=val; left2right[val]=right; }else if(hasLeft==0&&hasRight==0){ left2right[val]=val; right2left[val]=val; } } vector<vector<int>> getIntervals() { vector<vector<int>>ans; for(auto &mPair:left2right){ ans.push_back({mPair.first,mPair.second}); } return ans; } }; /** * Your SummaryRanges object will be instantiated and called as such: * SummaryRanges* obj = new SummaryRanges(); * obj->addNum(val); * vector<vector<int>> param_2 = obj->getIntervals(); */ 踩过的坑 right2left[right]=left; left2right[left]=right; //right2left.insert({right,left}); //left2right.insert({left,right}); 不能用insert插入,因为这是映射关系,直接给一个数组会看做两次插入,map不需要 使用insert 如果已经有了,就直接跳过,比如[8,6],来了6,用lower_bound找到第一个大于等于 6,second小于等于6就跳过 lower_bound是大于等于,upper_bound是大于,没有任何小于