首页 > 其他 > 详细

560. Subarray Sum Equals K

时间:2017-10-16 20:09:42      阅读:290      评论:0      收藏:0      [点我收藏+]

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

Input:nums = [1,1,1], k = 2
Output: 2

 Note:

  1. The length of the array is in range [1, 20,000].
  2. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

题目含义:求和为k的连续子数组的个数

 

 1     public int subarraySum(int[] nums, int k) {
 2         int[] preSum = new int[nums.length];  //dp数组,位置i上存储从0到i个元素总和
 3         preSum[0] = nums[0];  
 4         for (int i = 1; i < nums.length; i++) preSum[i] = preSum[i - 1] + nums[i];
 5         int result = 0;
 6         for (int i = 0; i < preSum.length; i++) {
 7             if (preSum[i] == k) result++;
 8             for (int j = i + 1; j < preSum.length; j++) {
 9                 if (preSum[j] - preSum[i] == k) result++;   //线段2-线段1==长度k
10             }
11         }
12         return result;
13     }

 

560. Subarray Sum Equals K

原文:http://www.cnblogs.com/wzj4858/p/7678443.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!