leetcode548 Split Array with Equal Sum

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

思路：

使用哈希表降低复杂度。具体来说：

枚举j:

枚举i，如果sum[i - 1] == sum[j - 1] - sum[i]，就用哈希表把sum[i - 1]记录下来；

枚举k，如果sum[k - 1] - sum[j] == sum[n - 1] - sum[k]并且哈希表中存在sum[k - 1] - sum[j]，返回true。

返回false。

实现：

 class Solution

 {

 public:

     bool splitArray(vector<int>& nums)

     {

         int n = nums.size();

         if (n < ) return false;

         vector<int> sum(n, );

         sum[] = nums[];

         for (int i = ; i < n; i++) sum[i] = sum[i - ] + nums[i];

         for (int j = ; j <= n - ; j++)

         {

             unordered_set<int> st;

             for (int i = ; i < j - ; i++)

             {

                 if (sum[i - ] == sum[j - ] - sum[i]) st.insert(sum[i - ]);

             }

             for (int k = j + ; k <= n - ; k++)

             {

                 if (sum[k - ] - sum[j] == sum[n - ] - sum[k] && st.count(sum[k - ] - sum[j]))

                     return true;

             }

         }

         return false;

     }

 }