LeetCode指北---前缀和&hash

今天搞一个简单的算法

先上题目：

没有用前缀 && hash 思想前，我们干撸的代码是这样子的。

   public int subarraySum(int[] nums, int k) {
       // 构造前缀和
       int res =0;
       int tempSum = 0;
       int[] preSum = new int[nums.length+1];
       // 累加和放入数组
       for (int i = 1; i < nums.length+1; i++) {
           tempSum += nums[i-1];
           preSum[i] = tempSum;
       }
       // O^2 遍历，获取的区间和是K的值
       for(int j=nums.length;j>=0;j--) {
          for(int i=0;i<j;i++) {
              if(preSum[j] - preSum[i] == k) {
                  res +=1;
              }
          }
       }
       return res;
   }

AC，但是结果用时很长，不开心🙃

那前缀&hash到底是什么，下面是题解代码：

 public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int sum = 0;
        int ret = 0;
        for(int i = 0; i < nums.length; ++i) {
            sum += nums[i];
            if(map.containsKey(sum-k)) // sum - k <==> j+1 j+2 ... i 子数组和为k  0到j子数组和为sum - k
                ret += map.get(sum-k);
            map.put(sum, map.getOrDefault(sum, 0)+1);
        }
        
        return ret;
    }

代码里的Map记录的是同样的和出现的次数，对每一个累计和sum，判断map里是否有sum-k

为什么是sum-k呢，why ？？？

仔细想想

• A[i] = A[0] + A[1] + A[2]+ …… +A[i]

• A[j] = A[0] + A[1] + A[2]+ …… +A[j]

如果A[j] - A[i] = A[i+1] + A[i+2] + …… +A[j] = k 的话，从i+1到j是满足条件的一个解把A[i]的值放入map中，当A[j]的值是A[i]+k的话，是满足条件的解，也就是判断一下sum -k 是否已经存在map里，统计符合这样A[j]，答案找到了。时间复杂度O(n)，AC结果也快了好多。

---

趁热打铁，再看一道题：

思路一致，需要注意的知识点：
java中负数做取模（%）运算，结果是负数，对应的整数结果应该是k+（sum%k）

  public int subarraysDivByK(int[] A, int K) {
        int res = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int preSum = 0;
        for (int i = 0; i < A.length; i++) {
            preSum += A[i];
            int temp = preSum % K < 0 ? (K + preSum % K) : preSum % K;
            if (map.containsKey(temp)) {
                res += map.get(temp);
            }
            map.put(temp, map.getOrDefault(temp, 0) + 1);
        }
        return res;
    }