本题
1.暴力法会超时,时间复杂度为O(n3)。
2.用一个数组存储该位置的累加和。时间复杂度减少到O(n2)。
3.另一种暴力解法,让end从start开始,省去了一层循环。
4.
public class Solution { public int subarraySum(int[] nums, int k) { int count = 0; for (int start = 0; start < nums.length; start++) { for (int end = start + 1; end <= nums.length; end++) { int sum = 0; for (int i = start; i < end; i++) sum += nums[i]; if (sum == k) count++; } } return count; } }
public class Solution { public int subarraySum(int[] nums, int k) { int count = 0; int[] sum = new int[nums.length + 1]; sum[0] = 0; for (int i = 1; i <= nums.length; i++) sum[i] = sum[i - 1] + nums[i - 1]; for (int start = 0; start < nums.length; start++) { for (int end = start + 1; end <= nums.length; end++) { if (sum[end] - sum[start] == k) count++; } } return count; } }
public class Solution { public int subarraySum(int[] nums, int k) { int count = 0; for (int start = 0; start < nums.length; start++) { int sum=0; for (int end = start; end < nums.length; end++) { sum+=nums[end]; if (sum == k) count++; } } return count; } }
public class Solution { public int subarraySum(int[] nums, int k) { int count = 0, sum = 0; HashMap < Integer, Integer > map = new HashMap < > (); map.put(0, 1); for (int i = 0; i < nums.length; i++) { sum += nums[i]; if (map.containsKey(sum - k)) count += map.get(sum - k); map.put(sum, map.getOrDefault(sum, 0) + 1); } return count; } }