美文网首页
前缀和+哈希表,剑指 Offer II 010. 和为 k 的子

前缀和+哈希表,剑指 Offer II 010. 和为 k 的子

作者: Abeants | 来源:发表于2022-07-23 12:17 被阅读0次

    剑指 Offer II 010. 和为 k 的子数组

    给定一个整数数组和一个整数 k ,请找到该数组中和为 k 的连续子数组的个数。

    示例 1:
    输入:nums = [1,1,1], k = 2
    输出: 2
    解释: 此题 [1,1] 与 [1,1] 为两种不同的情况

    示例 2:
    输入:nums = [1,2,3], k = 3
    输出: 2

    提示:
    1 <= nums.length <= 2 * 104
    -1000 <= nums[i] <= 1000
    -107 <= k <= 107

    来源:力扣(LeetCode)
    链接:https://leetcode.cn/problems/QTMn0o
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    解题思路及方法

    最初想的是滑动窗口、或者暴力,后面觉得前缀和貌似效率更高。

    我们并不需要构建一个数组来记录前缀和,只用维护一个变量sum,遍历数组时对sum进行更新,同时用一个map记录sum出现的次数。类似于力扣第一题两数之和,我们每次遍历时,都判断map中是否存在sum-k,存在则说明上一次出现sum的下标到遍历本次时的连续子数组和为k,记录出现sum-k的次数即可。

    class Solution {
        public int subarraySum(int[] nums, int k) {
            // 前缀和,map记录前i个数和以及出现次数
            Map<Integer, Integer> map = new HashMap<>();
            map.put(0, 1);
    
            int res = 0;
            // 记录前缀和
            int sum = 0;
            for (int i = 0; i < nums.length; i++) {
                sum += nums[i];
                // map存在sum - k,及说明存在i之前某一位置到i连续子数组和为k
                if (map.containsKey(sum - k)) {
                    res += map.get(sum - k);
                }
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
    
            return res;
        }
    }
    

    结果如下:

    剑指 Offer II 011. 0 和 1 个数相同的子数组

    给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组,并返回该子数组的长度。

    示例 1:
    输入: nums = [0,1]
    输出: 2
    说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。

    示例 2:
    输入: nums = [0,1,0]
    输出: 2
    说明: [0, 1] (或 [1, 0]) 是具有相同数量 0 和 1 的最长连续子数组。

    提示:
    1 <= nums.length <= 105
    nums[i] 不是 0 就是 1

    来源:力扣(LeetCode)
    链接:https://leetcode.cn/problems/A1NYOS
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    解题思路及方法

    和上一道题一样,也是前缀和+哈希表,注释已经写的很清楚了。这里说一下初始入map,没有元素时前缀和为0,但它的下边为-1,是为了后续计算子数组长度时用当前下标减去-1即可,就不用像计算普通长度时是j - i + 1。

    用变量sum记录前缀和,遇见1加1,遇见0减1,这样保证下一次当前缀和为sum且map中存在sum时,构成的子数组经过+相同数量的1和-相同数量的1,则代表子数组中有相同数量的0和1,对比长度即可。

    class Solution {
        public int findMaxLength(int[] nums) {
            int res = 0;
            // 记录前缀和
            int sum = 0;
            // 记录前缀和及下标
            Map<Integer, Integer> map = new HashMap<>();
            // 记录初始前缀和
            map.put(0, -1);
    
            for (int i = 0; i < nums.length; i++) {
                int num = nums[i];
                // 为1加1,为0减1
                if (num == 1) sum++;
                else sum--;
    
                // 如果map包含sum,及证明第一次出现sum的下标到此时sum组成的连续子数组包含相同0和1
                if (map.containsKey(sum)) {
                    res = Math.max(res, i - map.get(sum));
                } else {
                    // 仅记录第一次前缀和出现的下标,不更新后续出现位置
                    map.put(sum, i);
                }
            }
            
            return res;
        }
    }
    

    结果如下:

    相关文章

      网友评论

          本文标题:前缀和+哈希表,剑指 Offer II 010. 和为 k 的子

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