Python, Simple Explanation


  • 2

    Let A be the array. As in most problems involving querying the sum of contiguous elements of an array, let P[x] = sum(A[:x]) be the prefix sums of A, which can be found in linear time.

    Then the sums in question are P[i] = P[j] - P[i+1] = P[k] - P[j+1] = P[-1] - P[k+1]. For every j < k, P[i] = P[-1] - P[k+1] is a necessary requirement to choose i, so let's iterate over those indices first. This gives us the advantage that since we are iterating over a sorted list of candidate indices i, we can break when i >= j.

    def splitArray(self, A):
        P = [0]
        for x in A: P.append(P[-1] + x)
        
        N = len(A)
        Pinv = collections.defaultdict(list)
        for i, u in enumerate(P):
            Pinv[u].append(i)
            
        for j in xrange(1, N-1):
            for k in xrange(j+1, N-1):
                for i in Pinv[P[-1] - P[k+1]]:
                    if i >= j: break
                    if P[i] == P[j] - P[i+1] == P[k] - P[j+1]:
                        return True
        return False
    

  • 0
    R

    @awice said in Python, Simple Explanation:

    def splitArray(self, A):
    P = [0]
    for x in A: P.append(P[-1] + x)

    N = len(A)
    Pinv = collections.defaultdict(list)
    for i, u in enumerate(P):
        Pinv[u].append(i)
        
    for j in xrange(1, N-1):
        for k in xrange(j+1, N-1):
            for i in Pinv[P[-1] - P[k+1]]:
                if i >= j: break
                if P[i] == P[j] - P[i+1] == P[k] - P[j+1]:
                    return True
    return False
    

    To add to the explanation above, the hashmap's purpose is to store places where the sum (key) has the value (a list of positions in the sum array)

    Also, for i in Pinv[P[-1] - P[k+1]]: is slightly confusing, but the purpose is to take the sum from the last element in the sum array and subtract from the k+1 position.... this inherently should equal the equal sums in the list of "equal sum" stored in hashmap. Now if you take the list and iterate through the first items, just stop once you reach something above or equal to i.


  • 0
    R

    Feel free to help me optimize the solutions below. They are barely passing 4% on the judge.

    C++ solution:

    class Solution {
    public:
        bool splitArray(vector<int>& nums) {
            vector<int> sms;
            sms.push_back(0);
            int N = nums.size();
            
            for(auto i : nums) {
                sms.push_back(sms[sms.size()-1] + i);
                
            }
            
            unordered_map<int, vector<int>> hsh;
            
            for(int i = 0; i < sms.size(); i++) {
                hsh[sms[i]].push_back(i);
            }
            
            for(int i = 1; i < N - 1; i++ ) {
                for(int j = i + 1; j < N -1 ; j++) {
                    for(auto f: hsh[sms[sms.size()-1] - sms[j+1]]) {
                        if(f >= i) break;
                        if(sms[f] == sms[i] - sms[f+1] && sms[f] == sms[j] - sms[i+1]) {
                            return true;
                        }
                    }
                }
            }
            return false;
        }
    };
    

    Java Solution:

    public class Solution {
        public boolean splitArray(int[] nums) {
            ArrayList<Integer> sms = new ArrayList<Integer>();
            sms.add(0);
            int N = nums.length;
            
            for(int i : nums) {
                sms.add(sms.get(sms.size()-1) + i);
                
            }
            
            HashMap<Integer, ArrayList<Integer>> hsh = new HashMap<Integer, ArrayList<Integer>>();
            
            for(int i = 0; i < sms.size(); i++) {
                if(hsh.get(sms.get(i)) != null) {
                    hsh.get(sms.get(i)).add(i);
                } else {
                    hsh.put(sms.get(i), new ArrayList<Integer>());
                    hsh.get(sms.get(i)).add(i);
                }
            }
            
            for(int i = 1; i < N - 1; i++ ) {
                for(int j = i + 1; j < N -1 ; j++) {
                    for(int f : hsh.getOrDefault(sms.get(sms.size()-1) - sms.get(j+1), new ArrayList<Integer>())) {
                        if(f >= i) break;
                        if(sms.get(f) == sms.get(i) - sms.get(f+1) && sms.get(f) == sms.get(j) - sms.get(i+1)) {
                            return true;
                        }
                    }
                }
            }
            return false;
        }
    }
    
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.