=================================================================

 

I think the following is O(nlogn).

Given an array A in which we need to find the contiguous sub-array of sum k, create a new Array B such that

B[i] = Sum j = 1 to i A[i]

i.e B[m] = A[1] + A[2] + ...  A[m] is the prefix sum array of A.

Now create a third array C such that C[i] = (B[i], i) (ordered pairs)

Now sort array C using the values B only (i.e ignore the second co-ordinate of the ordered pair).

Now for each element C[p] =  (B[q],q) do a binary search for B[q] + K in C. Say you find the element(s) C[r] = (B[s], s)

if q < s, then we are done, else continue.

(Note, we might have to create a new array C' by merging sub-arrays with same value of B and also store the set of indices of B which take that value i.e. instead of just using the ordered pair (B,i) we use (B, {i1, i2, ..., ik}) and do a binary search on C')

+++++++++++++++++++++++++++++++++++++++++++++++++++

这个题目不同于找最大之和，最大之和的解能在O(1)空间下,在O(n)时间内完成

Digest from http://discuss.techinterview.org/?interview

----------------------------------------------------------

I have an array consisting of 2n+1 elements. n elements in it are
married, i.e they occur twice in the array, however there is one element
which only appears once in the array. I need to find that number in a
single pass using constant memory. {assume all are positive numbers}
Eg : 3 4 1 3 1 7 2 2 4
Ans: 7

===============================================

var array = [3, 4, 1, 3, 1, 7, 2, 2, 4]
var remaining = 0;

for(var i = 0; i < array.length; i++)
{
  remaining ^= array[i];
}

return remaining;

 

==========================================================

首先，应该用原地置换的思想。2，用两个指针，分别指向0和k＋1位置。两个比较，

小的换到0的那个指针(表示全局的较小)，后面那个指针得到的换过来的元素要和它的后续比较一下，

要确定这个指针所指是后半部分的最小。这样两指针一直从左到右移动，就排序完了。