子数组之和

墨蓝 2022-09-24 14:17 159阅读 0赞

## 蛮力法 ##

时间复杂度O(N2).

vector<int> subarraySum(vector<int> nums){
            // write your code here
            vector<int> res;
            int i,j,sum;
            for(i=0;i<nums.size();i++)
            {
                sum=nums[i];
                if(sum==0){
                    res.push_back(i);
                    res.push_back(i);
                    return res; 
                }
                for(j=i+1;j<nums.size();j++)
                {
                   sum+=nums[j];
                   if(sum==0)
                    {
                        res.push_back(i);
                        res.push_back(j);
                        return res;
                    }
                }
            }
            return res;
        }

## 巧妙解法 ##

时间复杂度为O(nlogn)  
思路思路：

> 已知 ：  
> sum\[ i \]=a\[ 0 \]+……a\[ i \];  
> sum\[ j \]=a\[ 0 \]+……a\[ j \];  
> 且 i < j;  
> 如果sum\[ i \]==sum\[ j \]  
> 那么 a\[ i+1 \]+..a\[ j \]==0;

vector<int> subarraySum(vector<int> nums){
            // write your code here
            vector<pair<int,int>> hash(nums.size()+1);
            vector<int> res;
            int i,j,sum=0;
            if(nums.empty())
                return res;
    
            for(i=0;i<nums.size();i++)
            {
                sum+=nums[i];
                hash[i+1].first=sum;
                hash[i+1].second=i+1;
            }
            sort(hash.begin(),hash.end());
            for(i=1;i<hash.size();i++)
            {
                if(hash[i].first==hash[i-1].first)
                {
                    res.push_back(hash[i-1].second);
                    res.push_back(hash[i].second-1);
                    return res;
                }
            }
            return res;
        }

详细的完了补。。。。