Subarray Sum Closest

Subarray Sum Closest

题目地址

https://www.lintcode.com/problem/subarray-sum-closest/description

题目描述

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

代码

Approach #1 Two For loop

public class Solution {
  class Pair {
    int first, second;
    public Pair(int first, int second) {
      this.first = first;
      this.second = second;
    }
  }

  public Pair findSubArray(int arr[], int n) {
    int start = 0, end = 0, min_sum = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
      int curr_sum = arr[i];
      if (Math.abs(curr_sum) < min_sum) {
        min_sum = Math.abs(curr_sum);
        start = i;
        end = i;
      }

      for (int j = i + 1; j < n; j++) {
        curr_sum = curr_sum + arr[j];

        if (min_sum > Math.abs(curr_sum)) {
          min_sum = Math.abs(curr_sum);
          start = i;
          end = j;
        }
      }
    }

    Pair p = new Pair(start, end);
    return p;
  }
}

Approach #2 leftSum2 - leftSum1 = sum[1, 2]

public class Solution {
  class Pair {
    int first, second;
    public Pair(){}
    public Pair(int first, int second) {
      this.first = first;
      this.second = second;
    }
  }

  public Pair findSubArray(int nums, int n) {
    int start, end, min_diff = Integer.MAX_VALUE;
    ArrayList<Pair> list = new ArrayList<Pair>();
    Pair p0 = new Pair(0, -1);
    for (int i = 1; i < n; i++) {
      Pair pre = list.get(i - 1);
      Pair p = new Pair();
      p.first = pre.first + nums[i - 1];
      p.second = i - 1;
      list.add(p);
    }

    list.sort(new Comparator<Pair>() {
      public int compare(Pair p1, Pair p2) {
          return p1.first - p2.first;
      }
    });

    for (int i = 1; i < n; i++) {
      int diff = list.get(i).first - list.get(i - 1).first;
      if (min_diff > diff) {
          min_diff = diff;
          start = list.get(i - 1).second;
          end = list.get(i).second;
      }
    }

    return new Pair(start, end);
  }

}