2. Linux.do
  3. Leetcode每日一题 —— 2574. 左右元素和的差值

Leetcode每日一题 —— 2574. 左右元素和的差值

SomeBottle 2026-06-06 09:44 1


昨天数位 DP 实在是不太会，就去随便挑了一道中等题做了。


今天这题就很常规了。



思路


其实就是在计算前缀和与后缀和的绝对差。不过额外空间可以只使用结果数组，先在结果数组中生成前缀，然后动态生成后缀并计算结果即可。



代码


class Solution {

public:

    vector<int> leftRightDifference(vector<int>& nums) {

        // 就是在考察前缀后缀，额外空间只需要结果数组

        int n=nums.size();

        vector<int> res(n,0);

        // 先生成前缀

        for(int i=1;i<n;i++){

            res[i]=res[i-1]+nums[i-1];

        }

        // 再根据后缀得到结果

        int rightSum=nums[n-1];

        for(int i=n-2;i>=0;i--){

            res[i]=abs(res[i]-rightSum);

            rightSum+=nums[i];

        }

        return res;

    }

};
最新回复 (3)
  • Lvvvv 06-06 09:58
    1楼

    昨天也是战胜不了。想了好半天发现统计量都不对劲 ^-^


    class Solution {
    
public:
    
    vector<int> leftRightDifference(vector<int>& nums) {
    
        int n = nums.size();
    
        std::vector<int> res(n),pre(n,0);
    
        int sum = std::accumulate(nums.begin(),nums.end(),0);
    
        int ls = 0;
    
        for(int i = 0; i < n; i++) {
    
            res[i] = abs(ls - (sum - nums[i] - ls));
    
            ls += nums[i];
    
        }
    
        return res;
    
        
    
    }  
    
};
  • Elbert 06-06 15:15
    2楼

    来两个一行解，一个声明式一个基于数学关系


    leftRightDifference nums = zipWith ((.) abs . (-)) (scanl (+) 0 nums) (drop 1 (scanr (+) 0 nums))
    


    leftRightDifference nums = let s = sum nums in snd $ mapAccumL (\l x -> (l + x, abs $ 2 * l + x - s)) 0 nums

    昨天那题拿python写了自顶向下的提交用了500+ms，一看最快的居然是0ms、还是自底向上的，还是太有水平了 ^-^

  • 咪帕 06-06 15:17
    3楼 
    class Solution:
    
    def leftRightDifference(self, nums: List[int]) -> List[int]:
    
        total = sum(nums)
    
        pre = 0
    
        ans = []
    
        for n in nums:
    
            right = total - n - pre
    
            ans.append(abs(right - pre))
    
            pre += n
    
        return ans

    刚刚考完试，有时间刷一下

    没能战胜数位dp ^-^

* 帖子来源Linux.do
附近帖子
返回
飞读
随机推荐