最接近0的数组子序列

待我称王封你为后i 2022-07-12 06:36 152阅读 0赞

给定一个数组，在数组中找一段子序列，要求子序列的和最接近0。  
例如：  
输入：\[-3, 1, 1, -3, 5\],  
\[0, 2\], \[1, 3\], \[1, 1\], \[2, 2\] ,\[0, 4\]都是可行解

sum\[i,j\]表示\[i,j\]索引的所有元素的和。  
sum\[i,j\]可以换算成下面公式：  
sum\[i,j\]=sum\[0,j\]-sum\[0,i\] + num\[i\]

这里为了方便起见，在写代码时记sum\[i\]表示前i个元素之和\[0,i-1\]所有元素相加。

得到sum数组之后，为了方便找出数组中绝对值最小的两个元素之差，对数组进行排序，计算相邻两个元素之差的绝对值。不过由于排序之后丢失了原来的索引信息，因此，用一个pair

class Solution {
        public:
        vector<int> subarraySumClosest(vector<int> nums){
            int n = nums.size();
            vector< pair<int,int> >sum(n+1);
            sum[0].first=0;
            sum[0].second=-1;
            for(int i=1;i <= n; ++i)
            {
                sum[i].first=nums[i-1]+sum[i-1].first;
                sum[i].second=i;
                if(sum[i].first==0)
                {
                    res[0]=0;
                    res[1]=i-1;
                    return res;
                }
            }
            sort(sum.begin()+1,sum.end(),
            [](const pair<int,int>&A,const pair<int,int>&B){
                return A.first<B.first;
            });
            n=sum.size();
            int curMin=abs(sum[1].first-sum[0].first);
            vector<int>res(2);
            res[0]=0;
            res[1]=0;
            for(int i=2;i<=n;++i)
            {
                int tmp = abs(sum[i].first-sum[i-1].first);
                if(tmp < curMin)
                {
                    int index1=sum[i-1].second;
                    int index2=sum[i].second;
                    if(index1>index2)
                    swap(index1,index2);
                    res[0]=index1;
                    res[1]=index2-1;
                    curMin=tmp;
                }
            } 
            return res;
        }
    };