Subarray Sum related

Leave a comment

March 4, 2017 by oneOokay


Subarray Sum

Given an integer array, find a subarray where the sum of numbers is zero. Your code should return the index of the first number and the index of the last number.


给一个数组:找到一个subarray使得subarray sum 为 0.返回第一个数和最后一个数的index

 HashMap<Integer, Integer>来存一个running sum和当前的index值.
找map里面是否已经存在这个running sum:若存在说明从map.get(sum)后一个元素到当前的i的元素的这个subarray和为0.
public static ArrayList subarraySum(int[] nums) {
        int len = nums.length;
        ArrayList<Integer> ans = new ArrayList<>();
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        map.put(0, -1);
        int sum = 0;
        for (int i = 0; i < len; i++) {
            sum += nums[i];
            if (map.containsKey(sum)) {
                ans.add(map.get(sum) + 1);
                ans.add(i);
                return ans;
            }
            map.put(sum, i);
        }
        return ans;
    }

Subarray Sum Closest

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


找到一个subarray使得subarray中元素的和最接近于0.

 

 

Maximum Size Subarray Sum Equals k 

Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn’t one, return 0 instead.

Note:
The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.

Example 1:

Given nums = [1, -1, 5, -2, 3], k = 3,
return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)

Example 2:

Given nums = [-2, -1, 2, 1], k = 1,
return 2. (because the subarray [-1, 2] sums to 1 and is the longest)

Follow Up:
Can you do it in O(n) time?


没有写出来但是我觉得我整个思路过程有点好玩.

第一反应:最优的肯定是用dp做,但是用dfs也能做出来.(事实上完全是错误)

先尝试了dfs+backtracking:dfs+backtracking事实上是建一个搜索树的过程,一次性走到一个叶子节点,然后再往上回溯; 到一个parent之后,跳过左儿子往找右儿子.注意这里就是完全错误的, 结果出来的array并不是连!续!的!不满足subarray这个条件. 所以这题根本不能够用这个方法(摊手

好,所以要subarray,那么brutal force两个for 循环肯定是可以的(逃避dp).brutal force很容易写出来很明显TLE

终于开始想dp.二维dp[i][j]来表示从i到j的元素和,找相差最大的i,j即可. 进一步,不用二维dp,一维就可以dp[i]表示,从0-i的所有元素的和.找到相差最大的i和j使得dp[j]-dp[i] == k.问题就转换成了
给你一个一维数组(duplicates exist),求数组中一对距离最大的元素使得他们的和/差为k.

然后卡在这里了(当然是因为基础不牢固啦)此时应该想到2 Sum呀敲黑板!!!就okay了.

2 sum: 用了hashmap. 这里是array里面会存在duplicates.由于是求最大距离,所以在从左往右扫的过程中,如果map已经包含元素了,那么skip,不更新map.因为取前面的元素能够构成的距离最大.

public int maxSubArrayLen(int[] nums, int k) {
        if (nums == null || nums.length == 0) return 0;        
        Map<Integer, Integer> map = new HashMap<>();
        int sum = 0;
        int max = 0;
        for (int i = 0; i < nums.length; i ++){
            sum += nums[i];
            if (sum == k) max = i + 1;
            else if (map.containsKey(sum - k)) //sum - k不是k - sum
                max = Math.max(max, i - map.get(sum - k));//这里不用+1
            if (!map.containsKey(sum)) map.put(sum, i);
        }
        return max;
    }


Continuous Subarray Sum

Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.

Example 1:

Input: [23, 2, 4, 6, 7],  k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.

Example 2:

Input: [23, 2, 6, 4, 7],  k=6
Output: True
Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.

Note:

  1. The length of the array won’t exceed 10,000.
  2. You may assume the sum of all the numbers is in the range of a signed 32-bit integer.

一个array,里面都是非负数,一个integer k. 判断该数组是否存在一个size至少为2的continuos subarray使得subarray sum是k的倍数.

这个和上面的Maximum Size Subarray Sum Equals k是一样的,都有subarray sum.

这题的技巧在于:

  1. 把什么放到map里面.这题是把runningSum % k的值放到map里面.(我觉得这个想法超级聪明!)
  2. 对于corner case的处理: 注意给的target k是一个integer,所以可能为0. 存在corner case[0,0] target = 0.这种情况下runningSum不能够%0.
    • runningSum %= k来解决.因为我们只关注是否能够被k整除,只要能够保证这个特性不变那么runningSum的值改变也没关系
    • map里面放入(0,-1)
public boolean checkSubarraySum(int[] nums, int k) {
        if (nums == null || nums.length <= 1) return false;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int runningSum = 0;
        for (int i = 0; i < nums.length; i ++){
             runningSum += nums[i];
             if (k != 0) runningSum %= k; 
            if (map.containsKey(runningSum)){
                 if (i - map.get(runningSum) >= 2) return true;
            }else map.put(runningSum, i); 
        }
        return false;
    }
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: