title: Drop two elements to split the array to three part evenly in O(n)
body: <p>I encounter a problem to let you drop two elements in an array to make the three part's sum equal.</p>
  
  <pre><code>  Ex:
    1 2 4 3 5 2 1
    After I drop the 4 and 5, it becomes 1, 2 | 3 | 2, 1
  </code></pre>
  
  <p>Constraints:</p>
  
  <pre><code>  1.Numbers are all integer &gt; 0
  
    2.Drop two elements in the array, so the three splitted subarrays will have same subarray sum.
  </code></pre>
  
  <p>I have tried it by using two pass algorithm as the following</p>
  
  <p>First pass:O(n)
    Count the accumulated sum from the left so I can get the range sum easily.</p>
  
  <p>Second pass:O(n^2)
    Use nested loop to get the subarray's start and end index. Then, calculate the left, mid, right sum.</p>
  
  <pre><code>// 1.get accumulated sum map
  int[] sumMap = new int[A.length];
  int sum = 0;
  for(int i = 0; i &lt; A.length; i ++) {
      sum += A[i];
      sumMap[i] = sum;
  }
  
  // 2.try each combination
  for(int i = 1; i &lt; A.length - 1; i ++) {
      for(int j = i + 1; j &lt; A.length - 1; j ++) {
          int left = sumMap[i] - A[i];
          int mid = sumMap[j] - sumMap[i] - A[j];
          int right = sumMap[A.length - 1] - sumMap[j];
  
          if(left == mid &amp;&amp; mid == right)return true;
      }
  }
  </code></pre>
  
  <p>Are there any better algorithm that can achieve O(n)?</p>
  
  <p>Thanks</p>