文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給你一個長度為 2 * n 的整數數組。
你需要將 nums 分成 兩個 長度為 n 的數組，分別求出兩個數組的和，并 最小化 兩個數組和之 差的絕對值 。
nums 中每個元素都需要放入兩個數組之一。

請你返回 最小 的 數組和之差。

示例 1： 輸入：nums = [3,9,7,3] 輸出：2 解釋：最優分組方案是分成 [3,9] 和 [7,3] 。 數組和之差的絕對值為 abs((3 + 9) - (7 + 3)) = 2 。示例 2： 輸入：nums = [-36,36] 輸出：72 解釋：最優分組方案是分成 [-36] 和 [36] 。 數組和之差的絕對值為 abs((-36) - (36)) = 72 。示例 3： 輸入：nums = [2,-1,0,4,-2,-9] 輸出：0 解釋：最優分組方案是分成 [2,4,-9] 和 [-1,0,-2] 。 數組和之差的絕對值為 abs((2 + 4 + -9) - (-1 + 0 + -2)) = 0 。提示： 1 <= n <= 15 nums.length == 2 * n -10^7 <= nums[i] <= 10^7

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/partition-array-into-two-arrays-to-minimize-sum-difference
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• 數組折半，分別對一半進行狀態枚舉
• 枚舉一邊取的數的個數，將左右的滿足二進制位個數的狀態取出，排序，雙指針求解最接近的
• 時間復雜度 $O(n?2^n)$

class Solution { public:int minimumDifference(vector<int>& nums) {int n = nums.size()/2;int sum = accumulate(nums.begin(), nums.end(), 0);vector<int> a(nums.begin(),nums.begin()+n), b(nums.begin()+n,nums.end());vector<int> stateSum1 = getsum(a);//獲取所有狀態的和vector<int> stateSum2 = getsum(b);int dis = INT_MAX;for(int x = 0; x <= n; ++x){ // 第一個數組取x個數int y = n-x; // 第二個數組取y個數vector<int> s1, s2;//把兩邊取出來的和存儲for(int state = 0; state < (1<<n); ++state){if(count1(state)==x)s1.push_back(stateSum1[state]);}for(int state = 0; state < (1<<n); ++state){if(count1(state)==y)s2.push_back(stateSum2[state]);}sort(s1.begin(), s1.end());//排序，雙指針，求解最接近的sort(s2.begin(), s2.end());int len1 = s1.size(), len2 = s2.size();int i = 0, j = len2-1;while(i < len1 && j >= 0){dis = min(dis, abs(sum-2*(s1[i]+s2[j])));if(s1[i]+s2[j] > sum-(s1[i]+s2[j]))j--;else if(s1[i]+s2[j] < sum-(s1[i]+s2[j]))i++;elsereturn 0;}}return dis;}vector<int> getsum(vector<int>& num){int n = num.size();vector<int> ans(1<<n);for(int i = 0; i < n; ++i){ans[1<<i] = num[i]; // 初始化}for(int state = 1; state < (1<<n); ++state){int prevstate = state&(state-1);ans[state] = ans[state-prevstate] + ans[prevstate];}return ans;}int count1(int x){ // 計算二進制1的個數int ans = 0;while(x){ans++;x = x&(x-1);}return ans;} };

692 ms 76.4 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 2035. 将数组分成两个数组并最小化数组和的差（状态压缩DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。