AcWing 76. java-神仙解法（哪位能告诉我为啥）    原题链接    中等

作者： 作者的头像   脆脆鲨 ,  2019-05-04 22:50:31 ,  所有人可见 ,  阅读 1152

0


不同于滑动窗口
对于15，[7,8]是因为除以二是7.5，两边取7和8，[4,5,6]是因为除以3，刚好能得到5,5就是中间的数字，往两边各延伸一个数字就3,4,5
所以依次遍历i，表示结果的个数，取值范围是[2,15/2+1]，
如果i是奇数，并且能被整除，那么sum/i就是中间的数，也就得到了连续序列；如果不能被整除说明结果的个数不可能是i
如果i是偶数，我这就看不懂了为啥是sum%i*2==i就是可以的呢，希望神仙能帮我解释一下==

class Solution {
    public List<List<Integer>> findContinuousSequence(int sum) {
        List<List<Integer>> res=new LinkedList();
        if(sum<=2) return res;
        for(int i=2;i<=((sum>>1)+1);i++){
            if((i&1)==1 && sum%i==0){
                //i是奇数，并且能被整除，则sum/i就是中间数；如果不能整除奇数则一定不是了
                int mid=sum/i,shift=i>>1;
                if(mid-shift>0){
                    //要排除非正数
                    res.add(continusSeq(mid-shift,mid+shift));
                }
            }else if((i&1)==0 && sum%i*2==i){
                //i是偶数，并且取余后乘2等于i
                int left=sum/i,shift=i/2-1;
                if(left-shift>0){
                    res.add(continusSeq(left-shift,left+shift+1));
                }
            }
        }
        return res;
    }

    private List<Integer> continusSeq(int start,int end){
        List<Integer> list=new LinkedList();
        for(int i=start;i<=end;i++){
            list.add(i);
        }
        return list;
    }
}

3 评论

用户头像
廖少少   2020-01-25 19:24         踩      回复

自己想的，全都在注释里面了，主要思想是判断每个len是否可能是序列的长度，需要根据len的奇偶性与avg的值来判断

class Solution {
public:
    vector<vector<int> > findContinuousSequence(int sum) {
        // 这种连续正数序列vec肯定满足：vec.avg()*vec.size()=sum
        // 而vec.avg()肯定是0.5的倍数
        // vec.avg()-vec.size()/2 肯定要大于0，也就是序列开头肯定要大于0
        if(sum < 3) return vector<vector<int> >();
        vector<vector<int> > ans;
        vector<int> vec;
        int len = 3;
        if(sum % 2){
            ans.push_back(vector<int>{sum/2, sum/2+1});
        }
        while(len < sum/2){
            // 如果avg是整数
            if((double) sum/len == sum/len){
                // 如果len是奇数且序列开头大于0
                if(len&1 && sum/len-len/2 > 0){
                    for(int num = sum/len-len/2; num <= sum/len+len/2; ++num){
                        vec.push_back(num);
                    }
                    ans.push_back(vec);
                    vec.clear();
                }
            }
            // 如果avg不是整数但是是0.5的倍数
            else if((double) sum*2/len == sum*2/len){
                // 如果len是偶数且序列开头大于0
                if(!(len&1) && sum/len+1-len/2 > 0){
                    for(int num = sum/len+1-len/2; num <= sum/len+len/2; ++num){
                        vec.push_back(num);
                    }
                    ans.push_back(vec);
                    vec.clear();
                }
            }
            ++len;
        }
        return ans;
    }
};
用户头像
廖少少   2020-01-25 19:24         踩      回复

自己想的，全都在注释里面了，主要思想是判断每个len是否可能是序列的长度，需要根据len的奇偶性与avg的值来判断

class Solution {
public:
    vector<vector<int> > findContinuousSequence(int sum) {
        // 这种连续正数序列vec肯定满足：vec.avg()*vec.size()=sum
        // 而vec.avg()肯定是0.5的倍数
        // vec.avg()-vec.size()/2 肯定要大于0，也就是序列开头肯定要大于0
        if(sum < 3) return vector<vector<int> >();
        vector<vector<int> > ans;
        vector<int> vec;
        int len = 3;
        if(sum % 2){
            ans.push_back(vector<int>{sum/2, sum/2+1});
        }
        while(len < sum/2){
            // 如果avg是整数
            if((double) sum/len == sum/len){
                // 如果len是奇数且序列开头大于0
                if(len&1 && sum/len-len/2 > 0){
                    for(int num = sum/len-len/2; num <= sum/len+len/2; ++num){
                        vec.push_back(num);
                    }
                    ans.push_back(vec);
                    vec.clear();
                }
            }
            // 如果avg不是整数但是是0.5的倍数
            else if((double) sum*2/len == sum*2/len){
                // 如果len是偶数且序列开头大于0
                if(!(len&1) && sum/len+1-len/2 > 0){
                    for(int num = sum/len+1-len/2; num <= sum/len+len/2; ++num){
                        vec.push_back(num);
                    }
                    ans.push_back(vec);
                    vec.clear();
                }
            }
            ++len;
        }
        return ans;
    }
};
用户头像
Muye   2019-07-17 16:59         踩      回复

偶数次其实就是在奇数次规律上在右边多加入一个数，假设x，当x-sum/i == sum%i 时，即满足条件，这样会比较好理解。而x又可以表示为 i-i/2 + sum/i。推导之后就是上面的等式了。