139. Subarray Sum Closest

Leave a comment

August 20, 2016 by oneOokay

求一个数组中,和的绝对值最小的一个subarray的起始index和终点index。利用“前缀和”来做。

先做一个Pair class用来存从第0个元素到第i个元素的综合以及index i

class Pair{
int sum;
int index;
public Pair(int s, int i) {
sum = s;
index = i;
}
}

public int[] subarraySumClosest(int[] nums) {
int[] result = new int[2]; //一个存储start index 和 end index的数组,用来返回结果
if (nums == null || nums.length == 0) {
return result;
}

int preSum = 0; // 0至前i – 1个数的和
Pair[] sums = new Pair[nums.length + 1]; //要比nums的长度多一个来存dummy
sums[0] = new Pair(0, – 1); //第一个 dummy,用来便于之后的比较
for (int i = 1; i < nums.length + 1; i ++){
sums[i] = new Pair(preSum + nums[i – 1], i – 1);
preSum = sums[i].sum;
}

Arrays.sort(sums, new Comparator<Pair>(){//按照sum的大小排列Sums数组。这样排好之后,相邻元素之间的差才有可能为最小。
public int compare(Pair a, Pair b) {
return a.sum – b.sum;
}
});

//而且由于sums数组已经按大小顺序排列好了,所以后一个元素减去前一个元素一定是正数,
int ans = Integer.MAX_VALUE;
for (int i = 1; i < nums.length + 1; i ++){
if (ans > sums[i].sum – sums[i – 1].sum) {
ans = sums[i].sum – sums[i – 1].sum;
int[] temp = new int[]{sums[i – 1].index, sums[i].index};
Arrays.sort(temp);
result[0] = temp[0] + 1; //这里注意要+1
result[1] = temp[1];
}
}
return result;

}

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: