Given an integer array, find a subarray with sum closest to zero. Return the indexes of the first number and last number.

Example

Given?[-3, 1, 1, -3, 5], return?[0, 2],?[1, 3],?[1, 1],?[2, 2]?or?[0, 4].

Challenge?

O(nlogn) time

這道題目思路目前還不是很清晰，有幾個不太懂的地方，需要回顧。

public class Solution {/*** @param nums: A list of integers* @return: A list of integers includes the index of the first number * and the index of the last number*/public int[] subarraySumClosest(int[] nums) {if (nums == null || nums.length == 0) {return null;}int res[] = new int[2];//為什么有個dummy node就可以包含單個的情況Pair[] sum = new Pair[nums.length + 1];sum[0] = new Pair(0, 0);int prev = 0;for (int i = 1; i <= nums.length; i++) {sum[i] = new Pair(i, prev + nums[i - 1]);prev = sum[i].sum;}Arrays.sort(sum, new Comparator<Pair>() {public int compare(Pair a, Pair b) {return a.sum - b.sum;}});int ans = Integer.MAX_VALUE;for (int i = 1; i <= nums.length; i++) {if (sum[i].sum - sum[i - 1].sum < ans) {ans = sum[i].sum - sum[i - 1].sum;int[] tmp = {sum[i].index - 1, sum[i - 1].index - 1};Arrays.sort(tmp);//有點不是很明白這里為什么要加上1res[0] = tmp[0] + 1;res[1] = tmp[1];}}return res;} }class Pair {int index;int sum;Pair(int index, int sum) {this.index = index;this.sum = sum;} }

?

轉載于:https://www.cnblogs.com/aprilyang/p/6263866.html

總結

以上是生活随笔為你收集整理的Lintcode Subarray Sum Closest的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。