leetcode刷题记录 5
Joking7.28
没注意到越界问题 用二分的另一种写法可以避免越界不用long
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public class Solution extends GuessGame {
public int guessNumber(int n) {
int ans = 1+(n-1)/2;
int res,left=1,right=n;
while(true) {
res = guess(ans);
if(res == 0) break;
if(res == -1) {
right=ans-1;
}else{
left=ans+1;
}ans= left+(right-left) /2 ;
}return ans;
}
}
|
REVIEW
超时了 思路错了 看题解吧
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
long ans = -1;
public long maxScore(int[] nums1, int[] nums2, int k) {
getScore(nums1,nums2,k,0,new TreeSet<Integer>(),0);
return ans;
}
public void getScore(int[] nums1, int[] nums2, int k, int begin, TreeSet<Integer> set,long sum) {
if(k==0) {
ans = Math.max(ans,sum*set.first());
return;
}
if(k>nums1.length-begin) return;
for(int i=begin;i<nums1.length;i++) {
if(!set.contains(nums2[i])){
set.add(nums2[i]);
getScore(nums1,nums2,k-1,i+1,set,sum+nums1[i]);
set.remove(nums2[i]);
}else getScore(nums1,nums2,k-1,i+1,set,sum+nums1[i]);
}
}
}
|
我根本连题解都看不懂啊…好烦啊 好像又看懂了
非常难想的转换问题 要对nums2排序并对排序后的nums遍历 可以确定遍历后max只会越来越大 是某种贪心吧?题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public long maxScore(int[] nums1, int[] nums2, int k) {
int n = nums2.length;
Integer[] idxs = new Integer[n];
for (int i = 0 ; i < n ; i++) {
idxs[i] = i;
}
Arrays.sort(idxs, (i, j) -> nums2[j] - nums2[i]);
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
long sum = 0L, max = 0L;
for (int i : idxs) {
int x = nums1[i];
int y = nums2[i];
minHeap.offer(x);
sum += (minHeap.size() <= k) ? x : (x - minHeap.poll());
if (minHeap.size() == k) {
max = Math.max(max, (sum * y));
}
}
return max;
}
}
|
牛马题目天天测溢出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| class Solution {
public long totalCost(int[] costs, int k, int candidates) {
int costSLen = costs.length,candidatesLen = candidates*2;
long ans=0;
if(candidatesLen<costSLen){
PriorityQueue<Integer> pqFront = new PriorityQueue<>(),pqBack = new PriorityQueue<>();
for(int i=0;i<candidates;++i){
pqFront.add(costs[i]);
pqBack.add(costs[costSLen-i-1]);
}
int indexFront = candidates,indexBack = costs.length-1-candidates;
for(int i=0;i<k;++i,--costSLen){
if(pqFront.isEmpty()){
ans += pqBack.poll();
}else if(pqBack.isEmpty()){
ans += pqFront.poll();
}else {
int frontCost = pqFront.peek(), backCost = pqBack.peek();
if (frontCost <= backCost) {
ans += pqFront.poll();
if (indexFront <= indexBack) {
pqFront.offer(costs[indexFront++]);
}
} else {
ans += pqBack.poll();
if (indexFront <= indexBack) {
pqBack.offer(costs[indexBack--]);
}
}
}
}
}else{
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int i=0;i<costSLen;++i){
pq.add(costs[i]);
}
for(int i=0;i<k;++i){
ans+=pq.poll();
}
}
return ans;
}
}
|
别人写的 判断的是 2*candidate+k<=n 非常妙 这样就少了一大堆麻烦的if
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution {
public long totalCost(int[] costs, int k, int candidates) {
int n = costs.length;
long ans = 0;
if (candidates * 2 + k > n) {
Arrays.sort(costs);
for (int i = 0; i < k; i++) {
ans += costs[i];
}
return ans;
}
PriorityQueue<Integer> pre = new PriorityQueue<>();
PriorityQueue<Integer> suf = new PriorityQueue<>();
for (int i = 0; i < candidates; i++) {
pre.offer(costs[i]);
suf.offer(costs[n - 1 - i]);
}
int i = candidates;
int j = n - 1 - candidates;
while (k-- > 0) {
if (pre.peek() <= suf.peek()) {
ans += pre.poll();
pre.offer(costs[i++]);
} else {
ans += suf.poll();
suf.offer(costs[j--]);
}
}
return ans;
}
}
|
7.29
呃 一遍过 就遍历组合加剪枝呗?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> res = new ArrayList<>();
getSum(res,k,n,0,new ArrayList<>(),1);
return res;
}
void getSum(List<List<Integer>> res,int k,int n, int sum, List<Integer> list,int index) {
if(k==0){
if(sum==n){
res.add(new ArrayList<>(list));
}return ;
}
if(10-index<k) return;
for(int i=index;i<=9;i++){
if(n-sum-i+1<k)break;
list.add(i);
getSum(res,k-1,n,sum+i,list,i+1);
list.remove(list.size()-1);
}
}
}
|
REVIEW
调了半天 拉 看看怎么优化 53ms > 9.02%
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int[] successfulPairs(int[] spells, int[] potions, long success) {
Arrays.sort(potions);
int [] result = new int[spells.length];
int index=0;
for(int spell : spells)
result[index++]=getNum(spell, potions, success);
return result;
}
int getNum(int spell, int[] potions, long success) {
long target = success/spell + (success%spell==0?0:1);
int left = 0, right = potions.length-1;
while(left <= right) {
int mid = left + (right-left)/2;
if(potions[mid]>=target&&(mid==0||(potions[mid-1]<target))) {return potions.length-mid;}
if(potions[mid]<target) {left=mid+1;}
if(potions[mid]>=target) {right=mid-1;}
}return 0;
}
}
|
折腾了好久结果时间越来越长了… 提交三次结果越来越久了 哈哈哈
看了别人的代码 说实话没看太懂 他好像在写一种很新的二分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
public int[] successfulPairs(int[] spells, int[] potions, long success) {
Arrays.sort(potions);
for (int i = 0; i < spells.length; i++) {
long target = (success - 1) / spells[i];
if (target < potions[potions.length - 1]) {
spells[i] = potions.length - upperBound(potions, (int) target);
} else {
spells[i] = 0;
}
}
return spells;
}
private int upperBound(int[] nums, int target) {
int left = -1, right = nums.length;
while (left + 1 < right) {
int mid = (left + right) >>> 1;
if (nums[mid] > target) {
right = mid;
} else {
left = mid;
}
}
return right;
}
}
|
又看了官解写了一遍 47ms > 49.53% 其实我只要能写出来就行吧??
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int[] successfulPairs(int[] spells, int[] potions, long success) {
Arrays.sort(potions);
int [] result = new int[spells.length];
int index=0;
for(int spell : spells)
result[index++]=getNum(spell, potions, success);
return result;
}
int getNum(int spell, int[] potions, long success) {
long target = (success + spell - 1) / spell - 1;
int left = 0, right = potions.length-1,res=right+1;
while(left <= right) {
int mid = left + (right-left)/2;
if(potions[mid]>target) {
res = mid;
right=mid-1;
}else {left=mid+1;}
}return potions.length-res;
}
}
|
REVIEW
真没思路啊 看了题解 特点是暴力算时间 在非数组二分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public int minEatingSpeed(int[] piles, int h) {
int left = 1, right = 0;
for(int i:piles) right = Math.max(right, i);
int ans = right;
while(left < right) {
int mid = left + (right - left) / 2;
long time = getTime(piles,mid);
if(time <= h){
ans = mid;
right = mid;
}
else {
left = mid +1;
}
}
return ans;
}
long getTime(int[] piles, int pile) {
long res = 0;
for(int i:piles)
res += (i+pile-1)/pile;
return res;
}
}
|
二分好难
7.30
没想出状态转移公式 找规律找出来了 用int和不%会溢出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public int numTilings(int n) {
if(n == 1) return 1;
if(n == 2) return 2;
if(n == 3) return 5;
int index = 3;
long num1=1,num2=2,num3=5,tmp;
while(index<n){
tmp=num3;
num3=2*num3+num1;
num1=num2;
num2=tmp;
if(num1>1000000007){
num1%=1000000007;
num2%=1000000007;
num3%=1000000007;
}
++index;
}return (int) (num3%(1000000007));
}
}
|
简单的dp
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public int minCostClimbingStairs(int[] cost) {
int len = cost.length;
int []dp = new int[len+1];
dp[0] = 0; dp[1] = 0;
for(int i=2;i<=len;i++){
dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
}
return dp[len];
}
}
|
简单dp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int tribonacci(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
if (n == 2) return 1;
int num1 = 0, num2 = 1, num3 = 1,tmp;
int index=2;
while(index<n){
++index;
tmp=num1+num2+num3;
num1=num2;
num2=num3;
num3=tmp;
}return num3;
}
}
|
7.31
最简单的多维dp 话说我差点忘了多维dp怎么写了
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public int uniquePaths(int m, int n) {
int [][]dp = new int[m][n];
for(int i = 0; i < m; i++) dp[i][0] = 1;
for(int i=0;i<n;i++) dp[0][i] = 1;
for(int i = 1; i < m; i++)
for(int j = 1; j < n; j++)
dp[i][j] = dp[i-1][j] + dp[i][j-1];
return dp[m-1][n-1];
}
}
|
我去 我是真忘了怎么写多维dp了 这么简单经典的题我还推导了好一会
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length();
int n = text2.length();
char[] chars1 = text1.toCharArray(), chars2 = text2.toCharArray();
int[][] dp = new int[m][n];
dp[0][0] = chars1[0] == chars2[0] ? 1 : 0;
for (int i = 1; i < m; i++) {
if(dp[i-1][0]==1)dp[i][0] = 1;
else dp[i][0] = chars1[i]==chars2[0]?1:0;
}
for (int i = 1; i < n; i++) {
if(dp[0][i-1]==1)dp[0][i] = 1;
else dp[0][i] = chars2[i]==chars1[0]?1:0;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = Math.max(dp[i-1][j-1] + (chars1[i]==chars2[j]?1:0), Math.max(dp[i-1][j], dp[i][j-1]));
}
}
return dp[m-1][n-1];
}
}
|
判断可以优化一下 12ms -> 9ms
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length();
int n = text2.length();
char[] chars1 = text1.toCharArray(), chars2 = text2.toCharArray();
int[][] dp = new int[m][n];
dp[0][0] = chars1[0] == chars2[0] ? 1 : 0;
for (int i = 1; i < m; i++) {
if(dp[i-1][0]==1)dp[i][0] = 1;
else dp[i][0] = chars1[i]==chars2[0]?1:0;
}
for (int i = 1; i < n; i++) {
if(dp[0][i-1]==1) dp[0][i] = 1;
else dp[0][i] = chars2[i]==chars1[0]?1:0;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if(chars1[i]==chars2[j]) dp[i][j] = dp[i-1][j-1]+1;
else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[m-1][n-1];
}
}
|
没想出来… 沟槽的不是多维dp你标什么多维dp
两个dp数组 一个表示不持有股票的一个表示持有股票的
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public int maxProfit(int[] prices, int fee) {
int [][]dp = new int[prices.length][2];
dp[0][1] = -prices[0];
for(int i=1;i<prices.length;i++){
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]-fee);
dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
}
return dp[prices.length-1][0];
}
}
|
还有个贪心的算法 不好想 维护一个最小费用 其实就是无限假买假卖 墙头草
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int maxProfit(int[] prices, int fee) {
int n = prices.length;
int buy = prices[0] + fee;
int profit = 0;
for (int i = 1; i < n; ++i) {
if (prices[i] + fee < buy) {
buy = prices[i] + fee;
} else if (prices[i] > buy) {
profit += prices[i] - buy;
buy = prices[i];
}
}
return profit;
}
}
|
8.1
7ms 别人怎么只用1ms
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public int[] countBits(int n) {
int []ans = new int[n+1];
for(int i=1;i<=n;i++){
int num = i;
for(int j=1;j<=32;j++){
if((num & 1) == 1)++ans[i];
num >>>= 1;
}
}
return ans;
}
}
|
牛逼 复用前面的
1
2
3
4
5
6
7
8
9
10
| class Solution {
public int[] countBits(int n) {
int[] ans = new int[n + 1];
for (int i = 1; i <= n; i++)
ans[i] = ans[i >> 1] + (i & 1);
return ans;
}
}
|
条件写得比较复杂
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int minFlips(int a, int b, int c) {
int ans=0;
for(int i=1;i<=32;++i){
if((c & 1) == 0){
if((b&1)==1){
if((a&1)==1) ans+=2;
else ++ans;
}else if((a&1)==1) ++ans;
}else{
if((b&1)==0 && (a&1)==0) ans++;
}
a>>=1;b>>=1;c>>=1;
}return ans;
}
}
|
调试了一下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class StockSpanner {
Deque<int[]> stack;
public StockSpanner() {
stack = new LinkedList<>();
}
public int next(int price) {
int day=1;
if(stack.isEmpty()){
stack.push(new int[]{price,day});
}else{
while(!stack.isEmpty() && stack.peek()[0] <= price){
day += stack.pop()[1];
}
stack.push(new int[]{price,day});
}
return day;
}
}
|
用Deque快1ms 就不贴了
8.2
一开始没想清楚 其实就是贪心问题 排序后只考虑两个区间的情况 肯定保留右区间小的那个
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) ->a[0]-b[0]);
int []cur = intervals[0];
int ans=0;
for(int i = 1; i < intervals.length; i++){
if(intervals[i][0] < cur[1]){
++ans;
if(intervals[i][1]<cur[1]){
cur = intervals[i];
}
}else{
cur = intervals[i];
}
}
return ans;
}
}
|
写起来麻烦 用时不太好 看看别人怎么写的 80ms 11.49%
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| class Solution {
class Node {
char val;
StringBuilder str;
boolean isWord = false;
Node[] next = new Node[26];
Node(char val,StringBuilder stringBuilder) {
this.val = val;
if(stringBuilder!=null)
str = new StringBuilder(stringBuilder);
else str = new StringBuilder();
str.append(val);
}
Node(){}
}
public List<List<String>> suggestedProducts(String[] products, String searchWord) {
Node root = new Node();
for (String product : products) {
char[] chars = product.toCharArray();
Node node = root;
for (int i = 0; i < chars.length; i++) {
int index = chars[i] - 'a';
if(node.next[index] == null) {
node.next[index] = new Node(chars[i],node.str);
}node = node.next[index];
}node.isWord=true;
}
List<List<String>> result = new ArrayList<>();
char[] chars = searchWord.toCharArray();
for (int i = 0; i < chars.length; i++) {
List<String> list = new ArrayList<>();
int index = chars[i] - 'a';
if(root!=null){
root = root.next[index];
result.add(getProducts(root,list));
}else result.add(list);
}
return result;
}
List<String> getProducts(Node root,List<String> list) {
if(root==null) return list;
if(root.isWord){
list.add(root.str.toString());
if(list.size()==3) return list;
}
for(Node node : root.next) {
if(node!=null) getProducts(node,list);
if(list.size()==3) return list;
}
return list;
}
}
|
无语子 前排都是用排序二分做的啊 根本没用前缀树啊
那我的字典树写得还是挺漂亮的^ ^
REVIEW
想不出来 暴力超时了 剪枝也减不好 感觉思路错了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
int ans = 0;
public int longestZigZag(TreeNode root) {
dfs(root);
return ans;
}
void dfs (TreeNode root) {
if (root == null) return;
getZigZag(root.left,0,false);
getZigZag(root.right,0,true);
dfs(root.left);
dfs(root.right);
}
void getZigZag(TreeNode root,int len,boolean flag) {
if(root == null){
ans=Math.max(ans,len);
return;
}
if(flag) getZigZag(root.left,len+1,false);
else getZigZag(root.right,len+1,true);
}
}
|
离谱 厉害 自底向上的递归dfs 每个节点传左右路径长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
int ans = 0;
public int longestZigZag(TreeNode root) {
dfs(root);
return ans;
}
private int[] dfs(TreeNode root) {
if (root == null) {
return new int[]{-1, -1};
}
int lr = dfs(root.left)[1] + 1;
int rl = dfs(root.right)[0] + 1;
ans = Math.max(ans, Math.max(lr, rl));
return new int[]{lr, rl};
}
}
|
我错得离谱啊 不该对每个节点求最长交错路径的 dfs到最后才判断长度才对 我这都不是dfs的思想了 看看典型的dfs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
int res = 0;
public int longestZigZag(TreeNode root) {
dfs(root, 0, 0);
return res;
}
public void dfs(TreeNode root, int l, int r) {
if (root == null) {
return;
}
res = Math.max(res, Math.max(l, r));
if (root.left != null) {
dfs(root.left, r + 1, 0);
}
if (root.right != null) {
dfs(root.right, 0, l + 1);
}
}
}
|
8.3
用的递归加栈的方式写的 感觉思路不太对
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| class Solution {
int index=0;
public String decodeString(String s) {
char[] chars = s.toCharArray();
int n = chars.length;
StringBuilder res = new StringBuilder();
while(index < n){
if(chars[index] >= 'a' && chars[index] <= 'z'){
res.append(chars[index++]);
}else if(chars[index] >= '0' && chars[index] <= '9'){
push(res,chars);
}
}
return res.toString();
}
void push(StringBuilder str,char [] chars){
int num = chars[index++]-'0';
while(chars[index] >= '0' && chars[index] <= '9'){
num = num*10+(chars[index++]-'0');
}
++index;
StringBuilder stringBuilder = new StringBuilder();
while(chars[index]!=']'){
if(chars[index]>='0' && chars[index]<='9'){
push(stringBuilder,chars);
}else {
stringBuilder.append(chars[index++]);
}
}
String string = stringBuilder.toString();
for(int i=0;i<num;i++){
str.append(string);
}++index;
}
}
|
正常的栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public String decodeString(String s) {
Deque<Integer> intStack = new ArrayDeque<>();
Deque<StringBuilder> stringStack = new ArrayDeque<>();
StringBuilder cur = new StringBuilder();
int num = 0;
for(char c : s.toCharArray()) {
if(Character.isDigit(c)) {
num=num*10+(c-'0');
}else if(c=='[') {
intStack.push(num);
stringStack.push(cur);
cur = new StringBuilder();
num=0;
}else if(c==']') {
int time = intStack.pop();
StringBuilder str = stringStack.pop();
while(time--!=0) str.append(cur);
cur = str;
}else cur.append(c);
}
return cur.toString();
}
}
|
比较数组是否相同 别整花活就比较好写 加了个flag 前一个符合条件的情况下只需要比较两个位置就可以 剪枝
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
public List<Integer> findAnagrams(String s, String p) {
if(s.length() < p.length()) return Collections.emptyList();
int []pChar = new int[26];
char[] chars = s.toCharArray();
for (char c : p.toCharArray()) {
pChar[c - 'a']++;
}
int sLen = s.length(),pLen = p.length();
int []curr = new int[26];
for (int i = 0; i < pLen; i++) {
curr[chars[i] - 'a']++;
}
List<Integer> ans = new ArrayList<>();
boolean flag = false;
if(Arrays.equals(curr, pChar)) {
ans.add(0);flag=true;
}
for (int i = pLen; i < sLen; i++) {
int left = chars[i-pLen]-'a',right=chars[i]-'a';
curr[left]--;curr[right]++;
if(flag){
if(curr[left]==pChar[left]&& curr[right]==pChar[right]){ans.add(i-pLen+1);}
else flag=false;
}else{
if(Arrays.equals(curr, pChar)){ans.add(i-pLen+1);flag=true;}
}
}
return ans;
}
}
|
没想出来 看提示看到前缀和写了一个 结果用时1704ms
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int subarraySum(int[] nums, int k) {
int [] front = new int[nums.length+1];
int n = nums.length,ans=0;
for(int i = 1; i <= n; i++){
front[i] = front[i-1] + nums[i-1];
}
for(int i = 1; i <= n; i++){
for(int j=i;j<=n;j++){
if(front[j]-front[i-1] == k){++ans;}
}
}
return ans;
}
}
|
太帅了 一句话解释清楚所有问题 题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int preSum = 0,ans=0;
for(int num : nums) {
preSum+=num;
if(map.containsKey(preSum-k))
ans+=map.get(preSum-k);
map.put(preSum, map.getOrDefault(preSum, 0) + 1);
}
return ans;
}
}
|
