方法1 纯暴力

思路:
i:左端点
j:右端点
然后用z统计[i,j]之间的值
时间复杂度 o(n3)

方法2 暴力算法优化

用z统计[i,j]之间的值,当j–>j+1,其实不需要从头统计[i,j],[i,j+1]=[i,j]+num[j+1]

 // 法一 暴力public int subarraySum(int[] nums, int k) {int sum;int res =0;for (int i = 0; i < nums.length; i++) {sum=0;for (int j = i; j < nums.length; j++) {sum+=nums[j];if (sum==k){res++;}}}return res;}

法三 前缀和

思路:
求出所有元素的前缀,然后使用i,j穷举出所有的前缀差,=k,就+1
前缀和关键:
prefixNum[i] num[i]前面的元素(不包括自身)的和

==if (prefixSum[j+1]-prefixSum[i]k) // 用我前面的(包括我)-别人前面的(不包括别人),这样可以列举所有的情况,当i=j时,代表只有num[i]

public int subarraySum02(int[] nums, int k) {int[] prefixSum=new int[nums.length+1]; //prefixNum[i]  num[i]前面的元素(不包括自身)的和int res =0;prefixSum[0]=0;for (int i = 0; i < nums.length; i++) {prefixSum[i+1]=prefixSum[i]+nums[i];}for (int i = 0; i < nums.length; i++) {for (int j = i; j < nums.length; j++) {if (prefixSum[j+1]-prefixSum[i]==k)  // 用我前面的(包括我)-别人前面的(不包括别人)res++;}}return res;}