leetcode15

素颜马尾好姑娘i 2022-08-09 02:21 54阅读 0赞

国庆假期也玩也coding，再不写博客，之前没写注释的代码可能都忘了。。。  
以后要开始写写注释。  
LeetCode15-3Sum  
这道题目出出来就知道暴力搜索肯定是超时的，虽然这样依然抱着侥幸心理试了试，确实超时了，就不贴代码了。

当然考虑Two Sum用map空间来换取时间的方法，我还是尝试了一下。由于是三个数，很有可能要考虑重复的问题，我在代码中使用如下方式来去重：

if(find(result.begin(),result.end(),temp) == result.end())
    {
    	result.push_back(temp);
    }

在两重循环中使用find来判断vector<int>类型的变量temp是否在result结果集中出现，结果是超时的，后来查了一下得知，std::find的时间复杂度是O(n)

参考http://www.cplusplus.com/reference/algorithm/find/ 代码：

template<class InputIterator, class T>
      InputIterator find (InputIterator first, InputIterator last, const T& val)
    {
      while (first!=last) {
        if (*first==val) return first;
        ++first;
      }
      return last;
    }

好了，言归正传，对于3Sum来说，做法是先固定一个数，再对另两个数进行夹逼。

三点注意的是：

1.原数组事先按升序排序。

2.对于固定的第一个数来说，每次循环需要去重。

3.对于夹逼的两个数来说，也需要去重，并且根据三数相加的结果，从两边向中间靠近（要么左数向右要么右数向左，不同时）。

代码：

bool cmp(const int & x,const int & y)
    {
    	return x<y;
    }
    class Solution {
    public:
        vector< vector<int> > threeSum(vector<int>& nums) {
    		int numLen = nums.size();
    		int i;
    		int j;
    		int k;
    		vector< vector<int> >result;
    		if(numLen  < 3)
    		{
    			return result;
    		}
    		vector<int>temp;
    		sort(nums.begin(),nums.end(),cmp);
    		for(i=0;i<numLen-2;i++)
    		{
    			j=i+1;
    			k=numLen - 1;
    			while(j<k)
    			{
    				if(nums[i] + nums[j] + nums[k] == 0)
    				{
    					temp.push_back(nums[i]);
    					temp.push_back(nums[j]);
    					temp.push_back(nums[k]);
    					result.push_back(temp);
    					temp.clear();
    					while(j<k&&nums[j]==nums[j+1])
    						j++;
    					while(j<k&&nums[k]==nums[k-1])
    						k--;
    					/*
    					if(find(result.begin(),result.end(),temp) == result.end())
    					{
    						result.push_back(temp);
    					}//时间复杂度为O(n)
    					*/
    				}
    				if(nums[i] + nums[j] + nums[k] < 0)
    					j++;
    				else
    					k--;
    				//j++;
    				//k--;
    			}
    			while(i<numLen-2&&nums[i]==nums[i+1])
    			    i++;
    		}
    
    		return result;
    	}
    };