Presum数组的建立 - Subarray Sum and cloest (lintcode 138, 139)

遇到subarray sum的问题,需要建立presum数组。presum的数组建立如下。

  1. 用hash table建立,简单

  2. 如果需要对presum进行排序。同时还要记录presum值,与index的对应关系时,建立vector<Node> presum, 其中Node记录sum与index。

  3. 不管怎么建立,always要初始化presum[0] = -1。表示index -1,对应sum为0,来对应从index 0开始的结果。同时,presum的区间,是(presum[small]+1, presum[large]), 有加1.

  4. Subarray Sum:

sum为0,表示前后presum值应该相等,注意扩展到sum为any target的情况。

vector<int> subarraySum(vector<int> nums){
        // write your code here
        vector<int> ret;
        if(nums.empty()) return ret;
        unordered_map<int, int> mp;
        mp[0] = -1;
        int sum = 0;
        for(int i=0; i<nums.size(); i++){
            sum += nums[i];
            if(mp.count(sum)){
                ret.push_back(mp[sum]+1);
                ret.push_back(i);
                break;
            }
            mp[sum] = i;
        }
        return ret;
    }
  1. Subarray Sum Cloest
    http://www.lintcode.com/en/problem/subarray-sum-closest/#

这道题的思路是对presum数组进行排序,然后两两比较(presum[i], presum[i+1])。因为排序后相邻两数之间差最小。

这道题如果扩展到cloest to a target,则比较难。需要用Treeset来找 lower bound。扩展阅读如下:
https://rafal.io/posts/subsequence-closest-to-t.html

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
     */
    struct Node{
        int value, idx; 
        Node(int v, int i) : value(v), idx(i){}
    }; 
    
    static bool comp(const Node &n1, const Node &n2){
        return n1.value < n2.value;
    }
    vector<int> subarraySumClosest(vector<int> nums){
        // write your code here
        if(nums.empty()) return vector<int>();
        vector<int> ret(2, 0);
        int len = nums.size();
        vector<Node> presum;
        presum.push_back(Node(0, -1));
        int sum = 0;
        for(int i=0; i<len; i++){
            sum += nums[i];
            presum.push_back(Node(sum, i));
        }
        sort(presum.begin(), presum.end(), comp);
        int min_diff = INT_MAX;
        for(int i=0; i<presum.size()-1; i++){
            int diff = abs(presum[i+1].value - presum[i].value);
            if(diff < min_diff){
                min_diff = diff;
                ret[0] = min(presum[i].idx, presum[i+1].idx)+1;
                ret[1] = max(presum[i].idx, presum[i+1].idx);
            }
        }
        return ret;
    }
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,779评论 0 33
  • Spring Cloud为开发人员提供了快速构建分布式系统中一些常见模式的工具(例如配置管理,服务发现,断路器,智...
    卡卡罗2017阅读 135,001评论 19 139
  • LeetCode 刷题随手记 - 第一部分 前 256 题(非会员),仅算法题,的吐槽 https://leetc...
    蕾娜漢默阅读 17,950评论 2 36
  • 从此以后,你的喜怒哀乐,你的一切都跟我没有关系,我会放下你,我也是有脾气的,我不会再为了你一再放下我自己本身的原则...
    zxcv108阅读 265评论 0 0
  • 我不敢直视太阳, 而你却向着太阳。 虽说唯有太阳与人心不可直视, 可我却折服于你的直视灼光的勇气。 可能这就是我所...
    酸酸甜甜涩阅读 274评论 0 0