力扣 前缀和

找子数组的个数了解前缀和的基础。

前缀和大致理解为到达某个位置，前面几个数的总和，即s[i+1]=s[i]+a[i+1]，可以通过一次循环获得。然后几个前缀和作差，即可得到某个位置到某个位置的和，根据map的键值对进行更新次数。

题目 

class Solution {
   public static int subarraySum(int[] nums, int k) {
        int count = 0;
        int sum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1); // 初始化前缀和为0的次数为1

        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];//计算前缀和
         //sum-k满足条件从某个位置到当前位置的连续子数组的和为k
         //sum[j]-sum[i]=k,k即i+1到j的元素之和
            if (map.containsKey(sum - k)) {
                //对应的次数累加
                count += map.get(sum - k);
            }
            //更新sum在map出现的次数，出现过就在原来的次数递增，没出现过初始化为1
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }

        return count;
    }
}

class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
       //双指针
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;//每到一个数就重置sum
            for (int j = i; j >= 0; j--) {
                sum += nums[j];//从当前的数开始往回进行累加，找组合数的和
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }
}

 

原文地址：https://blog.csdn.net/visitorcsdn/article/details/142834778

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！