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.

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

Challenge
O(nlogn) time
We are here

Link

Lintcode_ladder

Method

1. Create node{running sum, index}
   Sort nodes based on less value and less index when found equal value O(nlogn)
   Scan all differences of contiguous/continuous node, find the minimum difference, than record the index for the result O(n)
2. x

Example

1. 1

struct node {
    node(): val(0), pos(0){}
    node(int _val, int _pos):val(_val), pos(_pos) {}
    int val;
    int pos;
};
class Solution {
public:
    /**
     * @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
     */
    vector<int> subarraySumClosest(vector<int> nums){
        // write your code here
        if (nums.empty()) {
            return {};
        }
        int n = nums.size();
        vector<node> sum(n);
        vector<int> result(2);
        //sum[0] = node(nums[0], -1);
        sum[0].val = 0;
        sum[0].pos = -1;
        for (int i = 0; i < n; ++i) {
            sum[i].val = sum[i-1].val + nums[i];
            sum[i].pos = i;
        }
        // using lambda to customize STL sort()
        sort(sum.begin(), sum.end()
        , [](const struct node& n1, const struct node& n2) {
           return n1.val < n2.val || (n1.val == n2.val && n1.pos < n2.pos);
        });
        int ans = INT_MAX;
        for (int i = 0; i < n-1; ++i) {
            if (abs(sum[i+1].val - sum[i].val) < ans) {
                ans = abs(sum[i+1].val - sum[i].val);
                result[0] = min(sum[i+1].pos, sum[i].pos)+1;
                result[1] = max(sum[i+1].pos, sum[i].pos);
            }
        }
        return result;
    }
};

Similar problems

x

Tags

x