和为k的子数组

Zhang Jin · Zhang Jin · commit a366ea59aedd · 2025-01-14T11:25:13.000+08:00
diff --git a/basic/algorithm/src/main/java/com/jinchanc/hot100/PrefixSum.java b/basic/algorithm/src/main/java/com/jinchanc/hot100/PrefixSum.java
@@ -0,0 +1,46 @@
+package com.jinchanc.hot100;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * @author zhangjin@algorix.co
+ * @since 2025/1/14 10:31
+ */
+public class PrefixSum {
+
+    public static int findPrefixSum(int[] nums, int k) {
+        List<Integer> prefixSum = new ArrayList<>();
+        int count = 0;
+        for (int i = 0; i < nums.length; i++) {
+            if (i == 0) {
+                prefixSum.add(nums[i]);
+            } else {
+                prefixSum.add(nums[i] + prefixSum.get(i - 1));
+            }
+        }
+
+        // 左右边界条件理解
+        // x - sum = y 条件？
+        for (int i = -1; i < nums.length - 1; i++) {
+            for (int j = i + 1; j < nums.length; j++) {
+                int sum;
+                if (i == -1) {
+                    sum = prefixSum.get(j);
+                } else {
+                    sum = prefixSum.get(j) - prefixSum.get(i);
+                }
+
+                if (sum == k) {
+                    count++;
+                }
+            }
+        }
+
+        return count;
+    }
+
+    public static void main(String[] args) {
+        System.out.println(findPrefixSum(new int[]{1, 2, 3}, 3));
+    }
+}
diff --git a/basic/algorithm/src/main/java/com/jinchanc/hot100/SlideWindow.java b/basic/algorithm/src/main/java/com/jinchanc/hot100/SlideWindow.java
@@ -46,6 +46,18 @@ public List<Integer> findAnagrams(String s, String p) {
         }
         return result;
     }
+
+    // 和为k的子数组
+    public int countK(int[] nums, int k) {
+        int count = 0;
+        int sum = 0, left = 0, right = 0;
+        for (int i = 0; i < nums.length; i++) {
+            int num = nums[i];
+
+        }
+        return count;
+    }
+
     public static void main(String[] args) {
         System.out.println(new SlideWindow().findAnagrams("abcba", "abc").equals(List.of(0, 2)));
     }

Original file line number	Diff line number	Diff line change
`@@ -46,6 +46,18 @@ public List<Integer> findAnagrams(String s, String p) {`
`46`	`46`	`}`
`47`	`47`	`return result;`
`48`	`48`	`}`
	`49`	`+`
	`50`	`+ // 和为k的子数组`
	`51`	`+ public int countK(int[] nums, int k) {`
	`52`	`+ int count = 0;`
	`53`	`+ int sum = 0, left = 0, right = 0;`
	`54`	`+ for (int i = 0; i < nums.length; i++) {`
	`55`	`+ int num = nums[i];`
	`56`	`+`
	`57`	`+ }`
	`58`	`+ return count;`
	`59`	`+ }`
	`60`	`+`
`49`	`61`	`public static void main(String[] args) {`
`50`	`62`	`System.out.println(new SlideWindow().findAnagrams("abcba", "abc").equals(List.of(0, 2)));`
`51`	`63`	`}`