給你一個整數數組nums，和兩個整數limit與goal。數組nums有一條重要屬性：abs(nums[i])<= limit。

創(chuàng)新互聯公司-專業(yè)網站定制、快速模板網站建設、高性價比惠民網站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式惠民網站制作公司更省心,省錢,快速模板網站建設找我們，業(yè)務覆蓋惠民地區(qū)。費用合理售后完善，十余年實體公司更值得信賴。

返回使數組元素總和等于goal所需要向數組中添加的 最少元素數量 ，添加元素 不應改變 數組中abs(nums[i])<= limit這一屬性。

注意，如果x >= 0，那么abs(x)等于x；否則，等于-x。

示例 1：

輸入：nums = [1,-1,1], limit = 3, goal = -4
輸出：2
解釋：可以將 -2 和 -3 添加到數組中，數組的元素總和變?yōu)?1 - 1 + 1 - 2 - 3 = -4 。

示例 2：

輸入：nums = [1,-10,9,1], limit = 100, goal = 0
輸出：1

提示：

• 1<= nums.length<= 10^5
• 1<= limit<= 10^6
• -limit<= nums[i]<= limit
• -10^9<= goal<= 10^9

分析：

看到這道題，第一反應就是把nums中的數加起來，然后用加起來的值和goal的差值除以limit即可得到結果。

class Solution {public:
    int minElements(vector& nums, int limit, int goal) {int addnum = 0;
        for(auto num : nums)
            addnum += num;
        int gapnum = goal - addnum;
        return (abs(gapnum) - 1)/abs(limit) + 1;
    }
};

很遺憾只能滿足65 / 77 個通過測試用例。原因在于后面的測試用例中nums的和非常大，超出了int所能表示的范圍，因此我們還要考慮其他的方式。

為了防止超出范圍，我想到了一個方法：

在nums求和的過程中，想辦法讓和的絕對值小于limit，我們可以通過給這個和加上或者減去limit來實現這個效果，并分別記錄加上和減去的次數，這個次數在后面是可以相互抵消的。

依照這個思路可得到如下代碼：

class Solution {public:
    int minElements(vector& nums, int limit, int goal) {int addnum = 0;//nums的和(其中加上和減去了多個limit)
        int minustimes = 0;//減limit次數
        int plustimes = 0;//加limit次數
        for(auto num : nums){addnum += num;
            if(addnum >= limit){//過大則減
                addnum -= limit;
                ++minustimes;
            }
            if(addnum<= -limit){//過小則加
                addnum += limit;
                ++plustimes;
            }
        }
        int gapnum = goal - addnum;//goal與addnum的差值
        if(gapnum == 0)//正好為0時，可直接返回差值
            return abs(minustimes - plustimes);
        int remaintimes = (abs(gapnum) - 1)/abs(limit) + 1;//加減limit后還需limit的個數
        int totaltimes = 0;//總次數
        if(gapnum >0){//gapnum大于0時，remaintimes為加的次數
            totaltimes = abs(remaintimes + plustimes - minustimes);
        }else{//gapnum小于0時，remaintimes為減的次數
            totaltimes = abs(remaintimes + minustimes - plustimes);
        }
        return totaltimes;
    }
};

執(zhí)行用時：88 ms, 在所有 C++ 提交中擊敗了92.20%的用戶

內存消耗：71.6 MB, 在所有 C++ 提交中擊敗了78.72%的用戶

通過測試用例：77 / 77

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

當前標題：leetcode-1785-構成特定和需要添加的最少元素-創(chuàng)新互聯
URL分享：http://aaarwkj.com/article26/coedjg.html

成都網站建設公司_創(chuàng)新互聯，為您提供網站導航、營銷型網站建設、面包屑導航、網站排名、網站建設、全網營銷推廣

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯