做几个leetcode数组题二 - c++编程基础

1.Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

解析：要求时间复杂度 O(n)，循环需要n,所以必须在常数时间内查找出某个特定的值--〉哈希表（散列表）

class Solution {

public:

int longestConsecutive(vector &num) {

unordered_map helparray; //散列表STL

for (auto i : num) helparray[i] = false; //这里用了auto ， auto i : vector是把容器内从第一个开始的值依次赋值给i

int longest = 0;

for(auto i : num)

{

if (helparray[i]) continue; //如果查过了用true,未查到用false

int length = 1;

helparray[i] = true;

for (int j = i + 1; helparray.find(j) != helparray.end(); ++j) //查比i大的

{

helparray[j] = true;

length++;

}

for (int j = i - 1; helparray.find(j) != helparray.end(); --j) //查比i小的

{

helparray[j] = true;

length++;

}

longest = max(longest,length); //总是维护longest为目前最大值

}

return longest;

}

};

3Sum

Total Accepted: 29031 Total Submissions: 173719My Submissions

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0 Find all unique triplets in the array which gives the sum of zero.

Note:

Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)

The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

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

解：

一开始自己试的，把所有满足的都放到了一个vector里

#include

#include

using namespace std;

vector
    
      threeSum(vector
     
       &num) {

        vector
    
     ::iterator r1;

        vector
    
     ::iterator r2;

		const int target = 0;

        vector
    
      result;

        for (r1 = num.begin(); r1 != num.end(); ++r1)

    		int a = *r1;

    		for (r2 = r1 + 1; r2 != num.end(); ++r2)

		        	int b = *r2;

		        	int c = target - a - b;  //找第三个数时可以用二分法等来缩短时间复杂度，前两个是就这样了，n^2,第三个可logn 
，后来查的，注意find不是成员函数，是STL算法,返回位置，二分法是binary_find(起位置，终位置，要查找的值);也是算法，但返回是bool

		        	vector
    
     ::const_iterator r3 = find(r2 + 1, num.end(), c);

		        	if (r3 != num.end())

						result.push_back(a);

		        		cout << " a: " << a;

		        		result.push_back(b);

		        		cout << " b: " << b;

		        		result.push_back(c);

		        		cout << " c: " << c;

		        		cout << endl;

        return result;

int main()

	vector
    
      a;

	a.push_back(1);

	a.push_back(-4);

	a.push_back(0);

	a.push_back(4);

	a.push_back(-1);

	a.push_back(5);

	a.push_back(5);

	vector
    
      resultr;

	vector
    
     ::iterator rp;

	resultr = threeSum(a);

	for (rp = resultr.begin(); rp != resultr.end(); ++rp)

	 cout << " " << *rp;

    cout << endl;

由此算法改成vector数组存放到vector，提交结果是Output Limit Exceeded

class Solution {

public:

    vector
    
      > threeSum(vector
     
       &num) {

        vector
    
     ::iterator r1;

        vector
    
     ::iterator r2;

		const int target = 0;

		vector
    
     > result;

        for (r1 = num.begin(); r1 != num.end(); ++r1)

    		int a = *r1;

    		for (r2 = r1 + 1; r2 != num.end(); ++r2)

		        	int b = *r2;

		        	int c = target - a - b;

		        	if (binary_search(r2 + 1, num.end(), c))

		        		result.push_back(vector
    
      {a,b,c});

        return result;

};

后来发现没考虑数组元素少于3的情况，和用二分法之前需要对其进行排序，更正后还是Output Limit Exceeded，后又查到for循环的判断条件1：-2； 2： -1 ；,后来找到原因，是我的算法不能排除重复的三个数，比如0，0，0，0，会出现好多组{0，0，0}，而题目要求不能，后来想到第二个for中加个一个if(r2 == prev(r2)) continue;这样首先r2第一个元素时不行，另外对r1的考虑也不健全（如 -1，-1，-1，2还是会有重复），后来还是采用答案中那种，把++r1换成了r1 = upper_bound(r1,prev(num.end(),2),*r1)，++r2换成r2 = upper_bound(r2,prev(num.end()),*r2)后就AC了。既然找到问题所在，那么

做几个leetcode数组题二(一)

1.Longest Consecutive Sequence

3Sum