美文网首页
LeetCode数组Subarray求和问题

LeetCode数组Subarray求和问题

作者: 专职跑龙套 | 来源:发表于2018-04-06 17:17 被阅读76次

    关于我的 Leetcode 题目解答,代码前往 Github:https://github.com/chenxiangcyr/leetcode-answers


    LeetCode题目:560. Subarray Sum Equals K
    Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

    Example 1:

    Input:nums = [1,1,1], k = 2
    Output: 2

    Note:

    • The length of the array is in range [1, 20,000].
    • The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

    以下代码的时间负责度为O(n^2)

    class Solution {
        public int subarraySum(int[] nums, int k) {
            if(nums == null || nums.length == 0) return 0;
            
            // sum[i]记录前i个元素的和
            int[] sum = new int[nums.length];
            sum[0] = nums[0];
            for(int i = 1; i < nums.length; i++) {
                sum[i] = sum[i - 1] + nums[i];
            }
            
            int count = 0;
            // 遍历各个range
            for(int i = 0; i < nums.length; i++) {
                for(int j = i; j < nums.length; j++) {
                    if((sum[j] - (i == 0 ? 0 : sum[i - 1])) == k) {
                        count++;
                    }
                }
            }
            
            return count;
        }
    }
    

    以下代码的时间负责度为O(n)

    class Solution {
        public int subarraySum(int[] nums, int k) {
            int count = 0;
            int sum = 0;
            
            // key: 累计和sum, value: 从idx = 0 开始有多少种方式可以累积到该sum
            HashMap <Integer, Integer> map = new HashMap < > ();
            map.put(0, 1);
            
            for (int i = 0; i < nums.length; i++) {
                sum = sum + nums[i];
                
                if (map.containsKey(sum - k)) {
                    count = count + map.get(sum - k);
                }
                
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
            
            return count;
        }
    }
    

    LeetCode题目:325. 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?

    以下代码的时间负责度为O(n^2)

    class Solution {
        public int maxSubArrayLen(int[] nums, int k) {
            if(nums == null || nums.length == 0) return 0;
            
            // sum[i]记录前i个元素的和
            int[] sum = new int[nums.length];
            sum[0] = nums[0];
            for(int i = 1; i < nums.length; i++) {
                sum[i] = sum[i - 1] + nums[i];
            }
            
            int max = 0;
            // 遍历各个range
            for(int i = 0; i < nums.length; i++) {
                for(int j = i; j < nums.length; j++) {
                    if((sum[j] - (i == 0 ? 0 : sum[i - 1])) == k) {
                        max = Math.max(max, j - i + 1);
                    }
                }
            }
            
            return max;
        }
    }
    

    以下代码的时间负责度为O(n)

    class Solution {
        public int maxSubArrayLen(int[] nums, int k) {
            
            int max = 0;
            int sum = 0;
            
            // key: 累计和sum, value: 从idx = 0 开始第一次累积到该sum 的索引位置
            // 为什么保存第一次的位置,因为是求 max size
            HashMap <Integer, Integer> map = new HashMap < > ();
            map.put(0, -1);
            
            for (int i = 0; i < nums.length; i++) {
                sum = sum + nums[i];
                
                if (map.containsKey(sum - k)) {
                    max = Math.max(max, i - map.get(sum - k));
                }
                
                if (!map.containsKey(sum)) {
                    map.put(sum, i);
                }
            }
            
            return max;
        }
    }
    

    LeetCode题目:[53. Maximum Subarray]
    (https://leetcode.com/problems/maximum-subarray/description/)
    Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

    For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
    the contiguous subarray [4,-1,2,1] has the largest sum = 6.

    以下代码的时间负责度为O(n^2)

    class Solution {
        public int maxSubArray(int[] nums) {
            int max = Integer.MIN_VALUE;
            
            for(int i = 0; i < nums.length; i++) {
                int sum = 0;
                for(int j = i; j < nums.length; j++) {
                    sum = sum + nums[j];
                    
                    max = Math.max(max, sum);
                }
            }
            
            return max;
        }
    }
    

    以下代码的时间负责度为O(n)

    class Solution {
        public int maxSubArray(int[] nums) {
            // dp[i] means the maximum subarray ending with A[i]
            int[] dp = new int[nums.length];
            
            // init
            dp[0] = nums[0];
            int max = dp[0];
            
            for(int i = 1; i < nums.length; i++){
                dp[i] = nums[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
                
                max = Math.max(max, dp[i]);
            }
            
            return max;
        }
    }
    

    相关文章

      网友评论

          本文标题:LeetCode数组Subarray求和问题

          本文链接:https://www.haomeiwen.com/subject/ozjshftx.html