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。
实现：
1 class Solution 2 { 3 public: 4 bool splitArray(vector<int>& nums) 5 { 6 int n = nums.size(); 7 if (n < 7) return false; 8 vector<int> sum(n, 0); 9 sum[0] = nums[0]; 10 for (int i = 1; i < n; i++) sum[i] = sum[i - 1] + nums[i]; 11 for (int j = 3; j <= n - 4; j++) 12 { 13 unordered_set<int> st; 14 for (int i = 1; i < j - 1; i++) 15 { 16 if (sum[i - 1] == sum[j - 1] - sum[i]) st.insert(sum[i - 1]); 17 } 18 for (int k = j + 2; k <= n - 2; k++) 19 { 20 if (sum[k - 1] - sum[j] == sum[n - 1] - sum[k] && st.count(sum[k - 1] - sum[j])) 21 return true; 22 } 23 } 24 return false; 25 } 26 }